자료구조+알고리즘

LCS - 최장 공통 부분 수열

LCS? LCS (longest common substring)는 두 문자열 사이에 가장 긴 공통 부분 문자열을 구하는 문제이다. dp를 이용해 쉽게 해결할 수 있다! str1 = "ABCGI" str2 = "ACGIK" dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)] result = "" for i in range(1, len(str1) + 1): for j in range(1, len(str2) + 1): if str1[i - 1] == str2[j - 1]: result += str1[i - 1] dp[i][j] += dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) ..

가장 긴 증가하는 부분 수열

이게머임? DP 알고리즘의 문제 해결 기법 중 하나로, 어떠한 수열이 주어졌을 때, 원소가 증가 혹은 감소 하는 형태(내림차순 or 오름차순)가 가장 긴 부분 수열을 찾는 방법! 길이가 n인 수열에서 dp 테이블의 모든 원소 값을 1로 초기화 한 후 dp[i]가 array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이라고 정하면 점화식은 아래와 같다! 모든 0

플로이드-워셜

플로이드-워셜 다익스트라: 출발점을 정했을 때 다른 노드에 이르는 최단거리. 플로이드-워셜: 모든 지점에서 다른 모든 지점까지 최단거리. 시간복잡도 O(N^3) 핵심은 점화식! D_{ab} = min(D_{ab}, D_{ak} + D_{kb}) a에서 b로 가는 거리 = a에서 b로 바로 가는 경우와 a에서 k를 거쳐 b를 가는 비용의 최솟값 각 노드별로 해당 노드를 거쳐가는 경우를 고려해서 최단 경로를 갱신하면 끝! 예를 들어 1번 노드를 거쳐가는 경로는 D23 = min(D23, D21 + D13) D24 = mIn(D24, D21 + D14) D32 = min(D32, D31 + D12) D34 = min(D32, D31 + D14 D42 = min(D42, D41 + D12) D43 = min(D..

우선순위 큐 다익스트라

우선순위 큐 heapq 라이브러리를 활용해서 우선순위 큐 사용 가능. 데이터가 리스트 형태일 경우, 0번 인덱스를 우선순위로 인지, 우선순위가 낮은 순서대로 pop 할 수 있음!! import heapq queue = [] heapq.heappush(queue, [2, 'A']) heapq.heappush(queue, [5, 'B']) heapq.heappush(queue, [1, 'C']) heapq.heappush(queue, [7, 'D']) print (queue) //[[1, 'C'], [5, 'B'], [2, 'A'], [7, 'D']] for index in range(len(queue)): print (heapq.heappop(queue)) //[1, 'C'] //[2, 'A'] //[5,..