'COMPUTER TECH/C, C++'에 해당되는 글 34건

  1. 2010.08.12 피보나치 수열
  2. 2010.08.12 MyVector만들기
  3. 2010.08.09 최단경로 알고리즘
  4. 2010.08.09 Static Member 와 Const Member

피보나치 수열

 

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

댓글을 달아 주세요


#ifndef __MYVECTOR_H
#define __MYVECTOR_H

template <class T>
class MyVector
{
 int cap;  //현재 최대 보관 가능 공간크기
 int usage;   //현재 보관된 개체 수
 T *base;     //개체를 보관할 버퍼 위치

public:
 class iterator //객체 출력자-분석하시오.
 {
  
  friend class MyVector<T>;
  T *pos;
  
    public:
  iterator(T *_pos=0)
  {
   pos = _pos;
  }
  iterator(const iterator &in)
  {
   pos = in.pos;
  }
  operator T*()
  {
   return pos;
  }
  iterator operator++()
  {
   pos++;
   return (*this);
  }
  const iterator &operator++(int)
  {
   static iterator re;
   re.pos = pos;
   pos++;
   return (*this);
  }
 };
 
 //초기화하는 습관을 키운다
// int cap;  //현재 최대 보관 가능 공간크기
// int usage;   //현재 보관된 개체 수
// T *base;     //개체를 보관할 버퍼 위치
 MyVector(int _capacity=0,T data =0)//생성자
 {
  cap=_capacity;
  base=new T[cap];
  usage=0;
  for(int i=0; i<cap; i++)
  {
   base[i]=data;
  }
  //속성 초기화
  //_capacity만큼 버퍼 공간 할당
  //data를 _capacity만큼 보관

 }
 
 virtual ~MyVector()
 {
  delete []base;
 }
 //버퍼가 할당되어 있으면 버퍼를 해제
 
 void push_back(T in)
 {

  if(cap==0)
  {  
   cap=1;
   base=new T[cap];
  }
  else if(usage==cap)
  {
   extend();   //확장하는 것을 private에 함수로 구현했음(extend)
  } 

  base[usage]=in;
  usage++;

 
  //공간이 꽉 찼다면 배열을 cap*2배로 버퍼 증가 후 usage에 값을 저장.
  //(cap==usage)가 참이라면 공간의 여유분이 없음 
  //공간이 남아 있다면 usage에 값을 저장.(base[usage]위치에 data를 보관)
  //usage증가 
 }

 T &operator[](int index)
 {
  if(index>=0 && index<cap)
  {
   return base[index];
   
  }
  //index가 유효하면 버퍼의 index위치 원소 반환
  //예외 발생할 때는 throw
  else
  {
   throw "잘못된 인덱스 접근입니다.";//유효 하지 않다면 오류 메시지 던지기
  }
 }
 
 void clean()
 {
  for(int i=0; i<usage; i++)
  {
   base[i]=0;
  }

  //보관된 개체수를 0으로 reset
  
 }
 
 int size()
 {
  return usage;//보관량
 }
 
 iterator begin()
 {
  iterator re(base);
  return re;
 }
 iterator end()
 {
  iterator re(base+usage);
  return re;
 }
 void insert(iterator it,T in)
 {
  int gap=it-base;  
  
  for(int i=usage; i>=gap; i--)
  {
   base[i+1] = base[i];
  }  

  base[gap]=in;   
  
  //유효한지 확인 int gap=pos-base;
  //gap이 유효하지 않으면 함수 종료
  
  //꽉 찼다면
  //버퍼가 할당되어 있다면
  //cap*2만큼 버퍼 공간 확장
  //아니라면 1만큼 버퍼공간 할당
  //gap위치에서부터 뒤에 보관된 개체를 ShiftRight하여라
  //gap위치에 in을 보관하라

  //usage 증가
  usage++;

 }
 void erase(iterator it)
  {
  int gap=it-base;
  
  base[gap]=0;
  for(int i=gap; i<usage; i++)
  {
   base[i]=base[i+1];
  }
  usage--;

  
  //gap에서부터 윈쪽으로 이동
  //usage 감소
 }
 int capacity()
 {
  return cap; //전체 크기 넘겨주기.
 }
 private:

  void extend()
  {
   T* temp=new T[cap];
  
  for(int i=0; i<usage; i++)
  {
   temp[i]=base[i];
  }
  cap=cap*2;
  delete[] base;
  
  base=new T[cap];
  
  for(i=0; i<usage; i++)
  {
   base[i]=temp[i];
  }
  
   delete[] temp;
  }
 
};


 template <class T>
 MyVector<T>::iterator find(MyVector<T>::iterator &beg,MyVector<T>::iterator &end,T data)
 {
  for( ; beg !=end; ++beg)
  {
   if(*beg == data)
   {
    break;
   }
  }
  return beg;
 }

#endif

'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

댓글을 달아 주세요


1. 다익스트라 알고리즘

 

2. 벨만-포드 알고리즘

 

'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

댓글을 달아 주세요

static 멤버

    instance의 멤버가 아닌 Class의 멤버

    해당 클래스의 전체 instance를 관리하기 위한 목적의 멤버라 할 수 있다.

    static 멤버 속성은 소스파일(class  정의문 밖)에 변수 선언을 통해 구체화 시켜야 함

    static 멤버 메소드에서는 static 멤버에만 접근이 가능하다.

    static 멤버 속성을 위한 메모리는 프로그램 시작시 할당된다. (다른 멤버 속성은 instance의 생성시 할당됨)

    클래스명과 스코프 연산자 멤버명으로 접근 가능하다.(접근 권한이 있을 시)

   const 멤버

    const 멤버 속성은 생성자 initilalize하여야 한다.

    const 멤버 메소드는 signature뒤에 const가 붙는다.(선언 및 정의에 둘다)

    const 멤버 메소드는 멤버 속성을 변경할 수 없다.(즉, const 멤버 메소드만 호출할 수 있다.)

 class Stu

    {

        const int num;

        char *name;

        static int scnt;

        ...

    public:

        Stu(const char *_name);

        ...

        int HowManyStues()const;

    private:

       static int SetNum();  

    };

    int Stu::scnt=0;

    Stu::Stu(const char *_name):num(SetNum())//Initialize

    {

       ...

    }

    int Stu::HowManyStues()const

    {

         return scnt;

    }

    int Stu::SetNum()

    {

        scnt++;

        return scnt;

    }

 

    void Foo()

    {

         cout<<"현재 학생 수는"<<Stu::HowMany()<<"입니다."<<endl;

    }


'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

댓글을 달아 주세요

이전버튼 1 2 3 4 이전버튼