●동적계획법(dynamic programming)

- 작은 문제들의 해를 먼저 구하여 저장하고 더 큰 문제의 해를 구할 때 작은 문제의 해를 반복계산하지 않고 저장도니 ㄱ려과를 사용하는 방법이다. 동적계획법을 하기 위해선 주어진 문제의 해를 구하기 위한 순환적인 성질을 구성하여야 한다. 상향식으로 작은 부분부터 해를 구한다.

 

 

●장점

- 프로그램을 구현할 때에는 필요한 모든 가능성을 고려해서 구현하게 된다. 따라서 동적 계획법을 이용하여 항상 최적의 결과를 얻을 수 있다.

 

 

●단점

- 모든 가능성에 대한 고려가 불충분할 경우  최적의 결과를 보장할 수 없다. 동적 계획법을 구현하기 위해서는 충분히 많은 가능성에 대한 고려를 해야 한다. 다른 기법에 비해 메모리를 많이 요구한다.

 

 

●점화식 세우는 법

①해를 구하기 위한 순환적인 성질을 구성해야 한다.

 

②전체 문제도 부분 문제 형태로 표현할 수 있어야 한다.

 

③문제를 어떻게 부분 문제로 분할할 것인지 생각해야 한다.

 

④보통 동적 계획법 문제는 일정 회수의 선택을 반복하는 구조로 이루어져 있다.

 

⑤그 상태에서의 선택과 그 선택 전의 상태를 고려해야 한다.

 

⑥한 번의 선택에서는 생길 수 있는 모든 가능성을 고려해야 한다.

 

⑦최적해를 찾는 문제라면, 그 가능성 중에서 가장 좋은 선택을 찾아야 한다.

 

 

 

Posted by -현's-

댓글을 달아 주세요

 

●큐

- 저 들어간 데이터가 먼저 나오는 구조이다(FIFO). 큐는 데이터를 담는 큐배열, 데이터를 집어넣는 곳을 알려주는 포인터 변수(Tail)와 데이터를 꺼내는 곳을 알려주는 포인터 변수(Head), 입력(Enqueue)출력(Dequeue)을 당담하는 함수 이루어 진다. 큐를 자동으로 구현해 주는 프로그램 기법은 없다.

 

 

 

●Enqueue함수

 void Enqueue(int data)

{

  queue[++tail]=data;

}

 

 

 

●Dequeue함수

int Dequeue(){

  int daga;

  data=queue[++head];

  return data;

}

 

 

 

 

 

 

 

Posted by -현's-

댓글을 달아 주세요

 

●스택(Stack)

- 나중에 들어간 데이터가 먼저 나오는 구조이다(LIFO).

- 스택은 데이터를 담는 스택 배열과 데이터를 담을 위치를 알려주는 스택포인터 변수입력(push)출력(pop)함수로 구현된다.

 

 

 

●push함수

void push(int data)

{

  stack[sp]=data;

  sp++;

} 

 

 

●pop함수

 int pop()

{

  int data;

  sp--;

  data=stack[sp];

  return data;

}

 

 

●재귀호출은 스택을 자동으로 구현해줌으로써, 백트래킹 프로그램을 구현하는데 매우 편리하다.

 

 

 

 

Posted by -현's-

댓글을 달아 주세요

 

●분기한정(Branch and Bound)

- 백트래킹과는 달리, 분기와 한정을 정해서 해를 구하는 기법이다. 백트래킹을 구현할 때 경우의 수가 너무 많아 모든 경우를 다 해보기 어려울 때, 사용하면 좋다. 가지치기하는 기준이 되는 값이 바운드 값이다. 너비우선탐색을 사용한다.

 

●너비우선탐색(BFS, Breadth First Search)

- 반복문과 큐를 이용하여 구현한다. 경로가 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다. DFS 보다 많은 자료를 처리할 경우에 적합한다.

 

●큐(queue)

-  먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조이다.

 

