1. (Hashing)이란 무엇인가?

 

 

- 해싱(hashing)이란 한마디로 말해서 많은 양의 데이터(data)들을 그보다는 작은 크기의 테이블(table)로 대응

(mapping)시켜 저장할 수 있도록 하는 일종의 데이터 관리 기법이다. 데이터들을 저장하거나 찾을 때 인덱스

(index)라는 또다른 데이터 스트럭쳐(data structure)를 이용하는 대신, 각 데이터들이 테이블의 어느 영역에 위

치할 것인가를 결정해주는 해쉬함수(hash function)를 사용하여 일정한 시간 내에 데이터들을 효과적으로 찾을

수 있도록 해주는 것이 바로 해싱이다. 따라서 데이터들은 순차적으로 저장되는 것이 아니라 테이블 전 영역에

걸쳐서 고루 분포하게 되며, 저장된 데이터를 찾을 때에도 해쉬함수를 사용하면 곧바로 그 위치를 알 수가 있

기 때문에 빠르게 데이터를 검색할 수가 있게 된다.

그러나 해싱은 그 기본 개념으로 인하여 매우 치명적인 약점을 지니고 있는데, 해쉬함수가 이상적(ideal)이지

않은 이상 서로 다른 키(key)들이 테이블의 같은 위치로 결정될 소지가 다분하다는 것이 바로 그것이다. 이런

현상을 충돌(collision)이라 하며, 따라서 해싱에서는 이 충돌을 어떻게 해결할 것인가가 매우 커다란 이슈

(issue)가 된다. 결국 해싱 알고리즘(hashing algorithm)은 해쉬함수와 충돌해결전략(collision resolution

strategy)으로 나뉘게 된다.

=========================================================================================

 

 

 

2. Hashing Algorithm

 

- 해싱 알고리즘(hashing algorithm)은 해싱을 위한 구현 부분으로, 다음과 같이 크게 세 가지로 구분할 수가 있다.

2.1. 완전 해싱 (Perfect Hashing)

- 완전 해싱은 나중에 좋은 해싱 기법으로 언급될 simple uniform 해싱을 의미한다. 즉 서로 다른 키(key)값이 해싱에 의해 주소값을 할당받을 때, 주소값이 절대로 겹치지 않는 이상적인 해싱을 의미한다. 물론 이런 방식은 일대일대응 이외에는 존재하지 않는 방식으로 이상적인 것이다.

2.2. 정형 해싱 (Conventional Hashing)

- 데이타 개수를 이미 알고 있어서, 데이타들이 저장될 주소 범위를 미리 데이타 개수만큼 지정해 두는 방식을 의미한다. 즉, 필요한 메모리의 크기는 미리 측정되고 미리 할당받아야 한다.

2.3. 동적 해싱 (Dynamic Hashing)

- 정형 해싱의 문제점은 데이타를 입력하기 이전에 데이타 개수에 대한 정보가 있어서 메모리를 미리 할당받아야 한다는 점이다. 일반적으로 시간이 지남에 따라서 데이터의 양의 증가하게 되므로 잘못된 측정으로 데이터가 메모리의 범위를 넘게 되면, 더 큰 메모리 크기를 잡고 다시 해싱을 해야 하는 시간적, 자원적 낭비가 일어나게 된다. 동적 해싱은 이러한 데이터의 증감에 적응하기 위해서 나타난 것으로, 동적으로 메모리의 크기를 변화시키는 해싱 기법을 의미한다.

=========================================================================================

 

 

3. Hash Function

 

- 해싱 알고리즘을 해쉬 함수라고 부른다. 해싱 함수(hashing function) h(k)는 어떤 키 k에 대한 테이블 주소(table address)를 계산하기 위한 방법으로, 주어진 키 값으로부터 레코드가 저장되어 있는 주소를 산출해 낼 수 있는 수식을 말한다.

해싱은 빠른 속도의 데이터 검색 외에도, 전자서명을 암호화하고 복호화 하는 데에도 사용된다. 전자서명은 해쉬 함수를 이용하여 변환된 다음, 해쉬 값(이를 요약 메시지라고 부른다)과 전자서명이 별도로 전송된다. 수신자는 송신자가 사용한 해쉬함수와 같은 것을 사용하여, 서명으로부터 요약 메시지를 뽑아내어 그것을 이미 수신한 요약 메시지와 비교한다. 그 비교 결과는 같아야만 전자서명이 유효한 것이다.

해쉬 함수는 원래의 값이나 키를 색인하는데 사용되며, 그값이 관련된 데이터가 검색될 때마다 다시 사용된다. 그러나, 해싱은 항상 한 쪽 방향으로만 연산된다. 따라서, 해쉬된 값을 분석함으로써 해쉬 함수를 추출해내는 역방향 공학은 필요가 없다. 사실, 이상적인 해쉬함수는 그러한 분석에 의해 추론할 수 없어야 한다. 또한, 우수한 해쉬 함수는 서로 다른 두 개의 입력에 대해, 동일한 해쉬 값을 생산해서는 안된다. 만약 그렇게 되면, 충돌이 생긴다. 충돌 위험성이 매우 적은 해쉬 함수라야 훌륭한 해쉬 함수로 평가된다.

데이터베이스 저장이나 검색에 잘 적용되는 해쉬 함수는 오히려 암호화나 에러검출 목적으로는 잘 듣지 않을 수도 있다. 암호화에 사용되는 잘 알려진 해쉬 함수들이 몇 개 있다. 이러한 것들에는 전자서명을 요약 메시지라고 불리는 더 짧은 값으로 바꾸는 데 사용되는 요약 메시지 해쉬 함수 MD2, MD4, MD5 등과, 더 큰 요약 메시지 (60 비트)를 만드는 표준 알고리즘인SHA (Secure Hash Algorithm) 등이 포함된다.

 

 

저작자 표시 비영리 동일 조건 변경 허락
신고

'Computer Science > Algorithm' 카테고리의 다른 글

Hashing 이란?  (0) 2012.04.09
알고리즘 강좌 7회  (0) 2010.11.28
알고리즘 강좌 6회  (0) 2010.11.28
알고리즘 강좌 5회  (0) 2010.11.27
알고리즘 강좌 4회  (0) 2010.11.27
알고리즘 강좌 3회  (2) 2010.11.27

  

백 트래킹

 

백 트래킹(Backtracking : 되추적)의 개념부터 살펴보자.

백트래킹을 한마디로 말하자면... “몽땅 다 찾아본다” 라는 말로 요약이 가능하다. 여기다 살을 조금 붙이면 “답에 될 수 있는 것을 몽땅 다 찾아본다” 라는 말로 확장할 수 있다. 백트래킹의 개념은 이 말 그대로다. 답이 될 만한 것들을 모두 다 뒤져봐서 그 중에서 답을 찾는 알고리즘이 바로 백트래킹이다.

 

이러한 백트래킹은 몇가지 특징을 가진다.

1. 함수의 재귀호출을 이용해 구현한다.

2. 모든 가능성을 몽땅 뒤져보는 것이기 때문에, 대체로 수행하는데 시간이 오래 걸린다.

3. 모든 가능성을 몽땅 뒤져보는 것이기 때문에, 백트래킹으로 풀 수 없는 문제는 별로 없다.


이 특징들을 대충 살펴보자.

1번에 나온 것처럼 백트래킹은 재귀호출을 이용해 구현하는 경우가 대부분이다. 이것은 재귀호출이 백트래킹을 구현하기에 매우 편리하기 때문이다. 또한 2번 특징의 경우 너무나 당연한 결과라고 할 수 있겠다. 어떤 문제든, 보통 답이 될 수 있는 후보(이걸 후보해라고도 한다)는 굉장히 많다. 백트래킹은 이걸 모두 뒤져보기 때문에, 다른 알고리즘에 비해 수행시간이 오래 걸릴 수밖에 없다. 일반적으로 어떤 문제의 후보해는 문제의 크기(n)에 비례한다.

