08 01 - nolsigan/nolsigan.github.io GitHub Wiki

Algorithm

| Algorithm 의 내용은 대부분 '알고리즘 해결 전략'을 요약한 것입니다.

동적 계획법

동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다.
이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있다.

• 값을 저장해 두는 메모리의 장소를 캐시(cache)
• 중복되는 부분 문제(overlapping subproblems)

이와 같이 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법을 메모이제이션(memoization)이라 부른다.

참조적 투명성 (referential transparency)

함수의 반환 값이 그 입력 값만으로 결정되는지의 여부를 참조적 투명성이라 한다.

구현 패턴

• 항상 기저 사례를 제일 먼저 처리
• 함수의 반환 값이 항상 0 이상이면 초기값을 -1로 설정
• reference (&)의 사용으로 값의 변환과 저장을 한번에 함

시간 복잡도

(존재하는 부분 문제의 수) X (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

완전 탐색과의 관계

완전 탐색으로 답을 구할 때 흔히 가장 문제가 되는 것은, 원하는 답은 없는데 전체 답의 개수는 무지막지하게 많은 경우다.
동적 계획법을 사용하면 완전 탐색이 만드는 경로의 수가 매우 커도 불리는 함수의 경우의 수가 제한적이므로 비둘기집의 원리에 의해 중복으로 해결되는 문제가 항상 존재한다.

최적 부분 구조

탐색 과정에서 지금까지의 경로와 무관하게 현재 부분 문제를 해결할 수 있으면 이를 최적 부분 구조를 갖는다고 한다.
대부분 직관적이라 따로 증명이 필요하지 않지만 그렇지 않은 경우 귀류법, 대우로 증명하게 된다.

=> 최적 부분 구조를 만족하는 부분 문제로 잘 나누는 능력이 동적 계획법을 잘하는 방법이다!