분할 정복과 동적 계획법을 이용한 기초 프로그래밍

올해 정보올림피아드 부터는 본선 진출을 위해서는 기본적인 알고리즘을 익히고 어떤 문제가 주어졌을때 그것을 프로그래밍으로 구현을 할 수 있는 능력이 있어야 할것 같습니다.

기출문제 유형의 1,2번 문제 유형이 나온다고 하니 수학만 잘하는 학생이 급하게 C언어 문법을 익히고 문제를 해결함으로 본선에 진출했던 작년과 같은 경우와는 접근 방식을 다르게 접근해야 할것 같네요.

일단 초등부 1,2번 문제는 기본적인 문법과 실생활에서 어떤 규칙을 찾아서 접근한다면 충분히 해결 할 수도 있을것으로 판단이 됩니다.

하지만 중등부 1번 문제 까지는 어느정도의 문법과 문제에서 어떤 것을 요구하는지를 찾아 낸다면 해결이 가능 할 수 있겠지만 2번 유형은 아무래도 어느 정도 알고리즘을 접한 학생이 유리 할 수 밖에 없을것 같네요.

오늘은 중등부 2,3번 유형에서 자주 출제 되는 분할 정복과 동적계획법을 이용한 기초 프로그래밍에 대해서 알아 보겠습니다.

분할정복은 하향식 접근방법입니다. 상위의 해답을 구하기 위해서 아래로 내려가면서 하위의 해답을 구해 상위로 올라 오면서 그 계산을 합해서 구해 오는 방식입니다. 따라서 이러한 분할정복 알고리즘은 일반적으로 재귀함수로 구현이 됩니다.

반면 동적계획법은 상향식 접근방법입니다. 문제이 경우를 잘게 쪼개서 가장 작은 단위까지 분할 한다는 것은 분할정복과 비슷하지만 가장 작은 경우를 먼저 해결하고 그 결과를 저장 한 후에 그 결과 값을 이용하여 그 다음 문제를 풀어 나가는 방식이 동적계획법입니다. 따라서 동적 계획법은 배열을 주로 이용하게 되는데요.

이러한 배열의 크기 제한에 따라 너무 큰 메모리를 활용하게 되는경우의 제약사항이 따르기도 합니다.

동적계획법은 주로 최적화문제에 활용되는데 알고리즘 설계시 다음의 네단계를 고려하도록 합니다.

1. 최적해의 구조를 특성화 한다.

2. 최적해의 값을 재귀적으로 정의한다.

3. 상향식으로 최적해의 값을 계산한다.

4. 계산된 정보를 이용해 실제 최적해를 구성한다.

예제)

분할정복을 이용한 피보나치 수열 프로그래밍

1,1,2,3,5,8,13...

이와 같은 수열의 특징은 현재 항은 전항 과 전전항의 합으로 이루어진 수열입니다.

이러한 수열을 피보나치 수열이라고 하는데...

n번째 항의 값이 무엇인지 확인하려고 할때 분할정복을 이용하면 다음과 같이 나타낼수 있습니다.

f(n) = f(n-1) + f(n-2)

즉 f(n)을 구하기 위해서는 f(n-1) 과 f(n-2) 로 분할을 해야 합니다.

또한

f(1)=1,f(2)=1 이라는 바닥이 존재 해야 됩니다.

이렇게 분할해서 f(n) 에서 n <=2 일 경우 바닥 조건을 만나서 빠져 나오면서 f(n-1) + f(n-2) 와 같이 두 값을 합하여 계산하면서 빠져 나오게 됩니다.

이것을 프로그래밍으로 표현하면 다음과 같습니다.

int f(int n)

{

   if(n<=2) return 1;

   return f(n-1) + f(n-2);

}

이러한 규칙을 찾아서 수학적으로 규칙을 찾아 낸다면 그것을 재귀함수로 구현하는 것은 무척이나 간단해 보입니다.

하지만 이 재귀함수는 단점이 존재 하는데 f(5) 를 계산 하기 위해서 f(4) + f(3) 인데 여기서 f(3)을 계산하는데 f(4)를 계산하기 위해서 또 한번 f(3) + f(2) 이기 때문에 f(3)의 값을 다시 한번 계산한다는 부분에서 계속해서 중복해서 계산을 한다는 부분이 존재 하는 단점이 있습니다.

하지만 이 문제를 다음과 같이 동적계획법으로 구현을 한다고 하면 n항의 값을 구하기 위해서 중복 계산이 없으므로 단 n회만 반복해서 구할 수 있다는 부분이 있습니다.

동적계획법을 이용한 피보나치 수열 프로그래밍

피보나치 수열을 동적계획법으로 접근해 보면 테이블 안에 모든 부분의 최적값 을 저장 한 후 그 값을 이용하여 다음 항의 최적값을 구하여 마지막 까지 계산하여 테이블을 완성하는 상향식 방법을 사용하게 됩니다.  

즉 f라는 배열을 만들어서 f[1]=1,f[2]=1 을 미리 저장해 놓는다면

f[i] = f[i-2]+f[i-1] 과 같이 계산해서 나가면 n항의 값을 계산하기 위해서는 i는 3부터 n까지만 반복하면 되는 것입니다.

이것을 구현한 프로그래밍 예제는 다음과 같습니다.

int f(int n)

{

     int *f;

    f= new int[n+1]; //n+1개의 배열을 할당

   f[1]=1;

   f[2]=1;

   for(int i=3;i<=n;i++) f[i]=f[i-2] + f[i-1];

   return f[n];

}

이러한 동적계획법은 데이터양이 일정양이 되는 동안만 계산이 가능한데요.

일반적으로 메모리를 할당 할 수 있는 양이 대략 1000만개 정도 잡을 수 있기에 이것보다 더 큰 계산을 하기 위해서는 새로운 알고리즘을 고안해야 합니다.

피보나치 수열과 같은 경우에는 큰 수열을 계산하기 위해서는 단위 행렬의 곱을 이용해서 계산하는 방법이 있는데요.

단위 행렬이 n 승의 (1,1) 위치의 값이 n항의 값과 일치 한다는 규칙을 이용해서 행렬의 곱을 계산하는 방식이 사용되기도 하는데요.

이처럼 알고리즘 세계에서는 아직까지 해결 되지 않은 문제들이 많이 쌓여 있습니다.

우리 학생들이 열심히 이 세계를 파고 든다면 아직 해결되지 않은 문제들을 새로운 규칙을 이용하여 해결해 나간다면 새로운 세계를 열어 나갈것이라 생각하네요.

꼭 정보올림피아드를 준비하는 학생이 아니라도 알고리즘 세계에 빠져 든다면 신기한 세상을 많이 경험하게 될것이라고 말씀드리고 싶네요.^^