3번 특징이 많은 사람들이 백트래킹을 쓰는 가장 큰 이유이다. 거의 모든 문제가 백트래킹으로 풀린다고 봐도 무방할 정도이다. 이런 특징 때문에 각종 컴퓨터 경시대회 시험장에서 툭하면 쓰이는 게 백트래킹이다.(필자도 시험장에서 문제를 받아 들었을 때 모르겠다 싶으면 무조건 백트래킹 돌렸다--;) 하지만 백트래킹을 써야만 풀리는 문제들도 많이 있다. 다음 절부터는 이런 문제들을 중심으로 백트래킹을 설명해 나갈 것이다.

[미로탐색문제]

 한번쯤은 해보았을만한 미로 탐색문제이다.

0은 이동이 가능한 길이고 1은 벽이다.

대각선으로는 이동이 불가능하다.

0

0

1

1

0

 

0

0

1

1

0

1

0

0

0

0

 

1

0

0

0

0

1

0

1

0

1

 

1

0

1

0

1

0

0

0

1

0

 

0

0

0

1

0

0

1

0

0

0

 

0

1

0

0

0

 

0,0은 시작점이고 4,4는 도착지점이 된다. 0,0에서부터 출발하여 4,4까지 도달할 수 있는 모든 가지 수를 출력하는 프로그램을 작성하여라.

위와 같이 한 가지 길만이 존재한다.

DFS 탐색으로 0,0에서부터 4,4까지 모든 점을 탐색하여본다.

DFS 탐색이란 깊이우선탐색이라고 부르며 4방향을 검사하여 진행할 수 있다면 계속하여 진행하는 방식을 의미한다. 위의 그림에서 보면 0,0에서 진행할 수 있는 방향을 검사해보면 오른쪽이 나온다.

그럼 오른쪽으로 이동 후에 다시 이동할 수 있는 길을 보면 아래쪽만이 존재한다. 그럼 아래쪽으로 진행 후에 살펴보면 오른쪽과 아래쪽이 있다. 기본적으로 오른쪽, 아래, 왼쪽, 위 순서로 검사를 한다면 오른쪽으로 이동할 것이다. 그럼 계속해서 진행하면 1,4의 좌표에서 위쪽으로 진행이 가능하므로 위로 올라가게 된다. 위쪽에서는 더 이상 진행이 불가능하므로 갈림길이 생겼던 1,3으로 이동하게 된다. 여기서 아래쪽으로 이동하게 되면 더 이상 진행이 불가능하므로 1,1의 갈림길로 이동하게 된다. 다시 아래쪽으로 계속하여 진행하면 1,3의 지점에서 오른쪽으로 진행(왼쪽으로 진행하지 않는 이유는 검색방향이 오른쪽, 아래, 왼쪽, 위 순서대로 빽트래킹으로 검색을 하기 때문이다. 계속해서 진행하면 마지막 좌표까지 가게 된다. 이때 프로그램이 종료되면 안 되고 다른 곳으로도 이동이 가능한지 검사해야 된다.

 

<입력값>

<출력값>

5

0 0 1 1 0

1 0 0 0 0

1 0 1 0 1

0 0 0 1 0

0 1 0 0 0

1

 

 

<프로그램소스>

#include <stdio.h>

 

int n;

int map[4][4];

int cnt;

 

void input()

{

int i,j;

FILE *in;

in=fopen("input.txt","r");

fscanf(in,"%d\n",&n);

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

fscanf(in,"%d",&map[i][j]);

}

}

}

 

int back(int i,int j)

{

if(map[i][j]!=0 || i>=n || j>=n || i<0 || j<0) return 0;

map[i][j]=2;

if(i==n-1 && j==n-1)

{

cnt++;

map[i][j]=0;

return 0;

}

back(i,j+1);

back(i+1,j);

back(i-1,j);

back(i,j-1);

map[i][j]=0;

}

 

void main()

{

input();

back(0,0);

if(cnt!=0) printf("%d\n",cnt);

}

저작자 표시 비영리 동일 조건 변경 허락
신고

'Computer Science > Algorithm' 카테고리의 다른 글

Hashing 이란?  (0) 2012.04.09
알고리즘 강좌 7회  (0) 2010.11.28
알고리즘 강좌 6회  (0) 2010.11.28
알고리즘 강좌 5회  (0) 2010.11.27
알고리즘 강좌 4회  (0) 2010.11.27
알고리즘 강좌 3회  (2) 2010.11.27

- 그리디 #2 -

 

 

5. 그리디의 실제 #3

이번에도 그리디를 이용해서 효과적으로 풀 수 있는 문제를 알아보자.

그래프 G가 있을때, 한 정점에서 다른 모든 정점으로 가는 경로를 구하는 알고리즘을 아는가? 이것은 Dijkstra(다익스트라)라고들 부르는 방법이다. 이 알고리즘은 그래프가 있을때 두 정점사이의 최단거리를 구할때 꽤나 유용하다.

서론은 이 정도로 하고, 본격적으로 이 알고리즘을 알아보자.

다익스트라 알고리즘은 지난회에서 배웠던 MST와 좀 비슷하다. 다음과 같은 그래프(저번에 나왔던)을 보자.

 

A에서 다른 정점으로 가는 최단 경로들을 구해보자.

일단 A를 선택한다. 그리고 A를 집합 Y에 넣는다.

그다음 A에서 가장 가까운 정점 B를 선택하고, B를 집합 Y에 넣는다. 그러면 Y = {A, B}다.

 

그리고 이제부터는 A에서 집합 Y의 부분인 정점을 거쳐서 갈 수 있는 가장 가까운 정점을 잡으면 된다. 즉 이때는 C를 선택하는데, A에서 Y의 부분을 거치는(Y의 부분집합중에는 공집합도 들어감을 주의하라! A에서 바로 갈 수도 있다.) 가까운 C정점을 선택한다. 그러면 Y = {A, B, C}가 된다.

같은 과정을 반복한다. 다음에는 A에서 출발해 Y의 부분인 C정점을 지나 E로 가는 것이 거리 5로 최소경로이므로 E를 선택하면 된다. Y = {A, B, C, E}이다. 이제는 D로 가는게 최단 경로(거리는 7) 이므로 Y= {A, B, C, E, D}이다. 모든 경로까지의 거리를 계산했으므로 알고리즘은 여기서 끝.

각각의 과정에서 경로의 거리를 저장해 두면 알고리즘이 끝난 후 A에서 각 정점까지의 최단경로를 모조리 구할 수 있다.

 

역시 소스를 보면 이해가 쉬울 것이다.

program ____Dijkstra____;

const

n=5;{정점의 개수}

start = 1;{출발하는 정점}

 

{그래프의 상태에 대한 데이터.

D[i,j]<>0 이면 정점i와 정점j간의 거리는 D[i,j]이고,

D[i,j]=0 이면 정점i와 정점j을 연결하는 이음선이 없다는 뜻}

D : array[1..n,1..n] of integer =(

(0,1,3,0,0),

(1,0,3,6,0),

(3,3,0,4,2),

(0,6,4,0,5),

(0,0,2,5,0)

);

 

var

i, j : integer;

min,minp : integer;

L : array[1..n] of integer;{출발하는 정점으로부터 i정점까지의 거리}

Y : array[1..n] of boolean;{집합 Y. 정점 i가 Y에 속하면 Y[i]=true}

 

begin

for i:=1 to n do

if D[start,i]<>0 then L[i]:=D[start,i] else L[i]:=maxint;

L[start]:=0;

Y[start]:=true;{출발정점을 Y에 넣는다}

 

for i:=1 to n do begin

 

min:=maxint;

for j:=1 to n do begin

if (min>L[j]) and (Y[j]=false) and (L[j]<>0) then begin

min:=L[j];

minp:=j;

end;

end;

 

if min=maxint then begin

{중간에 더 연결할 정점이 없다면 그래프가 중간에 끊긴경우}

writeln('Unconnected!');

exit;

end;

 

Y[minp] :=true;{minp정점을 Y에 추가}

for j:=1 to n do begin

{minp정점을 거쳐 갈 수 있는 정점까지의 경로를 저장}

