3-1편 무식하게 풀기 1

1. 무식하게 풀기(brute-force)

- 가장 많이 하는 실수 중 하나가 쉬운 문제를 어렵게 푸는 것

- 공부를 열심히 할수록 복잡하지만 우아한 답안에 집착하기에..

- 부르트포스 문제는 빠르면서도 정확한 구현능력을 요구함

- 부르트포스는 더 빠른 알고리즘의 근간이 되기에 잘 익혀둘 필요가 있음

2. 재귀 호출과 완전 탐색

1) 재귀 호출

※ tail recursion 이라는 것도 있긴하지만 여기서 설명은 하지 않음

- 큰 조각을 반복되는 유사한 작은 조각들로 나누어 접근하는 것

- 작은 조각들 중 하나를 자신이 해결하고 나머지 조각들을 자기 자신을 호출해서 해결

예) 1 ~ n까지 합

int recursum(int n){
	if(n == 1) return 1;
	return n + recursum(n-1);
}

  n 과 1 ~ n-1 까지의 합으로 구분 => n-1과 1~ n-2 까지의 합으로 다시 구분 ... => 2와 1 ~ 1 까지의 합으로 마지막 구분

  n 의 합을 스스로 처리하고 나머지 1 ~ n-1 까지의 합을 자기자신을 호출하여 처리함

- 재귀는 크게 두 부분으로 구성됨

  base case : 더이상 쪼개지지 않는 작업, 최소 입력에 대한 작업, 답이 없을 경우에 대한 작업

  general case : base case를 제외한 재귀를 호출할 작업

예제. 문제 : PICNIC

- 절차적 접근

https://algospot.com/judge/problem/read/PICNIC

1) 문제를 읽고 이해하기

  : 시간제한 1000ms

  : 메모리제한 2^16kb

  : 2 <= n <= 10

2) 문제 재정의

  : 서로 친구인 학생 끼리 짝을 짓는 경우의 수

3) 계획 세우기

  : 짝이 지어지지 않은 학생을 골라서 친구사이인 다른 학생과 짝을 지어줌

  : 아직 짝이 지어지지 않은 학생을 대상으로 위 과정을 반복

  => "한쌍" 과 "짝이 지어지지 않은 학생" 으로 문제를 분할 => 재귀

4) 계획 검증하기

  : 시간복잡도 : 첫 짝이 없는 친구를 고르는 경우(1)(0 학생이 무조건 처음이므로) * 0학생과 친구인 관계(N-1) * 0과 0 친구를 제외한 다음 짝이 없는 친구를 고르는 경우(N-2) * 두 번째 고른 학생과 친구인 관계(N-3) * ... * 1 = 9! ≒ 360,000 

   즉, 1억번 내에 들어옴

  : 공간복잡도 : global variable - int * 3 = 12byte

                    local variable - bool * 100 + bool * 10 = 110byte

                    ≒ 122byte

   즉, 2^16kb 이내

5, 6) 계획 수행하기 및 회고하기

실패한 소스코드

- 중복처리를 안해줌

- 해당 코드에서는 (0, 1) (2, 3) 과 (2, 3) (0, 1) 이 다른 경우로 판단함.

#define LOCAL_TEST

#include<iostream>
using namespace std;

int n, m, cnt;

// isfriend : 두 명이 친구인지 여부
// check : 친구랑 짝이 지어졌는지 여부
// remain : 짝지을 학생이 몇명 남아있는지 여부
void dfs(bool isfriend[][10], bool check[10], int remain){
	// 짝지을 학생이 없으면 하나의 경우를 찾았으므로 cnt++
	if (remain == 0){
		cnt++;
		return;
	}

	// 짝을 지을 첫번째 학생 선택
	for (int i = 0; i < n; i++){
		if (!check[i]){

			// i 번째 학생과 친구인 학생
			for (int j = 0; j < n; j++){
				// i와 j가 친구이고 j가 다른 친구와 짝짓지 않은 경우, 친구임을 check 배열에 없데이트하고 재귀
				if (isfriend[i][j] && !check[j]){
					check[i] = check[j] = true;
					dfs(isfriend, check, remain - 2);
					check[i] = check[j] = false;
				}
			}
		}
	}

	return;
}

