[ALPS Study] 완전탐색 - 하노이탑, 블랙잭

- BOJ 11729 하노이탑

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

void hanoi(int n, int start, int mid, int end);
int cnt = 0;

int main() {
	int n; int start = 1, mid = 2, end = 3;
//	printf("원판의 개수를 입력하세요 : ");
	scanf("%d", &n);
	hanoi(n, start, mid, end);
	printf("%d\n", cnt);
	return 0;
}

void hanoi(int n, int start, int mid, int end) {
	if (n == 1) {
		cnt++; 
		printf("%d %d\n", start, end);

	}
	else {
		hanoi(n - 1, start, end, mid);
		printf("%d %d\n", start, end);
		cnt++;
		hanoi(n - 1, mid, start, end);
	}
}

 

2학년 정보과학시간에 주구장창 했고 시험문제에도 나왔던 하노이탑 문제! 이지만... 그 때 당시에도 반강제로 외웠고 이해하지 못한 상태로 끝나서 다시 한 번 재귀함수 공부할 겸 다시 풀어보았다. 그리고 무려 2년만에 좀 이해한 것 같다... 

(아까 폰으로 엄청 열심히 썼는데 지금 노트북으로 들어와보니 왜 절반 이상 날아가 있는 것일까..? 나한테 웨그래 티스토리야ㅡㅡ)

 

- 기본적인 원리

 

n개의 원판이 있을 때, 우리는 이 원판을 처음 기둥에서 목표 기둥으로 옮기고자 한다. 그러기 위해서는 맨 아래에 있는 원판 위의 n-1개의 원판을 가운데로 옮기고, 맨 아래의 원판을 목표 기둥으로 옮긴 뒤, 다시 가운데에 옮겨놓은 n-1개의 원판을 목표 기둥으로 옮겨야 한다. 

이 원리는 n이 2일 때까지 쭉 적용되다가 n이 1이 되면 그냥 바로 처음 기둥에서 목표기둥으로 옮기면 된다. (1개의 원판을 옮길 때에는 별다른 작업이 필요가 없다!)

이를 재귀함수를 통해서 구현하게 된다.

 

- 내가 이해하기 위해 쓰는 글

 

n이 3이라고 해보자. 앞서 설명했듯 먼저 2개의 원판을 시작 기둥(start)에서 중간 기둥(mid)으로 옮겨야 한다. 즉, n=3인 함수 안에서 n=2, start->mid 으로 옮기는 함수를 다시 호출한다.

 

이제 n=2일 때 start 기둥에서 mid 기둥으로 옮기는 함수가 호출되었다! (이제 목표기둥이 mid이다) 이제 2개의 원판을 목표 기둥으로 옮기려면 2개 중 위의 원판 하나를 중간 기둥에 임시로 내려놓아야 한다. 여기선 중간 기둥이 end이겠지?(왜냐면 시작 기둥이 start고 목표기둥이 mid니까!) 그래서 또 함수가 호출된다. 이제 n=1, start->end 인 함수를 호출한다.

 

n=1, 시작 기둥에서 중간 기둥으로 옮기는 함수가 호출되었다. (여기선 목표기둥이 다시 end이다) n=1이므로 if문 안으로 들어온다. start 기둥 --> end 기둥 을 출력하고 함수가 종료된다.

 

n=2 일 때의 함수로 돌아온다. 맨 위의 원판을 옮겨놓았으므로 이제 시작 기둥에서 목표기둥으로 옮긴다. 즉 start 기둥 --> mid 기둥이겠지. 그리고 다시 n=1 hanoi함수가 호출되어 중간 기둥(end)으로 옮겨둔 가장 작은 원판을 목표기둥(mid)으로 옮긴다.

 

n=3 일 때의 함수로 돌아왔다! 위 2개의 원판을 이미 중간 기둥(mid)로 옮겨놓았으므로 맨 아래의 가장 큰 원판을 목표 기둥(end)로 옮긴다. 그리고 중간 기둥에 있는 2개의 원판을 다시 목표기둥으로 옮겨야한다. 따라서 다시 n=2, mid->end 인 함수를 호출한다. 위와 같은 방식으로 다시 2개의 원판이 차례차례 end 기둥으로 옮겨진다.

 

 

- 덧붙이기

 

재귀함수는 얕보면 안되는 굉장히 머리 아픈 녀석이다. 탈출 조건 빼먹어서 무한 루프에 갇히기도 하고, 함수 호출 순서 잘못되어서 괴상한 답이 나오기도 하고 고려해야 할 사항이 상당히 많은 아이이다. 연습이 필요할 것 같다.

 

- BOJ 2798 블랙잭

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h> 

int main() {
	int n,i,j, k, m;
	int tmp, min, sum;
	int numset[100];
	int answer=0;
	//printf("카드의 수를 입력하세요 : ");
	scanf("%d", &n);
	//printf("딜러가 외칠 숫자를 입력하세요: ");
	scanf("%d", &m);
	for (i = 0; i < n; i++) {
	//printf("카드에 적힌 숫자를 입력하세요: ");
	scanf("%d", &numset[i]);
	}

	min = m;
	for (i = 0; i < n ; i++) {
		for (j = i+1; j < n ; j++) {
			for (k = j+1; k < n; k++) {
				sum = numset[i] + numset[j] + numset[k];
				if (sum > m)
					continue;
				tmp = m - sum;
				if (tmp < min) {
					min = tmp;
					answer = sum;
				}
			}

		}
	}
	printf("%d", answer);
	return 0;
}

 

문제를 딱 봤을 때 든 생각 : 설마 3중 for문을 쓰라고? 다 검사해봐야해? 에이 설마.. 다른 방법이 있겠지.. 

근데 해답인진 모르겠는데 일단 동아리 자료에는 실제로.. 그렇게 풀었다.  보니까 stack 이용해서 푼 코드도 있었는데 시간 관계상(오늘 매우 바빴..) 우선은 3중 for문을 이용한 완전 노가다식 풀이를 이용해서 풀어보았다. 

내가 잠깐 생각했던 방식은 저 카드에 적힌 숫자를 정렬해서 풀어볼까.. 했지만 생각만 해보고 더이상 고민을 못 해봤다. 내일 마저 해봐야겠다.

 

- 기본적인 원리

 

사실 원리라고 할 것도 별로 없다. 카드의 수, 딜러가 말할 수, 카드에 적힌 수를 차례대로 입력받은 뒤, 삼중 포문을 이용해 3개의 카드 조합으로 생길 수 있는 모든 숫자 합을 전부 검사한다. 이 때 같은 카드를 중복해서 3개의 카드에 포함시키면 안되므로 j = i+1, k= j+1로 시작한다. (사실 그래서 j<n이지만 k=j+1, k<n 이므로 j<n-1이나 마찬가지다. j가 n-1이게 되면 애초에 k 포문에 못 들어옴) 

포문을 돌 때마다 매번 합을 계산하고, 합이 주어진 수 m 보다 크면 바로 continue시켜준다. (문제에서 그러라고 했다) 만약 아니면 목표 숫자와의 차이를 계산해서 그동안 나온 차이의 최솟값보다 작은지 아닌지 검사해본다. 만약 최솟값보다 더 작다면, 최솟값을 갱신하고 답 변수에 합을 저장한다. 

포문을 다 돌았다면 모든 경우의 수를 다 시도해본 것이므로 답을 출력한다.