if (D[minp,j]<>0) and (L[j] > L[minp] + D[minp,j]) then

L[j]:=L[minp] + D[minp,j];

end;

 

end;

 

end.

 

위에서 설명한것과는 약간 다르다. 설명한 그대로 코딩을 하면 상당히 복잡해진다-_-; 그래서 그런것이니 이해해 달라.(설명한 그대로 하면 시간복잡도가 늘어나서 O(n^3)이 되버린다)

 

 

5. 정리

대강 엉성하게 나마 그리디 알고리즘에 대해 알아보았다. 그리디 알고리즘은 간단한 만큼 그 쓰임이 아주 많지는 않다. 하지만 위와 같은 문제들에 대해서는 아주 쓸만하고 간단한데다 속도도 빠르다. 게다가 조금 응용하면 근사해를 구하는 문제에도 적용해서 좋은 결과를 얻어낼 수 있다. 그리디를 잘 알아두면 여러가지로 쓸모가 많을 것이다. 다만 항상 주의할 것은, 그리디로 풀어서 만들어낸 해가 항상 전체의 최적해인지 생각해 보아야 하는 것이다.

 

저작자 표시 비영리 동일 조건 변경 허락
신고

'Computer Science > Algorithm' 카테고리의 다른 글

Hashing 이란?  (0) 2012.04.09
알고리즘 강좌 7회  (0) 2010.11.28
알고리즘 강좌 6회  (0) 2010.11.28
알고리즘 강좌 5회  (0) 2010.11.27
알고리즘 강좌 4회  (0) 2010.11.27
알고리즘 강좌 3회  (2) 2010.11.27

- 그리디 #1 -

 

 

1. 그리디(Greedy)란?

 

이번에 우리가 공부해 볼 알고리즘은 그리디(Greedy)이다.

간단히 그리디에 대해 알아보면, 어원 그대로 상당히 탐욕적임을 느낄 수 있을 것이다. 그리디 알고리즘의 핵심은, 몇번의 선택을 하면서 답을 찾아내는데, 그 선택은 전에 결정했거나 앞으로 결정할 선택을 고려하지 않고, 그 당시의 상황에서만 가장 최적인 해를 취하는 것을 의미한다. 이런 과정을 거치기 때문에 그리디 알고리즘은 또 다른 중요한 특징을 가진다. 각 선택들은 부분적으로는 최적일지 모르나 전체적으로 보면 최적이 아닐 수도 있다는 점이다. 그래서 그리디 알고리즘을 쓸 때는 ‘전체적으로도 최적이 되는가?’ 라고 한 번 다시 생각해 봐야한다.

...이렇게 말해놓으면 무슨 소린지 잘 모르는 사람도 많을 것 같다. 다음 장에서 실제 문제에 적용시키면서 공부해 보면 이해가 잘 될 것이다.

 

2. 그리디의 실제#1

 

그리디의 간단한 예를 살펴보도록 하자.

동섭이는 모 슈퍼마켓의 점원으로 아르바이트를 하게 되었다. 계산대에 서서 손님들이 물건을 사면 돈을 받고 거스름돈을 주는 게 동섭이의 일이다. 그런데 너무나 당연한 소리지만, 거스름돈은 돈의 개수를 최소한 적게 해서 주는 것이 좋다. 즉, 거스름돈으로 2250원을 주어야 한다면, 천원짜리 두 장, 백원짜리 두 개, 오십원짜리 한 개 이렇게 총 다섯개로 최대한 줄여서 줘야지, 십원짜리 동전 225개를 확 던져주면 안된다는 소리다.

이 문제는 그리디 알고리즘으로 해결 할 수 있다.

우선 가장 단위가 큰 화폐를 선택한다. 그리고 이렇게 선택한 화폐가 손님한테 줘야할 거스름돈보다 크면 두번째로 단위가 큰 화폐를 선택한다.(거스름돈이 2250원인데 만원짜리 지폐를 거스름돈으로 줄 수는 없는 노릇 아닌가!) 이런식으로 더 줘야할 거스름돈보다 크지 않은 화폐를 선택한다. 이러한 과정을 손님한테 줘야할 거스름돈이 더 없을때 까지 계속한다.

이러한 일련의 과정을 이해하는 것은 별로 어렵지 않을 것이다.(나중에 보면 알겠지만 그리디 알고리즘을 적용하는 문제들은 대부분 “쉽다”.) 이 소스도 역시 쉽다.

 

program ____charge____;

const

money : array[1..5] of integer = (1000,500,100,50,10);

var

result : array[1..5] of integer;

charge : integer;

i : integer;

begin

charge:=2250;{주어야 할 거스름 돈}

 

repeat

for i:=1 to 5 do begin

if charge>=money[i] then break;

end;

 

inc(result[i]);

dec(charge,money[i]);

until charge=0;

 

for i:=1 to 5 do begin

writeln(money[i]:4,'원 짜리 ',result[i],'개');

end;

end.

 

여기는 워낙 쉬워서 별로 설명할 건덕지도 없다.

 

3. 주의할 점

 

앞에서 한 번 말했던 바와 같이, 그리디 알고리즘은 부분적으로는 최적의 해를 가져다 줄 지 모르나 전체적으로도 항상 최적의 해를 가져다 주지는 못할 수도 있다. 위의 거스름돈 주기 문제를 생각해 보자.

위 문제의 상황을 조금 바꿔서, 한국은행에서 새로운 1100원 짜리 화폐를 만들었다고 가정해보자. 그리고 주어야 할 거스름돈을 2600원이라고 하자. 이 때 위의 방법으로 거스름돈을 준다면? 1100원 짜리 2장 + 100원 짜리 4개 = 총 화폐 6개. 하지만 이건 아시다시피 최적해가 아니다. 가장 화폐의 수가 적은 경우는 1000원 짜리 2장 + 500원 짜리 1개 + 100원 짜리 1개 = 총 화폐 4개이다. 그리디 알고리즘의 맹점을 단적으로 보여주는 예다. 그리디 알고리즘을 쓸 때는 항상 전체적으로도 최적의 해가 나오는지를 꼭 생각해 봐야 한다.

 

4. 그리디의 실제 #2

 

최소비용 신장 트리(Minimum Spanning Tree)에 대해서 아는가? 여기서는 최소비용 신장트리(이하 MST)를 구하는 그리디 알고리즘을 설명하겠다.

MST를 간단히 정의하면 “그래프 상의 모든 정점을 연결하는 가장 짧은 이음선들의 집합”이라고 말할 수 있다. 다음 그림을 보자.

 

이것도 그림이냐! 라고 하시는 분이 혹시 있을지 모르겠다. 미안타.-_-; 나한테 그림에 관해서는 시비를 걸지 말아달라-_-;;

그림 2를 보면, 그래프 G의 모든 정점(A,B,C,D,E)를 모두 연결할 수 있으면서 그 길이의 합이 최소(1+3+4+2=10)인 선들이 굵은 선으로 나타나 있다. 그림 2의 굵은 선과 같은 선들의 집합을 MST라고 하는 것이다. (MST에 대해 더 자세한 것은 앞으로 올라올 초급 알고리즘 강좌를 참고하시길.)

그래프 G가 주어질 때 MST를 찾는 알고리즘은 크게 두가지가 있는데, Prim의 알고리즘과 Kruskal의 알고리즘이 그것이다. 두 알고리즘 모두 그리디를 응용한 것인데, 여기서는 이해하기 쉬운 Prim의 알고리즘을 공부해보자.

 

위 그림을 예로 들어 설명하겠다. 우선 그래프상의 점을 아무거나 하나 잡는다. 편의상 A로 잡아본다. 그리고 이렇게 잡아서 MST를 만들게 될 정점들을 {}로 묶어서 표시해 보자. 우선 A를 잡았으므로 {A} 이다.

그 다음, {}에 속하는 정점들 중에서 가장 가까운 정점을 또 선택한다. A와 가장 가까운 곳은 거리가 1인 B이다. 그러면 선택한 정점이 하나 늘어나서 {A,B}가 된다.

