[ALGOS STUDY] 2023-SUMMER DAY1 Bruteforcing, Backtracking

Bruteforce

- 개념 : 가능한 모든 경우의 수를 탐색하며 요구조건에만 충족되는 결과만을 가져온다. (완전탐색)

• 구현이 쉽고 정답만을 출력한다.
• 시간 측면에서 비효율적이다.
• 모든 자료를 탐색해야하므로 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다.

 

- 완전 탐색 기법

• 단순 Bruteforce
  • 특정 기법을 사용하지 않고 모든 경우를 만들어 답을 구하는 과정
• 비트마스크 (BITMASK)
  • 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식
  • 나올 수 있는 모든 경우의 수를 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용 가능
  • 다른 자료구조에 비해 수행시간이 더 빠르다 : O(1)
  • 비트 연산자를 사용해서 코드가 간결하다.
  • 메모리를 더 적게 사용할 수 있다.
• 재귀 함수
  • 재귀함수를 통해서 문제를 만족하는 경우를 만들어내는 방식
  • 비트마스크와 마찬가지로 주로 각 원소가 포함되거나 포함되지 않는 두 가지 선택지를 가질 때 이용
• 순열
  • 완전탐색의 대표적인 유형
  • 순열에 원소를 하나씩 채워가는 방식이며, 재귀함수를 이용하거나 C++ next_permutation 함수를 사용할 수 있음.
  • 서로 다른 n개를 일렬로 나열하는 순열의 경우 n의 크기가 작아야 함.

 

- 완전 탐색 이용하기

• 입력으로 주어진 데이터의 크기가 매우 작다.
• 답의 범위가 작고, 임의의 답을 하나 선택했을 때 문제 조건을 만족하는지 역추적 가능
• 문제의 여러 조건 중 하나의 조건을 고정하면 문제 풀이가 간단해진다.

- 문제 풀이 예시 : 백준 2231 분해합 (https://www.acmicpc.net/problem/2231)

#include <iostream>
using namespace std;

int sum(int n)
{
	int result = n;
	while (n != 0)
	{
		result += n % 10;
		n /= 10;
	}
	return result;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int check = sum(i);
		if (check == n)
		{
			cout << i;
			return 0;
		}
	}
	cout << 0;
	return 0;
}

 

Backtracking

- 개념 : 해를 찾는 과정에서 해가 아니라면 되돌아가서 다시 해를 찾아가는 기법

• 기본적으로는 가능한 모든 경우의 수를 고려하는 방법이나 가지치기를 통해 효율을 올려주는 작업을 주로 사용함.
• 상태 공간을 트리로 나타낼 수 있을 때 적합한 방식
• 가지치기 : 불필요한 탐색 부분을 제거하는 방법

- 특징

• 상태공간트리에서 DFS를 진행하면서 각 노드에 대해 조건에 부합하는지 유망성을 점검함.
  • 상태공간트리 : 해를 찾기 위해 탐색할 필요가 있는 모든 후보를 포함하는 트
• 만약 해당 트리에서 조건에 맞지 않는 노드라면 가지치기 후 더 이상 탐색을 진행하지 않음.
• 해당 노드의 부모 노드로 돌아가서 다른 자식 노드를 탐색
• 노드의 유망성을 따져서 가지치기(pruning)를 통해 불필요한 경로를 조기에 차단
• 연산 시간을 줄이면서 완전 검색이 수행되도록 하는 것이 핵심으로 재귀함수를 사용해 구현

- 문제 풀이 예시 : 백준 15649 N과 M (1) (https://www.acmicpc.net/problem/15649)

#include <iostream>
using namespace std;

int n, m, arr[10];
bool visited[10];

void dfs(int k)
{
	if (k == m)
	{
		for (int i = 0; i < m; i++) cout << arr[i] << " ";
		cout << "\n";
	}
	else
	{
		for (int i = 1; i <= n; i++)
		{
			if (!visited[i])
			{
				visited[i] = true;
				arr[k] = i;
				dfs(k + 1);
				visited[i] = false;
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	dfs(0);
	return 0;
}

---

ALGOS 스터디의 경우 팀원들이 만든 자료를 바탕으로 스터디를 진행합니다. 해당 일시 자료는 제가 스터디 자료를 만들지 않았기 때문에 팀원의 자료 내 출처가 표기되었을 경우, 표기된 모든 출처를 옮겨 작성합니다. 

 

ALGOS 2023 여름방학 캠프의 경우 저는 주제 총정리 영상을 담당하였습니다. 5일동안의 주제를 간단히 정리하는 영상을 제작하였으며, 해당 글과 발표를 준비하는 데 참고한 내용의 출처는 다음과 같습니다.

 

<출처>

파이썬으로 배우는 자료구조 프로그래밍 (유석종)

https://hawaiian-pizza-it.tistory.com/39

https://hcr3066.tistory.com/26

https://chanhuiseok.github.io/posts/algo-23/

https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-Back-tracking