Week1

Week1

이 시리즈는 저희 학교내 동아리인 Tools 동아리의 친한 형이 진행하는 알고리즘 스터디를 들으며 배운 내용을 스스로 정리하며 작성해나갈 것 입니다.

Brute force

Brute force는 완전 탐색을 의미합니다. 빠르고 정확한 컴퓨터의 장점을 이용해서 모든 경우의 수를 하나씩 확인하는 것입니다. 매우 직관적이고 순진한 방법이지만 해당 방법으로 풀리는 문제들도 많습니다. 매우 어려운 문제를 마주해서 마땅한 방법이 떠오르지 않을 경우, 우선 Brute force를 사용해서 구현한 뒤 최적화를 하는 것도 매우 좋은 방법입니다.

완전 탐색 기법

• Iteration
• Recursion
• Permutation
• Bitmask

이 글에서는 Permutation까지만 설명합니다.

Iteration

모든 경우를 확인해보기 위해 반복문을 이용하는 방법으로 일반적으로 가장 구현이 간단합니다. 대신 for문이 중첩될 수록 시간 복잡도가 크게 증가합니다. 반복문으로 구현할 수 있는 경우는 중첩 횟수가 고정되어있을 경우입니다. 따라서 중첩 횟수가 가변적인 경우 반복문을 이용한 해결은 어렵습니다.

Recursion

Recursion은 즉 재귀함수로 문제를 해결하는 것을 뜻합니다. 완전 탐색으로 문제를 해결할 때 많이 사용하는 방법으로 문제 해결 방법을 재귀적으로 정의해서 해결합니다. 일반적으로 어떤 문제를 해결하기 위해 각 단계마다 수행해야 할 작업이 같을 경우 사용합니다. 이런 재귀함수를 사용할 때는 재귀함수의 종료 조건, base case가 꼭 존재해야합니다. 사실 Recursion 방법은 코드 자체는 간단해지지만 로직이 수행되는 깊이가 깊어질수록 시간복잡도가 크게 늘어나는 단점이 있습니다.

Permutation

Permutation은 완전 탐색으로 문제를 해결할 때 사용하는 방법으로 순열을 이용한 접근 방법입니다. N개의 원소 중, k개를 선택하여 확인하는 경우, N개의 원소가 주어졌을때, 원소의 순서에 따라 답이 변하는 경우 사용할 수 있습니다. C++에 경우 Algorithm 헤더에 있는 next_permutation, prev_permuation을 이용하여 완전 탐색을 구현할 수 있습니다. 이 방법에 경우 말로는 방법을 이해하기 어려우니 예제 코드를 같이 보여드리겠습니다. 밑에 문제는 백준 2309번을 Permutation을 이용해서 해결한 것입니다.

vector<int> p(2);
vector<int> seq;

int main() {
	int num;
	int sum;

	for (int i = 0; i < 9; i++) {
		cin >> num;
		seq.push_back(num);
		if (i < 7) {
			p.push_back(1);
		} 
	} // 순열을 작은 것에서 큰 것으로 순서대로 돌기 때문에 가장 작은 001111111로 먼저 배치해 준것! -> 중요!

	sort(seq.begin(), seq.end());

	do {
		sum = 0;

		for (int i = 0; i < 9; i++) {
			if (p[i]) {
				sum += seq[i];
			}
		}

		if (sum == 100) {
			for (int i = 0; i < 9; i++) {
				if (p[i]) {
					cout << seq[i] << endl;
				}
			}
			return 0;
		}
	
	} while (next_permutation(p.begin(), p.end()));

	return 0;
}