이제 {}에 속하는 정점에서 가장 가까운 정점을 선택하는 과정을 반복하면 된다. {A,B}에서 가장 가까운 곳은 거리가 1인 C이다. {A,B,C}까지 선택되었다.

{A,B,C}에서 가장 가까운 정점은 거리가 2인 E이다. {A,B,C,E}가 되었다. 마지막으로 {A,B,C,E}와 가장 가까운 정점은 거리가 4인 D이다. {A,B,C,E,D}가 되어 모든 정점이 연결되었으므로 MST는 완성이다.

아래 소스는 위 과정을 그대로 코딩한 것이다. 여기서 출력은 MST의 길이이다.

 

program __Mininum_Spanning_Tree__;

const

n=5;{정점의 개수}

 

{그래프의 상태에 대한 데이터.

D[i,j]<>0 이면 정점i와 정점j간의 거리는 D[i,j]이고,

D[i,j]=0 이면 정점i와 정점j을 연결하는 이음선이 없다는 뜻}

D : array[1..n,1..n] of integer =(

(0,1,3,0,0),

(1,0,3,6,0),

(3,3,0,4,2),

(0,6,4,0,5),

(0,0,2,5,0)

);

 

var

tree,selected : array[1..n] of integer;

i,j,k : integer;

min,edge : integer;

sum : integer;

begin

tree[1]:=1;{정점A를 선택}

selected[1]:=1;

 

for i:=2 to n do begin

 

min:=maxint;

for j:=1 to i-1 do begin

for k:=1 to n do begin

if (D[tree[j],k]<min) and (D[tree[j],k]<>0)

and (selected[k]=0) then begin

{가장 가까운 선택되지 않은 정점을 찾는다}

min:=D[tree[j],k];

edge:=k;

end;

end;

end;

 

inc(sum,min);

tree[i]:=edge;{정점 추가}

selected[tree[i]]:=1;

 

end;

 

writeln(sum);

 

end.

 

실제로 Prim의 알고리즘은 시간복잡도가 n2이지만 여기서는 이해를 편하게 할 목적으로 조금 풀어서 코딩했기때문에 n3이 되고 말았다(-_-;;)

저작자 표시 비영리 동일 조건 변경 허락
신고

'Computer Science > Algorithm' 카테고리의 다른 글

알고리즘 강좌 7회  (0) 2010.11.28
알고리즘 강좌 6회  (0) 2010.11.28
알고리즘 강좌 5회  (0) 2010.11.27
알고리즘 강좌 4회  (0) 2010.11.27
알고리즘 강좌 3회  (2) 2010.11.27
알고리즘 강좌 2회  (2) 2010.11.27

- 다이나믹 #3 -

 

7. 연습문제 풀이

 

자, 지난번 강좌에 나왔던 연습문제는 푸셨는가?

그럼 풀이법에 대해 설명하도록 하겠다.

이 문제도 동적계획법으로 풀린다.(당연하지.. 동적계획법 강좌에 나온 문젠데) 풀이법은 1차원 Up sequence문제와 별로 다를 것이 없다. 우선 이차원 배열 L(2차원 버젼이므로)을 다음과 같이 잡는다.

 

L[i , j] = i행 j열에 있는 숫자로 끝나는 오름차순 수열의 최대길이

 

1차원 버젼과 별로 다르지 않다.

그럼 점화식은?

 

L[i , j] = 1

L[i , j] = maximum( L[k1 , k2] + 1 )

 

역시 1차원 버젼과 다를것은 별로 없다.(음.. 그러고 보니 "다를것이 없다"라는 말을 지난 강좌에서부터 너무 많이 쓰고 있는 듯..-_-) 그 전까지의 최대길이에 조건을 만족할 경우 +1해주면 되는 것이다.

그럼 소스를 보자.

 

program Upsequence_2D;

const

n=5;

data : array[1..n,1..n] of integer =(

(1,2,3,4,5),

(8,5,4,10,9),

(7,2,9,3,20),

(21,22,6,19,11),

(10,5,20,12,11)

);

var

L : array[1..n,1..n] of integer;

i,j,k1,k2 : integer;

max : integer;

 

begin

L[1,1]:=1;

for i:=1 to n do begin

for j:=1 to n do begin

if i+j=2 then inc(j);{L[1,1] 은 처리할 필요가 없으므로}

 

for k1:=1 to i do begin

for k2:=1 to j do begin

if (k1=i) and (k2=j) then break;{자기 자신 L[i,j]은 계산에서 제외}

 

if data[i,j]>data[k1,k2] then begin{조건에 맞으면}

if L[i,j]<L[k1,k2]+1 then begin

L[i,j]:=L[k1,k2]+1;{점화식 이용}

end;

end;

 

end;

end;

end;

end;

max:=0;

for i:=1 to n do begin

for j:=1 to n do begin

if max<L[i,j] then

max:=L[i,j];

end;

end;

writeln(max);

end.

 

휴~ 길다. 작성해놓고 보니 1차원 버젼이랑 별다른 차이가 없다.(또...!--;;)

 

8. 추적

추적.. 영어로는 trace라고들 한다.

동적계획법에서는 추적도 상당히 중요한 부분을 차지한다.

지금까지 우리는 '최적해'만을 출력했다. 하지만 실제 문제에서는 그 최적해가 어떻게 해서 구성 되는지도 구해야 할 때가 매우 많다. 예를 들면 Up sequence문제에서 오름차순 수열의 최대길이말고도 최대길이를 갖는 오름차순 자체를 구하라고 요구하는 경우다. 사실 이렇게 답이 어떻게 구성되어 있는지를 구하는 방법은 여러가지가 있다. 하지만 여기서는 필자가 쓰는 방법만 간단히 소개하기로 한다.

동적계획법에서는 최적해를 구성하는 경로가 쭉 이어져서 나오는 경우가 대부분이다. Up sequence같은 경우도 1->3 , 3->9 , 9->13, ... 뭐 이런 식으로 연달아 이어져서 나온다. 문제의 이런 성질을 이용해 경로를 추적할 수 있다.

우선 추적할 경로를 저장하는 배열을 잡아보자.

 

trace : array[1..n] of integer;

 

보통 추적하는 배열은 동적계획법의 최적해가 들어가는 배열과 똑같은 크기로 잡는다.

Up sequence 1차원 버젼에 보면 다음과 같은 부분이 있다.

 

for i:=2 to n do begin

for j:=1 to i-1 do begin

if seq[i]>seq[j] then begin{i항의 숫자가 오름차순 수열이 될수 있다면}

if L[i] < L[j] + 1 then begin

L[i] := L[j] + 1;

...

end;

end;

end;

end;

 

그럼 ...부분에 추적 경로를 집어넣는 명령을 써 주는 것이다. 다음과 같이 써 주면 OK.

 

for i:=2 to n do begin

for j:=1 to i-1 do begin

if seq[i]>seq[j] then begin{i항의 숫자가 오름차순 수열이 될수 있다면}

if L[i] < L[j] + 1 then begin

L[i] := L[j] + 1;

trace[i]:=j;

end;

end;

end;

end;

 

즉 trace[i]에는 최적해 L[i]가 유래한 위치(여기서는 배열의 첨자)를 집어 넣어 주는 것이다. (앞으로 L[i]가 유래한 위치를 고향-_-; 이라고 칭하겠다)

이제 다음과 같은 루틴을 집어넣으면 추적은 완성된다.

 

result : array[1..n] of integer;{최적해의 경로를 최종적으로 저장할 배열}

t,c : integer;

 

c:=0;t:=maxp;{maxp는 배열 중 최적해의 첨자}

repeat

inc(c);

result[c]:=data[t];{경로 저장}

t:=trace[t];{정답의 고향(--;)을 쫓아감}

until t=0;

 

이렇게만 써 놓으면 무슨 소린지 이해가 잘 안갈 것이다. 이것에 대해서 개념적으로 자세히 설명하기는 힘들다. 아래에는 Up sequence 1차원 버젼을 경로 추적까지 해서 수열의 최대길이와 그 수열자체도 출력하도록 해 놓은 소스가 나와있다. 잘 모르겠다면 이 소스를 파스칼 통합환경에서 디버그해서 하나하나 trace해보도록 하자.(그것도 추적이고 이것도 추적이다--;)

 

