- 다이나믹 #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회  (1) 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회  (1) 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]값을 찾을 수 있습니다


'Info. > Fun' 카테고리의 다른 글

영작할때 도움  (0) 2014.11.17
Don't worry be HAPPY  (0) 2014.11.17
집에서 하루 6분으로 복근만들기  (0) 2011.08.09
do you like Coffee?, 커피 종류  (0) 2011.08.09
문명4 OST orchestra Ver.  (0) 2010.11.30
Google VS Apple VS MS  (0) 2010.11.27

정보보안 전문가란?


정보보안 전문가는 해커의 침입과 각종 바이러스 등 악성코드의 발생에 대비, 보안 이론과 실무 보안 정책 능력을 갖춰 전산망 보안과 유지를 담당합니다. 또 정보시스템과 정보자산을 보호하기 위해 보안정책을 수립하고, 정보보안에 대한 예방책을 세우고 시스템에 대한 인가받지 않은 접근 및 운영을 통제하며, 침입 발생시 즉각적으로 대응하고 손상된 시스템을 복구하는 임무를 가지고 있습니다.

 

 

정보보안 전문가가 되려면 IT에 대한 전반적인 지식은 기본이며 경제와 산업에 대한 폭 넓은 안목과 센스까지 겸비해야 합니다. 특히 전문적인 침입자에 대응하고 시스템을 복구하기 위해서는 컴퓨터시스템, 네트워크, 언어 전반에 걸친 넓고 깊은 지식이 필요합니다.

 

 

정보보호 기술은 시스템과 네트워크 기술에 그 기초를 두고 있기 때문에 운영 체제, 데이터베이스, 시스템 관리, C언어, 네트워크 프로그래밍에 대한 전반적인 지식이 필요합니다. 해커들의 해킹 기법과 바이러스에 대한 지식도 필수적입니다. 특히 역으로 얼마든지 정보시스템을 유린할 수 있기 때문에 윤리성도 주요 요건으로 꼽힙니다.

 

 

2. 정보보안 전문가는 왜 될까?

 


정부는 인터넷 기반의 IT 인프라를 구축하여 정보화 사회 건설을 국가적인 지상 과제로 삼고 있습니다. 이와같은 점에서 정보보호 산업은 인터넷 서비스에 대한 안전과 신뢰성 제고를 통해 국내의 산업 경쟁력을 높이는 밑거름이 될 뿐 아니라 국가 안보와도 직결되기 때문에 정보보안 전문가의 위상은 크게 향상될 것으로 예측됩니다.

 

 

이와 더불어 컴퓨터 해킹과 바이러스 유포, 개인ㆍ기업의 정보유출 등이 늘면서 사회에서 필요로 하고 있는 정보보안 전문가의 수요가 늘고 있습니다. 현재로서도 유망직종으로 각광 받고 있지만 국내외에서 정보보안 전문가는 필요로 하는 수요에 비해 사실상 인력이 부족한 상태입니다.

 

 

이와 더불어 정보보안전문가의 직업적 전문성은 타의 추종을 불허하며, 그로인한 경제적인이득은 부가적으로 쌓일것이고, 개인적으로 나은 삶은 물론 국가 및 사회 발전에 있어 명예로운 이점이 될수 있으므로, 여러마리의 토끼를 한번에 잡는 결과를 얻을 수 있습니다.

 

 

3. 정보보안 전문가에서의 자격증 취득과 취업및 진로 방향

 

 

보안전문가 자격증(CISA), 국제공인 정보시스템 보안전문가 자격증(CISSP)


-국제공인 정보보호 분야에서 3~5년이상 경력을 쌓아야 응시가 가능한 자격증으로 정보
보안전문가 과정에 있어서 최종적인 단계라고 생각하시면 됩니다.

 

정보보호전문가(SIS), 정보시스템감리사, 인터넷보안전문가


-국내에서 시행되고 있는 정보보안 자격증으로, 이부분에 대해 먼저 취득을 하고 국제공인 자격을 취득하는 것이 단계라고 생각하시면 됩니다.

 

최근 금융 시장, EC 쇼핑몰, 공공시장 등 정보보안전문가를 필요로 하는 기업들이 늘어나고 있는데 비해 국내의 모든 단계를 거친 정보보안전문가는 1백 명이 채 되지 않아서 정보보호 전문 인력의 부족은 고질적인 문제로 비화될 조짐을 보이고 있으며 세계적으로도 정보보호전문가는 그 수요를 따라가지 못하고 있는 실정입니다. 이러한 인력 공급의 부족으로 정보보안전문가는 그 가치가 직업의 희소성과 전문성으로 인해 상당히 높은 연봉을 받고 있으며 앞으로의 전망 또한 평생직업으로 유효할 것으로 보입니다.

 

4. 정보보안 전문가가 되는 과정.


정보보안 전문가가 되려면 위에서 말씀 드렸듯이 IT에 관한 전반적이고 깊은 지식을 모두 가지고 있어야 하며, 이를 위핸 어느정도 일정한 교육기간의 투자가 이루어 져야 합니다.
이에, 기본되는 프로그래밍언어와, 시스템, 네트워크, 데이터베이스, 실전해킹기법까지 인내를 가지고 진행하셔야 합니다.


알고리즘 강좌 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회  (1) 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회  (1) 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