5. 재귀 호출 - 완전 탐색, 동적 프로그래밍

 

완전 탐색

완전 탐색은 모든 경우의 수를 다 해보는 것으로 Brute Force라고도 한다.
컴퓨터의 빠른 계산 능력을 이용하여 모든 경우의 수를 해보지만, 시간 역시 최대로 소모된다.
for문을 사용하여 정말 모든 경우를 탐색하는 방법과, 재귀, DFS/BFS/ 백트래킹, 비트마스크 등이 존재한다.
위와 같은 방법들을 간단하게 소개하도록 하겠다.

재귀 호출 - 어느 함수가 자기 자신을 다시 참조하는 방법이다.
$f(n) = f(n-1) + f(n-2)$ 등의 피보나치 수열, $n! = (n-1)! * n$ 과 같은 팩토리얼 연산 등에서 자주 등장한다.
하지만 재귀함수는 잘못 사용하면 복잡도가 어마어마하고, 함수가 끝날 때까지 자기 자신 호출 이후의 명령문이 수행되지 않는다.
또한 반드시 종료조건이 있어야 무한루프를 방지할 수 있다.

백트래킹 - 한국말로 퇴각검색이라고 하는데, 어느 경로(노드)를 탐색할 때 가망이 없으면 이전으로 돌아가(부모 노드) 다시 탐색하는 방법이다.

DFS/BFS - 둘다 그래프에서 경로를 탐색하는 방법으로 DFS 는 깊이 우선 탐색(Depth-First-Search), BFS는 너비 우선 탐색 (Breadth-First-Search)이다.
DFS는 사실상 백트래킹을 사용한 기법으로 한가지 경로를 끝까지 탐색한 후, 이전 분기점으로 되돌아가 다시 탐색해보는 방법이고,
BFS는 갈 수 있는 모든 경로를 한 번씩 탐색하고 다음 분기점으로 넘어가는 방식이다.

비트마스크 - 자료 구조를 사용하지 않고, 간단하게 집합 등의 요소들을 표현하고 연산하는 방법.
1000000개를 담을 크기의 배열을 만들어야 하는데, 단순히 T/F만 표현하고자 하면, 굳이 배열을 만들 필요없이 000.....00으로 표현하고
위의 비트 연산등을 통해 적절한 위치에 1과 0으로 바꿔주면 된다.

 

동적 프로그래밍

동적 계획법(dynamic programing)은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.

사실 동적 프로그래밍이라는 명칭과 실제 의미가 별로 연관성이 없어 보인다. 특히 프로그래밍과는 그닥 어울리지 않는데,
공군 소속의 회사에 근무하던 벨만은 당시 연구를 하는 것을 극도로 싫어하던 국방 위원장 윌슨의 눈을 피해
문제 풀이의 절차를 프로세스(process) 대신 (programming)으로 숨겨서 표기했다고 한다. 이 프로세스가 다단계로 이루어져있고, 동적이기 때문에 동적 계획법 (Dynamic Programming)으로 명칭하게 된 것이다.

사실 작은 문제를 나눈다는 것은 분할정복(Divide and Conquer)와 비슷하다고 생각 할 수 있다. 여기서 두 방법 모두 큰 문제를 작게 나누어서 해결하는 점은 동일히지만, 동적 계획법은 같은 문제가 반복된다는 점이 다르다. 여기서 동적 계획법의 핵시민 메모이제이션이 등장한다.

메모이제이션은 작은 문제가 똑같이 반복되는 동적 계획법에서, 작은 문제의 결과값을 한군데 저장해놓고, 다시 사용하는 방법이다.
위의 피보나치 문제(사진)에서 예를 들면, f(n)이 f(n-1) 과 f(n-2)를 호출하고, f(n-1)은 f(n-2)와 f(n-3)을, f(n-2)는 f(n-3)과 f(n-4)를 호출하는데,
여기서 f(n)과 f(n-1)을 제외하고는 나머지 연산들은 반복되어 등장함을 알 수 있다. 이 결과값들은 저장해두었다가 다시 사용함으로써 동적 계획법은 시간복잡도를 확실하게 줄일 수 있다.

동적 프로그래밍 전략

사실 나도 동적 프로그래밍을 어떻게 써먹어야 할 지 처음에는 감이 잘 오지않았다. (물론 지금도 오지 않는다.)
그러다 참고하게 된 "알고리즘 문제해결전략"에서의 동적 프로그래밍 레시피는 아래와 같다.

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

또한 문제를 푸는 방법을 두가지로 나눌 수 있다. Top-down과 Bottom-up 방식이다.
Top-down 방식은 가장 큰 문제에서 작은 문제를 호출해서 풀어내는 방식이다. 주로 재귀호출을 사용한다.

//Top-down 방식의 피보나치 수열
public void Fibonacci(int n){
    if(n == 0) return 0;
    if(n == 1) return 1;
    
    if(cache[n] != 1) return cache[n];
    cache[n] = Fibonacci(n-1) - Fibonacci(n-2); 
}

Bottom-up 방식은 작은 문제부터 답을 구해가서 전체 문제의 답을 찾는 방식이다.

//Bottom-up 방식의 피보나치 수열
public void Fibonacci(int n){
    cache[0] = 0; cache[1] = 1;
    for(int i=2 i<=n; i++){
        cache[i] = cache[i-1] + cache[i-2]
    }
    
    if(cache[n] != 1) return cache[n];
    cache[n] = Fibonacci(n-1) - Fibonacci(n-2); 
}

보통 Top-down은 문제를 풀때 점화식에서 유추해내기 쉽지만 재귀를 사용해 깊이가 깊어지면 에러가 발생할 수 있다.
Bottom-up은 반복문 등의 간단한 식을 사용해 시간과 메모리를 줄일 수 있지만, 생각해내기 어려울 수 있다. 
어느 방법을 사용하던, 단순히 완전탐색보단 적절하게 메모이제이션을 활용해 동적으로 풀어나가는게 알고리즘 풀이에서 중요한 부분이라고 생각한다.