program Upsequence;

const

n=7;

data : array[1..n] of integer =(

8,13,2,9,4,15,19

);

var

L,trace,result: array[1..n] of integer;

 

i,j : integer;

max,maxp : integer;

begin

L[1]:=1;

for i:=2 to n do begin

for j:=1 to i-1 do begin

if data[j]<data[i] then begin

if L[i]<L[j]+1 then begin

L[i]:=L[j]+1; {점화식 이용}

trace[i]:=j; {L[i]의 값의 고향(?)을 저

장}

end;

end

end;

end;

{최대값 구하기 : 정답 찾기}

max:=-maxint;

for i:=1 to n do

if max<L[i] then begin

max:=L[i];

maxp:=i;

end;

{추적부분}

i:=maxp;j:=0;

repeat

inc(j);

result[j]:=i; {결과 출력용으로 저장}

i:=trace[i]; {정답의 고향(??)을 계속 찾아감}

until i=0;

{출력부분}

writeln(max);

for i:=max downto 1 do

write(data[result[i]],' ');

 

end.

 

이런 정도의 추적만 능숙히 할 수 있으면 실전에서도 상당히 도움이 될 것이다.

9. 정리

 

이상으로 동적계획법에 대해 어느정도 알아보았다. 하지만 지금껏 내가 설명한 것은 'the tip of the iceberg' 즉 빙산의 일각에 지나지 않는다. 보다 중요하것은 실제로 문제를 많이 풀어보는 것이다. 특히 동적계획법 문제는 다른 문제들과 비해서 과연 이게 동적계획법을 이용해서 풀리는 문제인지 구분하기 힘들다. 이런 것을 척 보고 구분할 수 있으려면.. 문제를 많이 풀어보는 수밖에 없다.

부족한점이 많은 강좌였지만 이 강좌를 보고 동적계획법에 대해 약간이라도 이해를 했기를 바란다. 다음회부터는 그리디 알고리즘에 대해 알아도록 하겠다.

저작자 표시 비영리 동일 조건 변경 허락
신고

'Computer Science > Algorithm' 카테고리의 다른 글

알고리즘 강좌 6회  (0) 2010.11.28
알고리즘 강좌 5회  (0) 2010.11.27
알고리즘 강좌 4회  (0) 2010.11.27
알고리즘 강좌 3회  (2) 2010.11.27
알고리즘 강좌 2회  (2) 2010.11.27
알고리즘 강좌 1회  (1) 2010.11.27

다이나믹 #2 -

 

4. 동적계획법의 실제 #3

 

자, 이번에도 역시 문제를 풀어봄으로서 동적계획법을 더 연습해 보자.

이번에 연습해 볼 문제도 역시 너무도 유명한 동적계획법 예제인 Knap sack문제이다. 설마 모르는 분이 있을까봐 문제설명을 드리자면.

소유권 이전 전문가(이하 도둑)가 직업인 동섭이는 어느 날 밤 귀금속 가게를 털었다. 숙련된 솜씨로 문을 따고 가게 안에 들어가 보니 오색찬란 금덩어리 은덩어리 보석덩어리 똥덩어리(엥~ 이건 아닌가) 등등 각종 덩어리들로 눈이 부실 지경이었다. 동섭의 마음 같아서는 몽땅 털어가고 싶지만 자신이 가져온 가방이 그렇게 큰 편이 되지 못했다. 그래서 가장 값을 높게 쳐주는 보석덩어리들만 가져가려고 한다. 동섭이 가장 비싸게 처분할 수 있도록 배낭을 채워주면 된다. 단, 보석덩어리들 마다 각각의 부피와 가격은 다르다. 이 보석가게는 워낙 크기때문에 보석은 제한 없이 얼마든지 가져갈 수 있다고 한다.

대충 이해가 되었을 것이다.

그럼 문제를 풀기 위해 생각해 보자.

일단 여기서는 배낭 전체을 채우는 것을 큰 문제, 배낭 일부를 채우는 것을 부분문제로 생각해 보면 문제 전체가 쉽게 풀린다.(사실 이것이 핵심이다)

그러면 이 문제는 최적화의 원칙이 성립하게 된다. 배낭전체를 채우는 것을 큰 문제, 배낭 일부를 채우는 것을 부분문제로 생각했으므로.

그러면 여기서는 배열을 어떻게 잡아야 할까. 위의 파란색 문장을 바탕으로 생각해보자. 감이 좀 오는가? 여기서 P라는 배열을 한번 정의해 보자.

 

P[i] = 배낭을 처음부터 i 부피만큼만을 채울 때의 얻을 수 있는 최대 값어치

 

그러니까 P[10]에는 10부피를 채우는 가장 값어치가 높게 되도록 보석을 넣었는때의 값어치가 들어갈 것이다.

여기까지 했으면 그 다음 점화식을 세워보자. 역시 저 위에 파란색 글귀를 생각하면 점화식을 만들 수 있을것이다. j번째 보석의 가격을 value[j], 부피를 size[j]라고 하고, 집어넣을 보석이 j번 보석이라고 한다면,

 

P[0] = 0

P[i] = maximum ( P[i - size[j]] + value[j] )

 

여기서 maximum(...)은 괄호 속에 올수 있는 값중 최대값을 나타낸다. 즉 모든 보석을 넣어봤을때의 가장 값어치가 많이 나가는 경우가 P[i]에 저장된다는 말이다.

점화식을 이용하려면 이번에도 역시 배열을 처음부터 차례대로 채워나가야 할 것 같다.

점화식까지 완성이 되었으면 이젠 프로그램을 짤 수 있다.

 

program knapsack;

const

n=5;{보석의 개수}

v=30;{배낭의 크기}

size : array[1..n] of integer =(5,10,20,4,8);{보석 한덩이의 크기}

value : array[1..n] of integer =(50,60,140,30,90);{보석 한덩이의 가치}

var

P : array[0..100] of integer;

i,j : integer;

 

begin

 

P[0]:=0;

for i:=1 to v do begin

for j:=1 to n do begin

if i-size[j]>=0 then begin{j번 보석이 i부피의 배낭에 들어갈 수 있으면}

if P[i] < P[i-size[j]] + value[j] then

P[i]:=P[i-size[j]] + value[j]; {점화식 이용}

end;

end;

end;

 

writeln(P[v]);

 

end.

 

자... 대충은 이해가 가리라고 믿는다. 이번에도 점화식을 그대로 이용했다. 배낭의 크기가 커지면 이 방법은 소용이 없지만 여기서는 동적계획법을 공부하게 위해 배낭의 최대크기를 100으로 잡았다.

5. 동적계획법의 실제 #4

 

한 문제 더 풀어보기로 하자. 이번에 풀 문제는 병신같이 딱히 이름이 없다.(--;) 여기서는 Up sequence문제라고 칭하겠다. 이 문제는 제목에서도 알 수 있듯 수열을 다룬다.

 

8 13 2 9 4 15 19

 

이와같이 별다른 규칙 없이 나가는 길이가 n인 수열이 있다고 한다. 문제는 이 수열에서 뒤로 갈 수록 점점 수가 증가되는(오름차순인) 또 다른 수열의 최대길이를 구하는 것이다. 이 수열에서의 오름차순 수열중 최대길이를 갖는것은

 

8 13 2 9 4 15 19

 

에서 빨간 글씨로 표시된 8,13,15,19 부분이다.(길이는 4) 또는 2,4,15,19의 경우도 길이가 4이므로 최대 길이를 갖는것이 된다. 하지만 13,15,19같은 것은 길이가 모자라므로 답이 될 수 없다.

수열 전체에서 답을 뽑아내는 것을 큰 문제, 수열의 일부에서 답을 뽑아내는 것을 작은 문제로 생각해보자.(이것이 이번 문제의 핵심이다) 그러면 이번에도 최적화의 원칙이 성립해 버리고 만다.

