[Python/파이썬] 백준 1208번: 부분수열의 합 2

문제 풀이 1. 주어진 수열을 절반으로 나눈다. [-7, -3, -2, 5, 8] -> [-7, -3], [-2, 5, 8] 2. 나눠진 수열의 부분 수열을 구한다. A : [-7, -3] -> [-7], [-3], [-7, -3] B : [-2, 5, 8] -> [-2], [5], [8], [-2, 5], [-2, 8], [5, 8], [-2, 5, 8] 3. A의 부분 수열 중 하나를 선택하고, B의 부분 수열 중 하나를 선택하면 모든 부분 수열을 구할 수 있다. ex) [-7, -3, 5] = [-7, -3] + [5] 4. A, B 부분 수열의 합을 배열에 저장한다. sumA : [-7, -3, -10] sumB : [-2, 3, 5, 6, 8, 11, 13] 5. sumA, sumB 그리고 su..

[Python/파이썬] 백준 15732번: 도토리 숨기기

문제 풀이 입력이 다음과 같을 때, 200 2 5 100 150 10 110 150 15 상자의 번호는 0 ~ 200까지 있다. 우선 중간 값(100)을 구하고, 0번 상자에서 100번 상자까지의 도토리 개수를 구한다. 도토리 개수에 따라 이분 탐색을 수행하면 된다. 코드 import sys input = sys.stdin.readline #도토리 수 구하기 def calAcorn(rules, boxNum): cnt = 0 for start, end, margin in rules: if boxNum < start: continue end = min(boxNum, end) cnt += (end - start) // margin + 1 return cnt def binarySearch(rules, end, ..

[Python/파이썬] 백준 10942번: 팰린드롬?

문제 풀이 dp[i][j] : i ~ j까지의 수열이 팰린드롬인지 저장 ex) dp[1][3] = True : 1 ~ 3까지의 수열이 팰린드롬 수 arr 배열에 전체 수열 저장 1. 원소가 하나인 경우 무조건 팰린드롬 수 dp[0][0], dp[1][1], ... dp[n][n] = True 2. arr[i] == arr[i+1]인 경우 팰린드롬 수 (부분 수열의 길이가 2이고, 원소가 동일한 경우) ex) 11, 22, 33, 44 는 팰린드롬 수 3. a~b까지의 수열에서 arr[a] == arr[b]이고 그 사이의 수열이 팰린드롬인 경우 원소가 4개인 경우, 5개인 경우 ... 반복하면 된다. 코드 import sys input = sys.stdin.readline n = int(input()) a..

[Python/파이썬] 백준 1695번: 팰린드롬 만들기 / 파이썬 메모리초과 해결

문제 풀이 1. 주어진 수열에서 팰린드롬 수열을 구한다. 12342의 부분 수열 중 팰린드롬은 242(12342)이다. 2. 팰린드롬의 정 가운데를 기준으로 수열을 나눈다. 123 4 2 3. 팰린드롬이 아닌 수를 반대편에 추가한다. 123 4 321 수열에서 이미 팰린드롬인 수열을 구했고, 팰린드롬이 아닌 수만 추가하면 되므로 최적의 알고리즘이다. 또다른 예시 팰린드롬을 찾는 과정에서 DP가 이용된다. [수열 A] 12342 [수열 A를 뒤집은 수열 B] 24321 이 있다고 가정해보자. 수열 A와 수열 B의 최장 공통 부분 수열(LCS)이 곧 팰린드롬 수열이다. (수열 A를 뒤집었을 때의 부분 수열 = 수열 A의 부분 수열 이므로, 팰린드롬 수열의 조건을 생각해봐라) 말로 설명하기가 참 어렵다... ..

[Python/파이썬] 백준 17404번: RGB거리 2

문제 풀이 첫 번째 집의 색을 R로 선택하고 DP를 통해 최솟값을 구한다. G, B에 대해 반복 코드 import sys input = sys.stdin.readline n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] def minPaint(selHouse): dp = [[0] * 3 for _ in range(n)] dp[0] = arr[0] for i in range(3): if i == selHouse: dp[1][i] = 1e9 continue dp[1][i] = arr[1][i] + arr[0][selHouse] for i in range(2, n): dp[i][0] = min(dp[i - 1][1], dp[i..

[Python/파이썬] 백준 14942번: 개미

문제 풀이 1. 주어진 입력은 양방향 간선이므로 단방향 간선으로 만들어줘야함 2. 희소배열 사용 https://hello-capo.netlify.app/algorithm-sparse-table/ 🧩 [Algorithm] 희소 배열(Sparse Table) 알고리즘 | hello-capo! 희소 배열(Sparse Table) 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 데이터가 저장되지 않은 경우가 더 많은 희소 행렬과 같이, 희소 배열은 배열의 원소 위치가 연속적이지 않은 배 hello-capo.netlify.app 3. LCA와 유사하게 노드 탐색 https://cyberflower.github.io/2019/07/22/LCA.html LCA(Least Common Ancestor)..

[Python/파이썬] 백준 16437번: 양 구출 작전

문제 풀이 경로는 유일하므로 방문 처리는 따로 구현하지 않았다. 트리의 리프 노드까지 재귀를 통해 이동하고, 리턴 값을 통해 문제를 풀었다. 코드 import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline n = int(input()) tree = [[] for _ in range(n + 1)] for i in range(2, n + 1): type, amount, root = input().split() amount, root = int(amount), int(root) if type == 'W': amount = -amount tree[root].append((i, amount)) def dfs(x, amount): for next, nex..

[Python/파이썬] 백준 17616번: 등수 찾기

문제 풀이 등수를 찾을 노드 위로 몇 개의 노드가 있는지, 아래로 몇 개의 노드가 있는지 구하면 된다. 코드 import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline n, m, x = map(int, input().split()) up = [[] for _ in range(n + 1)] down = [[] for _ in range(n + 1)] for _ in range(m): a, b = map(int, input().split()) down[a].append(b) # a 아래에 b up[b].append(a) # b 위에 a visited = [False] * (n + 1) def dfs(x, graph, cnt): visited[x] ..

[Python/파이썬] 백준 16947번: 서울 지하철 2호선

문제 풀이 먼저 사이클을 구한다. 사이클은 하나만 존재하고, 길이는 3 이상 이어야 한다. for i in range(1, n + 1): if not visited[i]: tmp = [] if dfs(i, tmp): print(cycle) break def dfs(x, tmp): global cycle visited[x] = True tmp.append(x) for next in graph[x]: if visited[next]: if next in tmp: if len(tmp[tmp.index(next):]) >= 3: cycle = set(tmp[tmp.index(next):]) return True continue dfs(next, tmp) tmp.pop() 사이클을 이루는 노드에서 시작하여 깊이를 ..

[Python/파이썬] 백준 3584번: 가장 가까운 공통 조상

문제 풀이 백준 LCA 문제와 동일한 줄 알았는데 아니었다. https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 차이점은 LCA의 경우 양방향 간선으로 입력이 주어지지만, 가장 가까운 공통 조상의 경우 단방향으로 간선이 주어진다. 또한 LCA는 루트 노드가 1로 고정되지만, 가장 가까운 공통 조상의 경우 루트 노드를 직접 구해야 한다. 코드 import sys sys.setrecursionlimit(10**9) input = sys.stdin..