기록과 정리의 공간

백준 9251번 : LCS(문제 링크) 사용 언어 : 파이썬(Python) 문제 유형 : 동적 프로그래밍(DP), LCS 난이도 : 하 소스코드 import sys x = sys.stdin.readline().rstrip() y = sys.stdin.readline().rstrip() D = [[0] * (len(y)+1) for _ in range(len(x)+1)] for i in range(1, len(x)+1): for j in range(1, len(y)+1): if x[i-1] == y[j-1]: D[i][j] = D[i-1][j-1] + 1 else: D[i][j] = max(D[i][j-1], D[i-1][j]) print(D[len(x)][len(y)]) 설명 최장 공통 부분 수열(LCS..

백준 11053번 : 가장 긴 증가하는 부분 수열(문제 링크) 사용 언어 : 파이썬(Python) 문제 유형 : 동적 프로그래밍(DP), LIS 난이도 : 하 소스코드 import sys n = int(sys.stdin.readline()) array = list(map(int, sys.stdin.readline().split())) D = [1] * n for i in range(1, n): for j in range(0, i): if array[j] < array[i]: D[i] = max(D[i], D[j] + 1) print(max(D)) 설명 가장 긴 증가하는 부분 수열(LIS) 문제는 전형적인 DP문제이다.(반드시 알아두기!) 수열의 크기가 n일 떄, 기본적인 DP알고리즘으로 O(n^2)에 해..

백준 12865번 : 평범한 배낭(문제 링크) 사용 언어 : 파이썬(Python) 문제 유형 : 동적 프로그래밍(DP) 난이도 : 하 소스코드 import sys n, k = map(int, sys.stdin.readline().split()) dp = [[0] * (k+1) for _ in range(N+1)] for i in range(1, n+1): weight, value = map(int, sys.stdin.readline().split()) for j in range(1, k+1): if j < weight: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value) print(dp[n][k]..

백준 1904번 : 문제집 (문제 링크) 사용 언어 : 파이썬(Python) 문제 유형 : 동적 프로그래밍 난이도 : 하 소스코드 주의 : 아래에서 cache를 [0] * 1000001가 아니라 cache = [0] * (n+1)으로 작성하면 n=1 일 때, cache = [0, 0]이므로 cache[2] = 2 에서 IndexError가 발생한다. import sys n = int(sys.stdin.readline()) cache = [0] * 1000001 cache[1] = 1 cache[2] = 2 for i in range(3, n+1): cache[i] = (cache[i-2] + cache[i-1]) % 15746 print(cache[n]) 설명 동적 프로그래밍문제의 가장 기본적이면서, 전..

백준 1766번 : 문제집 (문제 링크) 사용 언어 : 파이썬(Python) 문제 유형 : 힙, 위상정렬 난이도 : 중 소스코드 import sys, heapq n, m = map(int, sys.stdin.readline().split()) array = [[] for i in range(n+1)] indegree = [0] * (n+1) heap = [] result = [] for _ in range(m): a, b = map(int, sys.stdin.readline().split()) array[a].append(b) indegree[b] += 1 for i in range(1, n+1): if indegree[i] == 0: heapq.heappush(heap, i) while heap: no..

백준 1991번 : 트리 순회 (문제 링크) 사용 언어 : 파이썬(Python) 문제 유형 : 트리, 구현 난이도 : 하 소스코드 import sys n = int(sys.stdin.readline()) class Node: def __init__(self, head, left, right): self.head = head self.left = left self.right = right tree = dict() for _ in range(n): head, left, right = sys.stdin.readline().split() tree[head] = Node(head, left, right) def pre_order(node): print(node.head, end='') if node.left !=..

백준 2212번 : 센서 (문제 링크) 사용 언어 : 파이썬(Python) 문제 유형 : 그리디 난이도 : 하 소스코드 import sys n = int(sys.stdin.readline()) k = int(sys.stdin.readline()) pos = sorted(list(map(int, sys.stdin.readline().split()))) if k >= n: print(0) sys.exit() dist = [] for i in range(1, n): dist.append(pos[i] - pos[i-1]) dist.sort(reverse=True) for _ in range(k-1): dist.pop(0) print(sum(dist)) 설명 결론적으로 정렬만 수행하면 되므로 시간복잡도 O(Nlo..

백준 4195번 : 친구 네트워크 (문제 링크) 사용 언어 : 파이썬(Python) 문제 유형 : 해싱, 최소 스패닝 트리 난이도 : 중 소스코드 import sys t = int(sys.stdin.readline()) def find(node): if parent[node] != node: parent[node] = find(parent[node]) return parent[node] def union(node1, node2): root1 = find(node1) root2 = find(node2) parent[root2] = root1 number[root1] += number[root2] for _ in range(t): f = int(sys.stdin.readline()) number = dict..