그러면 배열을 어떻게 정의해야 할까. 여기서 구하고자 하는게 수열의 최대 길이니까 아무래도 수열의 최대길이 L을 다음과 같이 정의하는게 좋겠다.

 

L[i] = i항으로 끝나는 오름차순 수열의 최대길이

 

그러니까 L[4]라고 하면 4항으로 끝나는 오름차순 수열의 최대길이이다. 그 숫자는 2가 되겠군.(2,9가 오름차순이므로) 이번에도 차례대로 배열을 채워야 하겠다. 수열의 1항부터 끝항까지 차례대로 오름차순이 되어야 하니까.

이제 점화식을 세울 차례다.

 

L[1] = 1

L[i] = maximum( L[j]+1 )

 

이번엔 점화식이 비교적 간단하다. 즉 수열 길이를 하나씩 증가시켜 가면서 지금까지의 최적해에다 더할 수 있으면 더하는 것이다. 프로그램을 짜 보자.

 

program Up_sequence;

const

n=7;

seq : array[1..n] of integer=(8,13,2,9,4,15,19);

var

L : array[1..100] of integer;

i,j : integer;

max : integer;

 

begin

L[1]:=1;

for i:=2 to n do begin

for j:=1 to i-1 do begin

if seq[i]>seq[j] then begin{i항의 숫자가 오름차순 수열이 될수 있다면}

if L[i] < L[j] + 1 then begin

L[i] := L[j] + 1;{점화식 이용}

end;

end;

end;

end;

 

{최대값 찾기 : 그 이유는 밑에서 설명}

max:=0;

for i:=1 to n do

if max<L[i] then max:=L[i];

 

writeln(max);

 

end.

 

마지막에 배열L의 요소 중에서 최대값을 출력한 것을 눈여겨 보기를 바란다. 오름차순 수열이 몇 항에서 끝날지 모르므로 최대값을 구한 것이다. 이 소스도 위의 Knapsack문제 소스와 구조가 비슷하다.

 

6. 연습문제

 

이제 동적계획법의 기초는 익혔다. 심화학습을 위해 다음 문제를 풀어보자.

이 문제의 풀이는 다음회에 상세히 나올 것이다.

방금 풀었던 Up sequence문제를 기억하시는지? 이번 문제는 아까 푼 그 문제의 2차원 버젼이다. 참고로 이 문제는 정보올림피아드계의 이름난 분 중 한 사람인 한상진 님이 만드셨던 문제이다.(저작권을 보호하자!-_-;;) 여기서의 수열은 가로 n, 세로 n크기의 정사각형으로 주어진다.

 

1 2 3 4 5

8 5 4 10 9

7 2 9 3 20

21 22 6 19 11

10 5 20 12 11

 

여기서도 오름차순 수열을 찾을 수 있다. 단, 이번에 찾을 오름차순 수열의 숫자들은 오른쪽과 아래쪽으로만 가면서 찾아야 한다.(대각선, 그러니까 오른쪽 아래방향으로 갈 수 있다) 이 데이터에서의 답은

 

1 2 3 4 5

8 5 4 10 9

7 2 9 3 20

21 22 6 19 11

10 5 20 12 11

 

빨간색으로 표시된 부분으로 그 길이는 7이다. 1,5,9,19같은 경우도 조건은 만족하나 길이가 딸린다. 이런식으로 주어지는 정사각형 수열에서 가장 길이가 긴 오름차순 수열의 길이를 구하여라. 입력, 출력은 파일로 하든 상수선언을 하든 화면을 이용하든 각자 알아서 하기를 바란다.

저작자 표시 비영리 동일 조건 변경 허락
신고

'Computer Science > Algorithm' 카테고리의 다른 글

알고리즘 강좌 6회  (0) 2010.11.28
알고리즘 강좌 5회  (0) 2010.11.27
알고리즘 강좌 4회  (0) 2010.11.27
알고리즘 강좌 3회  (2) 2010.11.27
알고리즘 강좌 2회  (2) 2010.11.27
알고리즘 강좌 1회  (1) 2010.11.27
  1. 2015.05.20 22:58

    비밀댓글입니다

  2. 스치듯안녕† 2015.06.07 21:48 신고

    p[0]을 0으로 초기값을 두어 순차적으로 계산해서 p[i]값을 찾을 수 있습니다


알고리즘 강좌 2회

- 다이나믹 #1 -

 

1. 동적계획법의 특징

 

다이나믹 프로그래밍(dynamic programming : 이하 동적계획법) 이란 무엇일까. 이 역시 문제를 푸는 알고리즘의 일종이다. 다이나믹의 가장 큰 특징은 이것이다.

 

"작은 문제들을 해결한 다음 이 결과들을 바탕으로 더 큰 문제의 해답을 찾는 방법이다."

 

물론 이 말 한마디만으로 동적계획법에 대해 알수는 없다. 동적계획법의 특징들을 하나씩 살펴보자. 우선, 동적계획법은 작은문제를 먼저 해결하고 그 결과를 저장한 다음, 나중에 그 결과가 필요할때 다시 계산하는 대신 저장된 결과를 이용한다. 탑을 쌓을때 밑둥부터 차근차근 쌓아가는 것 처럼, 그 전의 결과를 바탕으로 새로운 결과를 만들어 낸다. 이를 상향식 접근방법이라고 한다. 나중에 배우게 될 분할정복과는 정 반대의 방법이다.(분할정복은 하향식 방법이라 부른다)

여기서 동적계획법의 특징이 하나 더 생기게 된다. 위의 파란색으로 쓴 문장안에 이런 글귀가 있다.

"그 결과를 저장한 다음..."

작은문제들을 해결해서 얻어낸 결과를 프로그램 상에서는 배열을 선언해서 저장해 두어야 한다는 것이다. 이미 계산해낸 결과들은 다음에 그 결과가 필요할때 그걸 빼서 쓰기만 하면 된다. 이러한 특성때문에 동적계획법에서는 배열을 어떻게 잡는가 하는것도 꽤 중요한 문제이다.

동적계획법의 또 하나의 중요한 특징은 작은 문제의 결과에서 큰 문제의 결과를 끌어내기위한 재귀 관계식(recursive property)을 세워야 한다는 것이다. 이러한 재귀 관계식을 '점화식'이라고 부르기도 한다.(여기서도 그냥 '점화식'이라 칭한다. '재귀 관계식'은 말이 너무 기니까.)

그냥 이론적으로만 주저리 주저리 써 놓았기 때문에 이해가 잘 안 갈 것 같다.(글 쓴 나

도 좀 알아보기가 힘들다-_-a) 다음 절에서 동적계획법을 실제로 써 보기로 하자.

 

2. 동적계획법의 실제 #1

 

우선 너무나도 유명한 동적계획법 예제인 '피보나치 수열의 n항 구하기'를 해보자.

피보나치 수열은 다음과 같이 나가는 수열을 말한다.

1 1 2 3 5 8 13 21 34 .........

이 수열을 자세히 보면 한가지 느끼는 바가 있을 것이다.

"음, 이 수열의 어떤 숫자는 그 숫자 바로 앞에 붙어있는 두 숫자의 합과 같군! 음홧홧홧 난 역시 똑똑해.."

똑똑하신(-_-;;) 여러분이 느낀 그대로다. 이 수열 F의 n번째 숫자 Fn은 그 전에 붙어있는 두 숫자 Fn-1과 Fn-2의 합으로 정해진다. 이것을 좀 수학적으로 나타내 보자.

F1 = 1 , F2 = 1

Fn = Fn-1 + Fn-2 (단, n≥3)

이것이 앞으로 우리가 이용해야 할 '점화식'이다. 사실 이런 류의 동적계획법 문제를 풀 때마다 이렇게 수학적인 식을 써야할 필요는 없다. 대충 '이 결과를 이렇게 더하면 저 결과가 되겠지'라고 머릿속으로 생각해놓고 코딩을 해도 답만 제대로 다온다면야 전혀 상관없다. 여기서는 여러분의 이해를 돕기위해 수학적으로 좀 놀아봤을 뿐이다.(-_-;;;)

