피보나치 수열

 

1. 피보나치수의 정의

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

 f(1) = f(2) = 1

 

2. f( )에서 문제 크기가 커짐에 따라 중복 호출이 증가하는 모습

수행되는 f( )

f(2)의 중복 호출횟수

f(3)

1

f(4)

2

f(5)

3

f(6)

5

f(7)

8

f(8)

13

f(9)

21

f(10)

34

 

3. 수정된 피보나치수의 정의

 f[n] = f[n-1] + f[n-2]

 f[1] = f[2] = 1

 

부분 결과를 저장하면서 해를 구해나감

 

4. 피보나치수 (동적 프로그래밍 2)

 f(n)
 {
    if(f[n] != 0) return f[n];
    else
    {
       if(n == 1 || n ==2) return f[n] = 1;
       else f[n] = f(n-1) + f(n-2);
       return f[n];
    }
 }

 

행렬경로

 

 

1. 상황

① i=j=1이면 원소 (1,1)에 이르는 최고점수를 구하는 것이다. 원소 (1,1)만 방문하므로 원소 (1,1)의 값이 답이다

② i=1, j>1이면 첫째 행의 한 원소에 이르는 최고점수를 구하는 것이다. 첫째 항을 따라 오른쪽 수평 이동하는 방법 밖에 없다.

   따라서 (1, j)의 바로 왼쪽 원소 (1, j-1)에 이르는 점수 ((1, j-1)에 이르는 유알한 점수이자 최고점수)에 원소 (1, j)의 값을 더하면 된다.

③ i>1, j=1이면 첫째 열의 한 원소에 이르는 최고점수를 구하는 것이다. 첫째 열을 따라 아래로 수직 이동하는 방법 밖에 없다.

   따라서 (i, 1)의 바로 위쪽 원소 (i-1, 1)에 이르는 점수 ((i-1, 1)에 이르는 유알한 점수이자 최고점수)에 원소 (i, 1)의 값을 더하면 된다

④ 이들 경우가 아니면 원소 (i, j)의 바로 왼쪽 원소에 이르는 최고점수와 원소 (i, j)의 바로 위쪽 원소에 이르는 최고점수

    큰것에 원소 (i, j)의 값을 더한 것이 원소 (i, j)에 이르는 최고점수이다.

 

2. 행렬 경로 문제 (재귀 호출)

 

3. matrixPath( )에서 문제 크기가 커짐에 따라 중복 호출이 증가하는 모습

수행되는 matrixPath( )

matrixPath(2, 1)의 중복 호출횟수

matrixPath(2, 2)

1

matrixPath(3, 3)

3

matrixPath(4, 4)

10

matrixPath(5, 5)

35

matrixPath(6, 6)

126

matrixPath(7, 7)

462

matrixPath(8, 8)

1,716

matrixPath(9, 9)

6,435

 

4. 행렬경로 문제 (동적 프로그래밍)

 

 

조약돌 놓기

 

1. 조약돌 놓기 문제 (재귀호출)

 pebble(i, p)

 ▷ i열이 패턴 p로 놓일 때의 최고점수

 ▷ w[i, p] : i열이 패턴 p로 놓일 때 i열에 돌이 놓인 곳의 점수합
 {
    if(i==1) return w[1, p];
    else 
    {
       max = -∞;
       for(q=1; q<=4; q++)
       {
          if(패턴 q과 패턴 p와 양립)
          {
             tmp = pebble(i-1, q);
             if(thmp > max) max = tmp;
          }
       }
    return (max+w[i,p]);
    }  
 }

 

2. 조약돌 놓기 패턴

 

3. pebble( )에서 문제가 커짐에 따라 중복호출의 비율이 증가하는 모습

문제의 크기 (n)

부분 문제의 총 수

함수 pebble( )의 총 호출 횟수

1

4

4

2

8

12

3

12

30

4

16

68

5

20

152

6

24

332

7

28

726

 

4. 조약돌 놓기 문제 (동적 프로그래밍)

 pebble(n)
 {
    for(p=1; p<=4; p++)
       peb[1, p] = w[1, p];
    for(i=2; i<=n; i++)
    {
       for(p=1; p<=4; p++)
          peb[i, p] = max(peb[i-1, q]) + w[i, p];
    }
    return max(peb[n, p]);
 }

 

 

최장공통부분순서(LCS)

 

<bcdb>는 문자열 <abcbdab>의 부분순서다. 문자열 <abcbdab>안에 b, c, d, b가 차례로 나타나기 때문이다.

문자열 <abcbdab>와 <bdcaba>에 대해서 <bcba>는 두 문자열에 존재하는 가장 긴 공통 부분순서이다.

 

1. 최장 공통 부분순서 길이 (재귀적 호출)

 func lcs(x,y)
    if ( length(x)=0 or length(y)=0 ) 
       return ""

    best = lcs(x[1,n-1],y[1,m])

    if ( length(best) < length(lcs(x[1,n],y[1,m-1])) )
       best = lcs(x[1,n],y[1,m-1])

    if ( x[n] = y[m] and length(best) < length(lcs(x[1,n-1],y[1,m-1]) + 1 )
       best = lcs(x[1,n-1],y[1,m-1]) + x[n]

   return best

 

2. 최장 공통 부분순서 길이 (동적 프로그래밍)

  func lcs(x,y)
   n = length( x ), m = length( y )
   for i from 0 to n
      for j from 0 to m
          if ( i is 0 or j is 0 )
             table[i,j] = ""
            if ( x[i] == y[j] ) table[i,j] = x[i]
         else
             /* Sentinel */
             table[i,j] = table[i-1,j]
             if ( length( table[i,j] ) < length( table[i,j-1] ) )
                table[i,j] = table[i,j-1];
             if ( x[i] = y[j] and length( table[i,j] ) < length( table[i-1,j-1] ) + 1 )
                table[i,j] = table[i-1,j-1] + x[i];
   return table[n][m]
 

'COMPUTER TECH > C, C++' 카테고리의 다른 글

퀵 정렬  (0) 2010.08.12
힙 트리  (0) 2010.08.12
피보나치 수열  (0) 2010.08.12
MyVector만들기  (0) 2010.08.12
최단경로 알고리즘  (0) 2010.08.09
Static Member 와 Const Member  (0) 2010.08.09
Posted by ... XJAPAN

댓글을 달아 주세요