문제 해결 기법
아래 내용들은 재귀를 적극적으로 사용함
•
분할정복
•
백트래킹
•
동적계획법
•
그리디 알고리즘
분할정복(Divide & Conquer)
큰 덩어리로 자르기
분할정복의 대표적인 예시 : MergeSort
1.
주어진 배열을 대략 절반으로 나눈다
2.
두 서브 배열을 각각 정렬(w. Recursion)
3.
정렬된 두 서브 배열을 합쳐서(merge) 하나의 정렬된 배열로 만든다
단, 주어진 인스턴스가 충분히 작으면 재귀없이 바로 해결(base case)
D&C Examples : Max
새로운 문제를 맞이했을 때, 감이 잘 안 온다. 그럴때 재귀를 떠올려서 분할정복을 생각해볼 법하다.
•
입력 : 배열 - 원소 N개
•
출력 : 배열의 최대값
max1(A[0, ..., n-1]):
m = A[0]
for i in range(n):
if A[i] > m:
m = A[i]
return m
max_dc(A[0, ..., n-1]):
if n == 1:
return A[0]
mid = n // 2
m1 = max_dc(A[0, ..., mid])
m2 = max_dc(A[mid, ..., n-1])
if m1 > m2:
return m1
else:
return m2
Python
복사
분할정복같은 고급 기술을 사용해도 사실은 최대값을 찾으려면 N개를 모두 확인해야 최대값을 구할 수 있음. 그러므로 O(N)보다 빠를 수 없음.
Binary Search(이분 탐색)
정렬된 배열에서 특정 값 K를 찾고 싶을 때, 배열의 어느 인덱스에 있는 지 찾아내는 알고리즘
•
A의 중간값을 K와 비교해 같으면 리턴
•
K가 작으면 왼쪽 절반에 대해 탐색 계속
•
K가 크면 오른쪽 절반에 대해 탐색 계속
이분탐색은 사실 분할 정복 문제 : 중간값을 K와 비교한 후에 배열의 절반에 대해서만 탐색을 지속. 즉 남은 n/2 크기의 부분 배열에 대한 서브 문제를 풀면 문제 해결
Multiplication(곱셈)
•
입력 : 두 정수 x,y
•
출력 : x와 y를 곱셈한 결과
분할 정복 방식
•
어떻게 분할하지?
•
분할 후 서브 문제를 풀고 나서는 어떻게 마무리하지?
EX : 1472 x 3986•
(14 | 72) x (39 | 86)으로 잘라보자
◦
14 | 72 : 1400 + 72
◦
39 | 86 : 3900 + 86
▪
⇒ ((14 x 39) x 10000) + ((14 x 86) x 100) + ((32 x 39) x 100) + (72 x 86)
•
시간복잡도 분석
◦
재귀 부분 : n/2 사이즈의 인스턴스들을 4번 재귀호출(recursion call) : 4 x T(n/2)
◦
재귀가 아닌 부분 : 덧셈과 쉬프트 연산(뒤에 0 붙이기) : T(n)
◦
결론 : T(n) = O(n^2)
Fast Multiplication
•
더 빠르게는 안되는 걸까 : O(N^2)이 최선인가?
Dynamic Programming
Smart Recursion
Fibonacci Number
F(n) ⇒ 0(n이 0인 경우), 1(n이 1인 경우), (F(n-1) + F(n-2))(나머지)
Recurisve Fibonacci is Horribly slow
•
수가 커지면 시간이 엄청 오래 걸림
•
피보나치 수(단순 재귀함수 버전)는 시간복잡도가 1.6^N(지수함수 형태) → 즉, n이 1 증가할 때마다 1.6배만큼 시간이 더 소요됨
동적 계획법 : Fill the table
•
배열에 순서대로 값을 저장해서 재사용함으로써 중복되는 함수의 결과는 그대로 사용
◦
DP 알고리즘은 중간의 서브 문제에 대한 솔루션을 저장(기억)해내는 것
◦
정말 중요한 것은 올바른 점화식을 찾는 것
▪
점화식을 찾는게 제일 어려움
◦
점화식을 이용해서 배열(1차원) or 테이블(2,3차원)을 순서대로 채워 나간다
동적계획법은 테이블을 채워내는 내용이 아니다. smart recursion에 대한 내용이다!
패턴 : 동적 계획법
DP를 사용해 문제를 해결하는 일반적인 과정
1.
️ Formulate the problem recursivelya.
문제를 해결하는 점화식이나 문제를 해결하는 재귀 알고리즘을 찾아내야함
b.
계산할 값이 무엇인지(what) 결정하고, 그것에 대한 점화식을 구함
2.
Build Solutions to your recurrence from the bottom up
예제 1 : 최단경로는 몇가지?
A → B 가는 최단경로의 개수 구하는 문제•
입력 : m,n(맵 크기)
•
출력 : 격자에서 (0,0)에서 (m,n)으로 가는 최단경로의 수
DP로 풀기 위해,
•
계산할 값들의 정의 및 부분문제 설정 : P(i,j)를 (0,0)에서 (i,j)까지 가는 최단경로 개수라고 하자
•
계산할 값들에 대한 점화식 구하기
◦
base case는 1 : i=0 or j=0의 경우
◦
P(i,j) = P(i-1,j) + P(i,j-1) : 나머지
즉, Bottom-Up 순으로 계산하는 알고리즘 설계 및 기술
•
i,j 증가 순으로 P(i,j)를 계산해나가면서 저장하면 됨
•
O(mn) 시간 소요
•
마지막으로 P(m,n) 리턴
예제 2 : Subsequence
Longest Common Subsequence(LCS) - TopDown 방식인듯
입출력•
입력 : 두 문자열 A,B
•
출력 : A,B의 LCS 길이
•
A와 B는 배열 형식으로 주어진다고 합시다 : A[1,…,m], B[1,…,n]
️ L(i,j)을 A[1,…,i], B[1,…,j] 사이의 LCS 길이로 ‘정의’합시다•
우리가 원하는 답은 L(m,n)
•
나머지 i,j에 대한 L(i,j)값들을 풀어내는 것이 부분문제
•
base case: i=0 혹은 j=0일때
•
일반적인 경우에 대한 L(i,j)의 재귀적 구조를 찾아라!! → 점화식
같은 문자끼리 선을 잇는다고 생각해보세요(짝짓기). 이러면 두 문자열에서 같은 문자들에 대해 선을 연결하면 교차하는 선이 생기지 않습니다. 그럼 i,j에서 짝을 찾으면 (인덱스 1~i)와 (i~마지막)로 분할되어 부분 문제로 생각해볼 수 있습니다.•
그래서 L(i,j)을 A[1,…,i], B[1,…,j] 사이의 LCS 길이로 정의
•
즉, L(i,j)의 재귀적 구조를 찾아라!!(i > 0 and j > 0)
◦
A[i] = B[j]인 경우
▪
짝짓기를 하고, 나머지 부분(L(i-1,j-1))에 대해 찾고 +1을 해준다
◦
A[i] ≠ B[j]인 경우
▪
짝짓기를 안 하기로 한 경우 → 두 가지 경우로 쪼개짐
•
L(i, j-1)
•
L(i-1,j)
•
결론 : 총 3가지 경우로 쪼개진다. 그 중에서 다른 경우에서는 둘 중 큰 값을 택하면 되는 구조
◦
max(L(i-1,j-1) + 1, L(i, j-1), L(i-1,j)) [같은 경우]
◦
max(L(i, j-1), L(i-1,j)) [다른 경우]
◦
0 [i=0 or j=0]