자료구조 공부#5 (순환, 반복#2)

2021.03.12 - [전체글] - 자료구조 공부#4 (순환, 반복)

이전 내용에서 이어지는 내용 입니다.

---

하노이 탑 문제

 

하노이탑 문제 출처: 교수님 수업자료

 

하노이 탑의 경우엔 순환의 방법이 효율적이다.

 

n=3 인경우 풀이과정

 

 

일반적으로 버퍼의 개념을 통한 해석

// 막대 A에 쌓여 있는 n개의 원반을 B를 임시공간으로 하여 막대 C로 옮긴다
void hanoid_tower(int n, char A, char B, char C){
	if (n==1){
      A에서 C로 원판을 옮긴다.
    }
	else{
    	hanoid_tower(n-1,A,C,B);
        A에 있는 한개의 원한을 C로 옮긴다.
        hanoid_tower(n-1, B,A,C);
    }
}

 

순환방식으로 풀이한 하노이탑의 유사코드

우리는 n개의 원한을 A에서 C로 옮기는 것이 목적이다. 그러므로 그 한개를 뺀 n-1개 만큼 임시버퍼에 옮기고 마지막 한개를 C에 옮기는 식으로 순환하여 함수를 호출하면 된다.

else{}부분을 중요시 보아야 하는데

 

알고리즘 순서

1. 아래를 순환해서 결국 마지막 남은 1개의 원반을 C로 옮긴다.
2. A에 있는 원반 n-1개를 C를 임시버퍼로 하여 B에 옮긴다
3. 그 이후 A에 남은 제일큰 원반 1개를 C로 옮긴다
4. B를 시작으로 n-1개를 A를 임시버퍼로 해서 C에 옮긴다

 

위 과정에서 임시 버퍼는 원반을 옮기기전 쌓아두는 임시로 사용하는 공간이다.

하나를 옮기기위해 위에 n-1개를 옮기고 나면 위치만 바뀔뿐 문제 구조는 별 다를게 없기 때문에 매개변수 호출 순서만 바꾸어서 다시 재 호출 하는 식이다.

 

 

#include <stdio.h>

void hanoi_tower(int n, char A, char B, char C){
	if(n==1){
    	printf("원판 1 을 %c 에서 %c로 옮긴다. \n", A, C);
    }
    else{
    	hanoid_tower(n-1,A,C,B);
        printf("원판 %d 을 %c 에서 %c로 옮긴다",n,A,C);
        hanoid_tower(n-1,B,A,C)
    }
}

int main(void){
	hanoid_tower(4,'1','2','3');
    return 0;
}

---

느낀점 : 코드의 실행 결과는 어떤 순서로 몇번쨰 원반을 어디로 옮기면 되는지 출력되는 형식이다.
수업 자체에 설명은 정말 난생 처음 접하는 사람은 무슨말 하는지 모를 내용이기도 하고, 아는사람도 한줄 한줄 조금씩더 고민해 봐야 익숙해질 수 있는 부분이다. 필자인 나또한 한번씩 다시 읽어보아야 할 알고리즘인거 같다.
반대로 피보나치에선 순환이 복잡도가 더 커서 사용이 덜되는 이유도 다시한번 봐야곘다.