신찬수 교수님의 알고리즘 동적계획법 - zigzag 문제 영상을 정리했습니다. 수열 [1,7,4,9,2,5] 가 있을 때, 이를 지그재그 수열이라고 한다. 크기가 큰 것과 작은 것이 번갈아 나오는 수열을 지그재그 수열이라고 한다. 수열 [1,5,3,2,7] 은 3 다음의 원소가 3보다 작은 2 이기 때문에 지그재그 수열이 아니다. 수열이 주어졌을 때, n개를 뽑아서 지그재그 수열을 만든다. 예를 들어, [3,2,0,7,1,4,5,8,3]에선 [2,7,1,4,3]을 뽑아서 길이가 5인 지그재그 수열을 만들 수 있다. 만들 수 있는 지그재그 수열 중, 가장 길이가 긴 지그재그 수열을 구하는 것이 문제이다. 수열 [3,-1,2, 5, 7, 4, 5, 9, 8]에서, 5 (인덱스 6) 로 끝나는 지그재그 수열 ..
신찬수 교수님의 알고리즘 동적계획법 - LCS 문제 영상을 정리했습니다. 동적계획법의 순서 다시 정리 ! 1. 해를 분석 후 부문제로 분할 2. 부문제의 해로 큰 문제의 해를 표현(점화식) 3. 적당한 순서로 DP table을 채우기 4. DP table에서 원문제의 해를 계산하고 알고리즘의 정당성 증명 LCS(Longest Common Subsequence) 문제 주어진 수열에서 일부 원소(문자)를 지웠을 때 남은 수열(문자열)을 부분 수열이라고 한다. 주의할 것은 원래 수열에서 연속하지 않아도 된다는 것이다. 영어 대문자로 구성된 X, Y 문자열이 주어진다. X = ABCDDAB Y = BDCABA 이때 ABCDDAB에서 부분 수열이라고 하면 ABCDDAB의 CDD와 같이 연속으로 이어진 것만 가능하..
신찬수 교수님의 알고리즘 동적계획법 -예제 문제 - 최대구간합 1 영상을 정리했습니다. 최대구간합 문제 : 4가지 풀이법 n개의 정수 리스트가 주어졌을 때, 연속되는 숫자의 합이 최대가 되는 구간을 구하는 문제 A = [1, -1, 3, -4, 5, -4, 6, -2] 첫 번째 방법 : 브루트 포스 문제의 정답은 A[i] + ... + A[j]가 된다. (i = r: return A[l] m = (l+r)//2 L = max_interval(A, l, m) R = max_interval(A, m+1, r) # M 계산 # for loop를 통해서 구한다.O(N)의 시간이 걸린다. # M 계산 부분 (코드 생략) return max(L, M, R) L과 R을 구하는 과정은 각각 T(A의 원소수/2), M을..
신찬수 교수님의 알고리즘 - 동적계획법 소개 영상을 정리했습니다. 동적계획법 (Dynamic Programming) - 소개 n까지의 수의 합을 구하는 경우 sum(n) = sum(n-1) + n (단, sum(1) = 1) 위처럼 함수를 재귀호출해서 사용해서 구할 수 있다. 이때 만약 sum 값이 S라는 배열에 저장된다면 아래와 같은 코드가 된다. S[n] = S[n-1] + n (단, S[1] = 1) 첫 번째의 경우는 재귀호출을 사용하는 경우로 분할정복 방법이고, 두 번째 경우는 값을 배열에 저장해 재사용하는 경우로 동적계획법이다. 분할정복은 어떤 문제를 계속해서 작은 문제로 쪼갠 뒤, 작은 문제의 답을 통해 원 문제의 해답을 얻는 방법이다. 분할정복의 경우 분할된 각각의 작은 문제들이 중복이 없지..
Tushar Roy - Coding Made Simple님의 Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search) 영상을 정리했습니다. KMP 하위 문자열 검색(KMP Substring Search) 문자열이 있을 때, 패턴 문자열이 문자열 안에 존재하는지 여부를 판단하는 알고리즘 문자열 abcbcglx에 패턴 bcgl이 존재하는지의 여부를 확인할 때, 일반적인 방법은 반복문을 돌리면서 문자열을 하나씩 비교하는 것이다. 이 경우 시간복잡도는 문자열의 길이 M, 패턴 길이 N에 비례하는 O(MN)이다. KMP 검색은 O(M+N) 시간에 하위 문자열 검색을 수행할 수 있다. 알고리즘 문자열 abxabcabcaby에서 패턴 abcaby이 존재하는지 KMP 알..
