수학 식 이용 알고리즘

분할 정복 알고리즘

 

분할 정복 알고리즘은 문제를 나누어서 해결하는 것입니다.

예로 병합정렬 같은 것이 있습니다.

해결 방법에는 여러가지가 있지만 대표적으로 재귀 호출이 있습니다.

 

재귀호출은 다음과 같이 이루어집니다.

function F(x):

if F(x)의 문제가 간단 then:

return F(x)을 직접 계산 값

else:

x를 y1,y2로 분할

F(y1) F(y2) 호출

return F(y1),F(y2)로부터 F(x)를 구한 값

 

 

재귀호출의 대표 작인 하노이의 탑을 보죠.

그림출처:https://ko.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/a/towers-of-hanoi

 

하노이 타워의 대표적 원칙

1.  한 번에 하나의 원판만 옮길 수 있다.

2.  큰 원판이 작은 원판 위에서 있어서는 안 된다.

A막대에서 맨 마지막 한개의 원판과 나머지 n-1개의 원판이 있다고 치면

A막대의 n-1개 원판을 B로 옮깁니다.

A의 젤 밑에있는 원판을 C로 옮깁니다.

B의 n-1개의 원판을 C로 옮깁니다.

이런 식으로 진행하게 됩니다.

이는 재귀함수 호출로 이루어집니다.

의사 코드로 보면

 

void hanoi_tower(int n,char from, char tmp, char to)

{
       if(n==1)

from에서 to로 원판을 옮긴다.

else{

1.from 맨 밑 원판 제외 나머지 원판을 tmp로 옮긴다.

2.from에 한개의 원판을 to로 옮긴다.

3.tmp의 원판들을 to로 옮긴다.

}

 

}

이를 코드로 작성해봅시다.

 

void hanoi_tower(int n,char from, char tmp, char to)

{
       if(n==1)

printf("원판 1을 %c에서 %c으로 옮긴다 \n",from, to); //from에서 to로 원판을 옮긴다.

else{

hanoi_tower(n-1,from,to,tmp); //1.from 맨 밑 원판 제외 나머지 원판을 tmp로 옮긴다.

printf("원판 %d을 %c에서 %c로 옮긴다 \n",n,from,to); //2.from에 한개의 원판을 to로 옮긴다.

hanoi_tower(n-1,tmp,from,to); //3.tmp의 원판들을 to로 옮긴다.

}

 

}

으로 재귀호출을 진행합니다.