●BFS기법

- 시작점과 연결된 모든 정점을 방문한다.

- 시작점과 연결된 모든 정점을 방문 후 시작점과 연결된 가장 가가운 정점을 방문한다.

- 방문한 정점과 연결도니 모든 정점 중 방문하지 않은 정점을 모두 방문한다.

- 위 과정을 계속 반복한다.

- 모든 정점을 모두 방문하면 탐색을 종료한다.

 

 

Posted by -현's-

댓글을 달아 주세요

백트래킹

- DFS(깊이우선탐색)방식으로 해를 찾는 방법이다. DFS는 해를 찾기 위해 전진, 후진을 반복한다. 백트래킹 재귀 호출을 해서 구현하면 편리하다.

 

●깊이우선탐색(DFS, Depth First Search)

- 답을 찾을 때 가장 위에서 가장 아래쪽으로 들어 갔다가, 제일 밑에 까지 왔을 때 더 들어갈 곳이 없으면 위로 나왔다가 다시 가장 끝까지 들어가는 동작을 되풀이 한다. 여기서 위로 나오는 동작을 백트래킹이라고 한다

 

●스택(stack)

- 나중에 입력된 데이터가 먼저 빠져 나오는 구조이다. 후입선출(LIFO)

 

●사용하는 재귀함수의 수는 수학의 "경우의 수"와 같다. 예를들어 동전,주사위 등의 문제를 코딩할 때 각각의 무제의 경우의 수만큼의 재귀호출을 사용한다.

 

백트래킹 알고리즘으로 해결할 수 있는 문제들

1. 미로에서 길 찾기

2. 미로에서 지나간 길에 쓰인 숫자의 합이 최소인 길 찾기

3. 그래프에서 오일러 패스

4. 그래프에서 해밀턴 사이클

 

 

 

Posted by -현's-

댓글을 달아 주세요

 

●퀵정렬(Quick sort)

- 어느 한 값을 기준으로 이 값보다 작은값을 갖는 데이터와 큰 값을 갖은 데이터를 분리하여 2개의 그룹으로 나눈다. 그리고나서 각 그룹에 대해 위 작업을 재귀적으로 반복해서 정렬한다. 다른 정렬보다 평균적인 실행시간이 빠르다.

 

●퀵정렬 코드( 제대로 정렬이 안됨, 나중에 수정)

 

#include<stdio.h>
#include<stdlib.h>


int i, n = 10, data[10] = {3, 7, 8, 2, 9, 1, 4, 7, 6, 5};

void quick(int array[], int left, int right)
{
 int choice;
 int i, j, temp;
 if(left<right)
 {
  choice = array[left];           //기준이 되는 값을 정한다.

  i=left+1;
  j=right;

  while(1)
  {
   while(array[i]<choice)
    i++;
   while(array[j]>choice)
    j--;
   if(i>=j)                    //교환할 데이터가 없으면 break
    break;
   temp=array[i];
   array[i]=array[j];
   array[j]=temp;
   if(array[i]==choice && array[j]==choice)
   {
    i++;
    j--;
   }
  }
  temp=array[j];
  array[j]=array[left];
  array[left]=temp;
  quick(array, left, j-1);
  quick(array, j+1, right);
 }
}


void output(){
 for(i=0;i<n;i++)
 {
  printf("%d ", data[i]);
 }
 printf("\n");
}


int main()
{
 output();
 quick(data, 0, n-1);
 output();
 return 0;
}

Posted by -현's-

댓글을 달아 주세요

 

●선택정렬(Selection sort)

- 데이터에서 가장 큰 값을 찾아서 마지막 위치에 있는 데이터와 교환하고, 그 다음 두번째로 큰 값을 갖은 데이터를 찾아서 마지막 전 위치에 있는 데이터와 교환한다. 이런식으로 모든 데이터를 정렬한다.

  

●선택정렬 코드

 #include<stdio.h>

