동적 계획법

분할정복 vs 동적 계획법

동적 계획법은 현재 문제를 부분문제로 나눈 뒤 현재 문제의 답을 구한다는 점에서 분할정복과 비슷하지만

분할 정복은 부분문제를 한번만 계산하게 되는 반면,

동적 계획법은 같은 부분문제를 여러 차례 계산한다.

따라서 중복적인 계산을 피하기 위해 메모이제이션 기법이 반드시 필요하며, 

두번 이상 계산되는 부분문제를 중복되는 부분문제 (overlapping subproblems) 라고 부른다.

(a)는 분할 정복 (b)는 동적 계획법

메모이제이션

입력 n과 r 이 정해져 있을 떄 bino(n, r) 의 반환값이 일정

∴ 한번 계산한 값을 저장해 뒀다가 재활용하는 최적화 기법을 사용해야 함

이와 같이 

두번이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써, 속도의 향상을 꾀하는 알고리즘 설계 기법을 동적 계획법이라고 한다.

메모이제이션 주의 할 점

최적화 동적 계획법 레시피

1. 모든 답을 만들어 보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다.
2. 전체의 값을 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 값 만을 반환하도록 부분 문제 정의를 바꾼다.
3. 재귀 호출의 입력에 이전 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다.
   문제가 최적 부분 구조에 성립할 경우에는 이전 선택에 관련된 정보를 완전히 없앨 수도 있다.
   입력의 정보가 줄어들면 줄어들수록 더 많은 부분 문제가 중복되고, 따라서 메모이제이션을 최대한 활용할 수 있다.
4. 입력이 배열이거나 문자열인경우 가능하다면 적절한 변환을 통해 메모이제이션을 이용할 수 있도록 한다.
5. 메모이제이션을 적용한다.

p. 175 ~ p. 205

분할 정복

1. 주어진 문제를 둘 이상의 부분문제로 나눈 뒤, (Divide)
2. 각 문제의 답을 재귀호출을 통해 계산 후 (Merge)
3. 각 답으로부터 원래 문제의 답을 계산하는 알고리즘 (Base case)

순수 재귀호출 방식과 다른 점

문제

쿼드 트리 뒤집기

울타리 잘라내기

p.91 ~ p.126

반복문

알고리즘의 수행시간을 지배하는 것은 반복문

반복문의 수행 횟수는 입력의 크기에 대한 횟수로 표현

수행시간에 따른 알고리즘 분류

선형 시간 알고리즘

입력의 크기에 대비해 걸리는 시간을 그래프로 그리면 직선인 경우.

우리가 찾는 좋은 알고리즘.

선형 이하 시간 알고리즘

N을 계속 절반으로 나누는 일을 1이하가 될때까지 지속

lgN: 100,000 을 17번만 나누면 1에 도달 함

ex) 이진 탐색 알고리즘

• 정렬이 필요 A[ ]
• A[i-1] < x <= A[i]

다항 시간 알고리즘

반복문의 수행 횟수를 다항식으로 표현

대다수의 알고리즘에 해당

지수 시간 알고리즘

완전탐색 방식, 재귀호출을 통해 할지 말지 결정하는 알고리즘

ex) DFS

n 가지 경우, 모든 조합의 수 2ⁿ, 조합이 맞는지 여부 체크 m*n

∴ 재귀호출() 2ⁿ + isValid() m*n = mn2ⁿ

입력으로 주어지는 숫자의 갯수가 아닌 숫자의 값에 따라 지수시간이 될 수도 있음

시간 복잡도

시간복잡도가 높다

입력의 크기가 증가할 때 수행시간이 급격히 증가

시간복잡도가 낮다

입력의 크기가 증가해도 수행시간이 비슷

알고리즘 수행시간은 보통 최악의 시간을 측정

O 표기법 (Big-O Notation)

주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지 다 버림

정렬 알고리즘

선택 정렬은 무조건 O(N²)

삽입 정렬은 O(N) ~ O(N²) 까지 입력에 따라 다름

∴ 대부분의 경우 삽이 정렬이 더 빠름

∴ 삽입 정렬은 O(N²) 정렬 중 가장 빠른 알고리즘

수행 시간 어림짐작하기

1초 ≒ 1억

ex)

알고리즘 선택에 따른 수행 시간 비교

문제) 1차원 배열 연속된 부분 구간의 합이 최대인 구간

완전 탐색: O(N³)

반복문 2개 + 메모이제이션: O(N²)

분할 정복 알고리즘: O(NlgN)

동적 계획법: O(N)