int main(void){
#ifdef LOCAL_TEST
	freopen("input.txt", "r", stdin);
#endif
	int T;
	cin >> T;

	while (T--){
		n = m = cnt = 0;
		cin >> n >> m;

		bool isfriend[10][10] = { false };
		bool check[10] = { false };
		for (int i = 0; i < m; i++){
			int a, b;
			cin >> a >> b;
			isfriend[a][b] = true;
		}

		dfs(isfriend, check, n);

		cout << cnt << "\n";
	}

#ifdef LOCAL_TEST
	fclose(stdin);
#endif
	return 0;
}

성공한 소스코드

- 중복처리는 시작점을 고정하는게 제일 좋음

- 단, 이 방법은 a와 b가 친구이면 isfriend[a][b] = isfriend[b][a] = true로 해줘야 (1,2) (3,0) 같은 경우를 골라낼 수 있음

- 아니면 0과 3이 친구가 아니므로 경우의 수가 빠지게 됨

※ 시간복잡도 : 학생 하나 고르는데 걸리는 시간(1) * 고른 학생과 친구인 학생 고르는데 걸리는 시간(N-1) * 두명을 제외한 학생 한명과 그 친구를 고르는데 걸리는 시간(N-3) * ... * 1= 9 * 7 * 5 * 3 * 1 = 945

   공간복잡도 : 위 공간복잡도 + 각 재귀마다 int student가 추가됨(int * (9 * 7 * 5 * 3 * 1) = 3780byte

   즉, 3920byte

#define LOCAL_TEST

#include<iostream>
using namespace std;

int n, m, cnt;

// isfriend : 두 명이 친구인지 여부
// check : 친구랑 짝이 지어졌는지 여부
// remain : 짝지을 학생이 몇명 남아있는지 여부
void dfs(bool isfriend[][10], bool check[10], int remain){
	// 짝지을 학생이 없으면 하나의 경우를 찾았으므로 cnt++
	if (remain == 0){
		cnt++;
		return;
	}

	// 짝을 지을 첫번째 고정학생 선택
	int student = 0;
	for (int i = 0; i < n; i++){
		if (!check[i]){
			student = i;
			break;
		}
	}

	// student 학생과 친구인 학생
	for (int j = 0; j < n; j++){
		// student와 j가 친구이고 j가 다른 친구와 짝짓지 않은 경우, 친구임을 check 배열에 없데이트하고 재귀
		if (isfriend[student][j] && !check[j]){
			check[student] = check[j] = true;
			dfs(isfriend, check, remain - 2);
			check[student] = check[j] = false;
		}
	}

	return;
}

int main(void){
#ifdef LOCAL_TEST
	freopen("input.txt", "r", stdin);
#endif
	int T;
	cin >> T;

	while (T--){
		n = m = cnt = 0;
		cin >> n >> m;

		bool isfriend[10][10] = { false };
		bool check[10] = { false };
		for (int i = 0; i < m; i++){
			int a, b;
			cin >> a >> b;
			isfriend[a][b] = isfriend[b][a] = true;
		}

		dfs(isfriend, check, n);

		cout << cnt << "\n";
	}

#ifdef LOCAL_TEST
	fclose(stdin);
#endif
	return 0;
}

※ 왜 종만북의 코드와 속도는 동일하지만 종만북 코드로 제출한 사람들의 코드는 0ms도 있음

   무슨 차이일까 코드를 보았더니

   눈에 띄는 차이는 cin, cout과 scanf, printf

   나중에 입출력 속도에 대해 정리된거 줍줍해와야겠음

- 알고리즘 문제 해결전략 1편 중 -

- 저작권 문제시 삭제하겠습니다 -