int i, n=10, data[10] = {32, 1, 15, 2, 7, 3, 9, 7, 92, 12};

void select(int array[], int n)
{
 int i, j, temp;
 for(i=0; i<n-1; i++)
 {
  for(j=i+1; j<n; j++)
  {
   if(array[i]>array[j])
   {
    temp=array[i];
    array[i]=array[j];
    array[j]=temp;
   }
  }
 }
}

void output(){
 for(i=0; i<n; i++)
 {
  printf("%d ", data[i]);
 }
 printf("\n");
}

int main()
{
 output();
 select(data, n);
 output();
 return 0;
}

 

 

 

 

 

 

 

 

 

Posted by -현's-

댓글을 달아 주세요

 

●삽입정렬(Insert sort)

- 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 배열이 길수록 효율은 떨어진다.

출처 - 위키백과

 

●삽입정렬 코드

 #include<stdio.h>

int i, n=10, data[10] = {30,5, 32,11, 98, 34, 12, 54, 32, 543};

void insert(int array[], int n)
{
 int temp, k;
 temp = k = 0;

 for(i=1; i<n; i++)
 {
  temp = array[i];
  k=i-1;
  while(k>=0 && array[k]>temp)
  {
   array[k+1] = array[k];
   k--;
   array[k+1] = temp;
  }
 }
}

void output()
{
 for(i=0; i<n; i++)
 {
  printf("%d ", data[i]);
 }
 printf("\n");
}

int main()
{
 output();
 insert(data, n);
 output();
 return 0;
}

 

 

 

Posted by -현's-

댓글을 달아 주세요

 

●버블정렬(Bubble sort)

- 인접한 두개의 데이터의 값을 비교해서 정렬되어 있지 않으면 교환하는 정렬이다. 이런방법으로  마지막까지 비교하고 교환하면 한 단계가 끝난다. 그리고나서 2번째 데이터부터 다시 두개의 데이터의 값을 비교해 나가면서 비교한다. 다른 정렬에 비해 정렬 속도는 느리지만 코드는 단순하다.

 

●버블정렬 코드

 #include<stdio.h>


int i;
int n=10;                                         //n은 데이터 개수
int data[10]={30,40,20,10,43,12,54,87,34,1};

void bubble(int array[], int n)
{
 int i, j, temp;
 for(i=0;i<n;i++)
 {
  for(j=0;j<n-i-1;j++)
  {
   if(array[j] > array[j+1])            //i번째 데이터와 j+1번재 데이터를 비교해서 j+1번째 데이터가 크면 교환
   {
    temp = array[j];
    array[j] = array[j+1];
    array[j+1] = temp;
   }
    
  }
 }
 
}


void output()
{
 for(i=0; i< n; i++)
 {
  printf("%d ",data[i]);
 }
 printf("\n");
}


int main()
{
 output();
 bubble(data,n);
 output();
 return 0;
}

 


 

 

 

 

Posted by -현's-

댓글을 달아 주세요

 

●정렬(sort)

- 임의의 순서대로 배치되어 있는 집합을 어떤 기준에 맞춰 순서대로 재배치하는 것이다. 정렬의 방법에는 크게 내부정렬와 외부정렬로 나눌수 있다.

 

●내부정렬(internal sort)

- 내부정렬(internal sort)은 정렬을 할 데이터가 메모리 안에서 정렬이 이루어 질때 사용한다. 내부정렬에는 버블정렬,선택정렬,퀵정렬,2-way합볍정렬,힙정렬,리스트정렬 등이 있다.

 

●외부정렬(external sort)

- 외부정렬(external sort)은 데이터의 크기가 매우 클때 외부의 디스크같은 보조 기억 장치를 사용하여 정렬하는 방법이다. 외부정렬에는 자연합병,균형2-way합볍,다단계합병 등이 있다. 

 

 

Posted by -현's-

댓글을 달아 주세요