[백준] 일곱 난쟁이 (완전 탐색)

완전 탐색에는 순열, 부분 집합, 조합이 있으며, 이번 문제는 9개의 숫자중 7개의 숫자를 선택해서 모두 더한 값이 100이 되는 경우의 수를 찾는 문제다.

 

백준 2309번 문제

입력값은 아래와 같다.

20
7
23
19
10
15
25
8
13

 

이번 문제는 재귀 함수를 이용하여 모든 경우의 수를 찾는 기본 문제로, 순열을 이용하면 쉽게 풀 수 있다. 순열이란, n개의 아이템 중에서 r개를 선택하여 순서대로 나열하는 것으로 완전 탐색 기법에 해당한다.

#include <stdio.h>
int finish = 0;
int minimum[9];

void show (int number) {
	int total = 0;
	
	insertsort();
	
	for (int i = 0; i < number; i++) {
		printf("%d\n", minimum[i]);
	}
}

void swap (int first, int second) {
	int temp = minimum[first];
	minimum[first] = minimum[second];
	minimum[second] = temp;
}

void insertsort () {
	for (int i = 1; i < 7; i++) {
		int j;
		int temp = minimum[i];
		
		for (j = i - 1; j >= 0; j--) {
			if (minimum[j] > temp) {
				minimum[j + 1] = minimum[j];
			} else {
				break;
			}
		}
		
		minimum[j + 1] = temp;
	}
}

void CheckTotalHeight (int total, int select, int step) {
	if (finish) {
		return;
	}
	
	if (step == select) {
		int total = 0;
		
		for (int i = 0; i < select; i++) {
			total += minimum[i];
		}
		
		if (total == 100) {
			finish = 1;
			show(select);
		}
		
		return;
	}
	
	for (int i = step; i < total; i++) {
		swap(i, step);
		CheckTotalHeight(total, select, step + 1);
		swap(step, i);
	}
}

int main(void) {
	for (int i = 0; i < 9; i++) {
		scanf("%d", &minimum[i]);
	}
	
	CheckTotalHeight(9, 7, 0);
	
	return 0;
}

 

이번 문제에서 알아야 할 점은 아래와 같다.

 

완전 탐색

 

완전 탐색이란, 어떤 문제를 풀기 위해 모든 요소를 탐색하는 방법으로 시간은 오래 걸리지만 문제를 해결할 확률이 가장 높은 방법이다. 이 방법에서 해결 시간을 줄이기 위해 빠른 재귀함수 종료를 위한 백트래킹 기법, 가까운 답만 찾는 탐욕 기법이 있다.

 

완전 탐색에는 서로 다른 n개의 요소 중 r개를 선택하여 순서대로 나열하는 순열 (중복 X), 순서를 생각하지 않고 n개 중 r개를 선택하여 집합을 만드는 조합 (중복 가능), 조합에서 r개를 선택하여 또다른 집합을 만드는 부분 집합이 있다.

 

이 문제는 순열을 이용해 9개의 요소 중 7개를 선택한 집합들의 합이 100이 되면 오름차순으로 출력하는 문제이며, 풀이 역시 순열을 이용하였다.

 

삽입 정렬

 

기본 정렬 3형제 마지막인 삽입 정렬은 다른 정렬들과 달리 구현 시 Swap을 사용하지 않으며, 어느 정도 정렬된 배열에서 굉장히 빠른 속도를 내는 장점이 있다.

 

삽입 정렬 과정

위의 그림을 아래의 삽입정렬 코드로 표현해보자.

void insertsort () {
	for (int i = 1; i < 6; i++) {
		int j;
		int temp = minimum[i];
		
		for (j = i - 1; j >= 0; j--) {
			if (minimum[j] > temp) {
				minimum[j + 1] = minimum[j];
			} else {
				break;
			}
		}
		
		minimum[j + 1] = temp;
	}
}

 

1) 5, 1, 6, 2, 4, 3 에서 1번째 인덱스인 1을 저장한다. (int temp = 1)

2) i - 1 인덱스와 i 인덱스의 값을 비교한다. i - 1 인덱스의 값이 크기 때문에 i - 1 인덱스의 값을 i 인덱스에 넣는다. (5, 5, 6, 2, 4, 3)

3) 내부 반복문이 모두 돌면 j 는 -1이 된다. 따라서, minimum[0] = 1; 이 대입된다.