그리고 여기서 하나 생각해 봐야 될 것이, 어떻게 답을 구해나갈 것인가 하는 점이다. 동적계획법은 이미 계산된 값을 가지고 그 다음 결과를 계산하기 때문에, 계산된 결과를 어떤 순서로 배열에 채워넣을 것인가 하는 것도 생각해 봐야 한다.

이 문제에서는 그냥 1부터 n까지 순서대로 쭉 구해 나가면 된다. (점화식을 보면 알겠지만 뒤에서부터 계산할 수는 없기 때문이다... 혹시 당신은 뒤에서부터 구하는 법을 알고있나?) 이 정도면 대충 감이 잡혔으리라 믿는다. 그럼 프로그램을 보자.

 

program Fibonacci;

const

n=10;

var

F : array[1..100] of integer;

i : integer;

 

begin

F[1]:=1;F[2]:=1; {점화식 이용}

for i:=3 to n do

F[i]:=F[i-1]+F[i-2]; {점화식 이용}

 

writeln(F[n]); {정답 출력}

end.

 

이 프로그램에서는 아까 잘 만들어 뒀던 점화식을 그대로 사용하고 있는 것을 알 수 있다.

3. 동적계획법의 실제 #2

 

이번에는 다른 문제를 하나 풀어보도록 하자. 이번 예제도 역시 너무 유명하다. '파스칼

의 삼각형 구하기'를 해보자. 혹시 파스칼의 삼각형을 모르는 사람은 있겠지.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

.

.

.

이런 모양의 숫자로 이루어진 삼각형이 다름 아닌 '파스칼의 삼각형'이다. 원래 이 삼각형은 이항정리와 관계있는 경우의 수를 구한 것이다. 하지만 이 이야기는 어려우니까 넘어가고. 우리는 본래의 목적에 충실해보자.

위 삼각형에서도 규칙을 찾을 수 있는가? 찾기 어렵다면 삼각형을 몇대 때려보자.

1 1

1 1 2

1 2 1 3

1 3 3 1 4

1 4 6 4 1 5

.

.

1 2 3 4 5

삼각형을 좀 찌그러지게 해 놓고 보니 규칙성이 보이는 것 같다.

일단 이 삼각형을 배열에 넣었다고 생각해 보자. 옆과 밑에 빨간 글씨로 써 놓은 숫자들은 배열의 첨자를 나타낸다. 배열첨자가 [4,3] 이면 4번째 줄 3번째에 위치한 숫자가 된다고 가정하자. 즉 이 삼각형 T에서 맨 꼭대기에 있는 1은 T[1,1]이고, 제일 밑에서 폼잡고 있는 6은 T[5,3]이 된다. 이렇게 되면 머릿속으로 점화식을 어떻게 세워야 할지 알 수 있을 것이다.

 

T[i,j] = 0 < j < i 일때 T[i,j] = T[i-1,j] + T[i-1,j-1]

j = 0 또는 j = i 일때 T[i,j]=1

 

점화식은 이렇게 만들어질 것이다.

그럼 이 식을 이용해서 배열을 어떻게 채워나가야 할까? 이것도 피보나치 수열처럼 첫번째 줄부터 마지막 줄까지 쭉 구해 나가야 할 것이다. 다음은 1부터 n번째 줄까지의 파스칼의 삼각형을 구하는 프로그램이다.

 

program pascal;

const

n=10;

var

T : array[1..100,1..100] of integer;

i,j : integer;

 

begin

 

for i:=1 to n do begin

for j:=1 to i do begin

if (j=1) or (j=i) then T[i,j]:=1 else T[i,j]:=T[i-1,j] + T[i-1,j-1]; {점화식 이용}

write(T[i,j]:5);{출력}

end;

writeln;

end;

 

end.

 

이번 프로그램 역시 점화식를 그대로 따라간다. 이해하는데는 별다른 어려움이 없을것이다.

4. 동적계획법과 최적화 원칙

 

이 세상 모든 문제들이 위와같은 방식으로 풀리면 얼마나 좋으랴. 그러나 세상은 그렇게 만만하지 않은 모양이다. 불행히도 세상에는 동적계획법으로 풀리지 않는 문제가 더 많다. 아무거나 동적계획법으로 풀면 안된다는 소리다.

그럼 동적계획법으로 풀 수 있는 문제와 풀지 못하는 문제를 어떻게 구분해야 잘 구분했다고 소문이 날까? 여기서 하나 알아둬야 할 것이 최적화의 원칙(principle of optimality)이다.

 

최적화의 원칙 : 어떤 큰 문제의 최적해는 그 문제에 속하는 부분문제의 최적해를 항상 포함한다.

 

이게 뭔 소린가는 예를 들어 설명하는 편이 더 쉬울것이다. 두 도시를 연결하는 최단경

로를 구하는 문제를 생각해보자. 항상 동적계획법으로 문제를 풀고자 할때는 최적화의 원칙이 성립하는지, 즉 동적계획법으로 풀 수 있는 문제인지를 미리 확인해야한다. 이는 동적계획법뿐만 아니라 모든 다른 알고리즘을 적용하려 할때도 마찬가지다. 어떤 알고리즘을 적용하려면 그 알고리즘을 적용할 수 있는 문제인가 하는것을 미리 생각해 봐야한다.

다음 회에서는 동적계획법을 이용해 문제를 푸는 방법을 좀더 자세히 알아보도록 하겠다.

신고

'Computer Science > Algorithm' 카테고리의 다른 글

알고리즘 강좌 6회  (0) 2010.11.28
알고리즘 강좌 5회  (0) 2010.11.27
알고리즘 강좌 4회  (0) 2010.11.27
알고리즘 강좌 3회  (2) 2010.11.27
알고리즘 강좌 2회  (2) 2010.11.27
알고리즘 강좌 1회  (1) 2010.11.27
  1. 2012.11.03 15:53 신고

    c언어가 아니네요 ㄷㄷ
    아니 베이직이네요

    • WOEK 2012.11.15 01:04 신고

      저건 의사코드 입니다.


알고리즘 강좌 1회

- 알고리즘 개론 -

 

1. 알고리즘

알고리즘을 한마디로 정의하면,

 

"어떤 문제의 해답을 찾아주는 일반적인 단계별 절차"

 간단한 예를 하나 들어보자. 여러분은 전화번호부에서 사람을 찾을때 어떻게 찾는가?

혹시 전화번호부의 첫장부터 끝장까지 넘겨가면서 원하는 사람의 이름을 찾는가?-_-;; 아마 정상적인 사회생활이 가능한 사람이라면 그런 미친짓은 하지 않으리라 믿는다. 그러면 어떻게 찾는가?

그렇다. 여러분도 아시다시피 전화번호부에 있는 사람들의 이름은 가나다 순으로 정렬이 되어있다. "정동섭"이라는 인물을 찾고자 할 경우 전화번호부의 'ㅈ'항목을 찾은 다음, '정'으로 시작하는 사람들의 이름을 찾고, '동'이라는 글자가 이어지는 이름을 찾아낸 후, 마지막으로 '섭'을 찾으면 "정동섭"이라는 사람의 전화번호를 알 수 있게 되는 것이다. 물론 사람마다 약간의 차이는 있겠지만.

위에서 말한 두가지 방법. 즉 무식한 방법과 유식한(?)방법. 이 두가지 방법 모두다 알고리즘으로 볼 수 있다. "정동섭이라는 이름을 가진 사람의 전화번호 을 찾아라" 라고 하는것이 우리에게 주어진 문제이고, 위에 주절주절 써놓은 것들이 해답을 찾아주는 절차, 즉 알고리즘이다. 그리고 이런 알고리즘을 사용해서 주어진 문제를 해결하는 것을 문제를 푼다(solve)라고 한다.

하지만 전화번호부에서 특정한 사람의 전화번호를 찾는것은 꼭 저 위의 두가지 방법만 있는것은 아니다. 저 두 방법외에 엄청나게 많은 방법이 존재할 수 있다. 이러한 방법들도 모두 알고리즘이라고 할 수 있는 것들이다.

앞으로 이 강좌에서는 여러가지 알고리즘들을 사용해 컴퓨터로 주어진 문제를 푸는 방법에 대에 설명하게 될 것이다. 여러분이 앞으로 공부할 내용들은 모두 이 "알고리즘"에 대한 것들이다.

2. 알고리즘의 중요성

 

앞에서 말했듯이 전화번호부에서 사람을 찾는 방법.. 즉 알고리즘은 여러가지가 있을 수 있다.

하지만 이 중에서 어떤 것을 선택해야 할까? 역시 "유식한 방법"을 선택하는 것이 좋을 것이다. 유식한 방법이 무식한 방법보다 더 빠르기 때문이다.

하지만 앞으로 우리는 이러한 일들을 컴퓨터에게 시킬것이다. 컴퓨터는 연산속력이 인간과는 비교가 안 될 정도로 빠르다. 그러면 컴퓨터는 무지 빠르니까 그냥 무식한 방법으로 풀게 해도 답은 금방 나오지 않을까?

대답은 "No"다. 만약에 찾는 전화번호부에 실린 이름들의 수가 1,000,000,000,000개라고 하자. 찾는 이름이 전화번호부 900,000,000번째에 있다면 컴퓨터는 전화번호부의 이름과 찾고자 하는 사람의 이름을 900,000,000,000번 비교해봐야 할 것이다. 하지만 유식한 방법의 경우 이러한 비교횟수는 크게 줄어든다. 동명이인만 가득한 엉터리 전화번호부가 아니라면 무식한 방법보다는 훨씬 더 빠르게 찾을 수 있을 것이다.

다음 표에서는 1항부터 n항까지 피보나치 수열(Fibonacci Sequence)을 구하는 두 가지 알고리즘이 소요하는 시간을 나타내고 있다. 이 두 가지 방법이 뭔지까지는 알 필요없다.(하지만 이 강좌를 읽는 독자들은 대충 어떤것들인지 감이 오리라 믿는다) 여기서 눈여겨 봐 두어야 할 것은 두 알고리즘이 정답을 출력하는데 소요되는 시간이다.

 

n

유식하게 풀 경우

무식하게 풀 경우

40

41 ns

1048000 ns

60

61 ns

1 초

100

101 ns

13 일

160

160 ns

38000000 년

200

201 ns

40000000000 년

 

여기서 ns는 나노초.. 즉 0.000000001초이다. 위 표에서 볼 수 있듯이, 좋은 알고리즘의 선택은 정답을 한번 보기 위해 40000000000년을 기다리는 불상사를 막아준다.(설마하니 피보나치 수열의 200번째 항을 보고싶어서 40000000000년을 기다리는 사람은 없겠지만) 한마디로 말해서 좋은 알고리즘의 선택이 무엇보다 중요하다는 것이다.

특히나 정보올림피아드 같은 대회를 보면, 모두 하나같이 문제에 제한시간을 두고 있다. "이러저러한 문제를 푸는 프로그램을 작성하라. 단, 프로그램이 10초이내에 답을 출력해야 한다." 프로그램으로 하여금 복잡한 문제를 풀때 빠른 시간내에 답을 출력하게 하려면 역시 "좋은 알고리즘"을 사용해야한다.

3. 시간복잡도

 

시간복잡도.. 영어로는 time complexity.

시간복잡도란 알고리즘의 수행속도에 대해 프로그램,컴퓨터,언어 등등의 세부사항과는 독립적인 측정법이다.

일반적으로 알고리즘의 수행시간은 입력데이터의 크기(위의 예를 보면 피보나치 수열의 항수)에 따라 증가하고, 컴퓨터가 실행하는 연산이 몇 번이나 수행되는가에 비례한다. 알고리즘 중의 일정한 명령문들을 선택해서 단위연산으로 잡고, 이 단위연산을 몇 번 수행하는가 알아내는 것이 시간복잡도를 분석하는 것이다.

내가 써놓고도 무슨말인지 모르겠군. 예를 들어보자.

for i:=1 to n do begin

for j:=1 to n do begin

...어쩌구 저쩌구 처리...

end;

end;

이런 프로그램에서, 가운데에 어쩌구 저쩌구 처리.. 하는 부분을 단위연산이라고 생각해보자. 이 어쩌구 저쩌구 처리는 이 프로그램을 다 끝냈을때 몇 번 수행될까?

당연히 n*n=n2 번이 될 것이다. 어쩌구 저쩌구 처리가 엄청 긴 명령문들이든, 엄청 짧은

명령문이든 상관없이 n2번 이 명령문들을 실행하게 된다. 이 경우의 시간복잡도는 n2 이라고 말할 수 있다.

그런데 다음과 같은 경우는?

for i:=1 to n do begin

for j:=i to n do begin

...단위연산...

end;

end;

이경우 단위연산을 수행하는 횟수는... 1+2+3+4+...+n 이므로 계산하면 (n2+n)/2 이다.(수1 교과서에 나와있다-_-;) 이때의 시간복잡도도 역시 단위연산의 수행횟수, 즉 (n2+n)/2이다.

하지만 이렇게 시간복잡도를 말해버리면 좀 멋이 없어보인다. 그래서 그랬는지 몰라도 전산학자들은 O표기법이란 것을 만들었다. 사실 O표기법의 정의에 대해 파고들어가면 끝이 없으므로, 여기서는 간단히 생각하기로 한다. 시간복잡도에서 나온 식에서 가장높은 차수만을 써주면 되는 것이다.

즉 시간복잡도 (n2+n)/2는 O(n2) 로 표시한다. 최고차항 앞에 붙어있는 계수도 생략한다. 고로 시간복잡도가 100n이어도 O(n), 0.1n이어도 O(n)이 되는 셈이다. 이렇게 계수를 생략해 버리는 이유는 "별로 중요하지 않기때문"이다. 500n과 0.1n2를 생각해 보자. 언뜻 보기에는 500n쪽이 더 수행시간이 느리지만, 조금만 n이 커지면 형세는 금방 역전된다. 즉 계수보다는 차수가 더 수행시간에 영향을 준다는 소리다.

결국, 시간복잡도가 O(n2)라는 말은 "이 알고리즘의 수행시간은 n2에 비례한다!" 라는 말의 다른 표현이 되는것이다.

이런 식으로 거의 모든 알고리즘들의 시간복잡도를 나타낼 수 있다.

O(n), O(n2), O(n4), O(n100), O(log n), O(nlog n), O(2n)

이런 식으로 알고리즘의 시간복잡도를 표현하면, 알고리즘들의 수행시간들을 대충 짐작할 수 있게 된다. n의 최대크기가 100일때 O(2n)의 알고리즘으로 답을 구한다고 생각해 보자. n이 100이면 컴퓨터는 2100번의 단위연산을 수행해야 된다. "음, 내가 살아있는 동안 답을 보기는 힘들겠구나"라고 생각하면 될 것이다.

알고리즘의 시간복잡도를 분석할 수 있으면, 자신이 선택한 알고리즘이 수행되는 시간을 대충이나마 짐작할 수 있다. 이렇게 되면 자신이 어떤 알고리즘을 선택해서 문제를 풀어야 될 지 명확하게 알 수 있을 것이다.

신고

'Computer Science > Algorithm' 카테고리의 다른 글

알고리즘 강좌 6회  (0) 2010.11.28
알고리즘 강좌 5회  (0) 2010.11.27
알고리즘 강좌 4회  (0) 2010.11.27
알고리즘 강좌 3회  (2) 2010.11.27
알고리즘 강좌 2회  (2) 2010.11.27
알고리즘 강좌 1회  (1) 2010.11.27
  1. 마크 2015.10.30 15:53 신고

    좋은 내용 감사합니다. 즐겨찾기 해 놓고 꾸준히 방문하며 나머지 내용도 다 읽어보도록 하겠습니다.

+ Recent posts

티스토리 툴바