완전 탐색 · 알고리즘 노트

개념

완전 탐색은 답이 될 수 있는 후보를 모두 확인하여 문제를 해결하는 방법입니다. 각 후보가 조건을 만족하는지 검사하고, 문제에서 요구하는 결과를 구합니다.

조건을 만족하는 후보의 개수를 구할 때는 하나씩 세고, 가장 좋은 값을 구할 때는 지금까지 확인한 값과 비교해 갱신합니다. 예를 들어 여러 수의 쌍 중 합이 가장 큰 쌍을 찾는다면, 모든 쌍의 합을 계산하면서 가장 큰 값을 저장합니다.

먼저 무엇을 하나의 후보로 볼지 정합니다. 두 칸에 각각 $1$ 부터 $3$ 까지의 수를 적는다면, 두 칸에 적힌 수의 쌍 하나가 후보입니다. 칸의 순서를 구분하므로 $(1,2)$ 와 $(2,1)$ 은 서로 다른 후보입니다.

첫 번째 수를 하나 정한 뒤 두 번째 수를 $1,2,3$ 으로 바꾸면 다음과 같이 모든 후보를 나열할 수 있습니다.

첫 번째 수가 $1$ 인 세 후보를 확인한 뒤 $2$ 인 세 후보, $3$ 인 세 후보를 확인합니다. 첫 번째 수가 될 수 있는 값마다 두 번째 수가 될 수 있는 값을 모두 확인하므로, 가능한 아홉 쌍이 정확히 한 번씩 나옵니다.

두 수의 합이 $4$ 인 경우의 수를 구한다면, 각 후보의 두 값을 더해 $4$ 와 같은지 확인합니다.

조건을 만족하는 후보를 하나씩 세면 답은 $3$ 입니다. 이처럼 후보를 나열하는 과정과 각 후보를 검사하는 과정을 정하면 완전 탐색을 구성할 수 있습니다.

완전 탐색의 계산량은 후보 수와 후보 하나를 검사하는 비용으로 정해집니다. 두 수를 각각 $1$ 부터 $N$ 까지 고르면 후보가 $N^2$ 개이고, 각 후보에서는 덧셈과 비교를 한 번씩 수행합니다.

$N=100$ 이면 $10\,000$ 쌍, $N=100\,000$ 이면 $100$ 억 쌍을 확인해야 합니다. 입력의 최댓값으로 후보 수를 계산하여 시간 제한 안에 모두 확인할 수 있는지 판단합니다.

두 반복문으로 수의 쌍을 확인하는 경우입니다. 현재 두 수와 조건을 만족하는 개수만 저장하므로 추가 공간은 일정합니다.

연산	시간복잡도	공간복잡도
두 수의 모든 쌍 확인	$O(N^2)$	추가 $O(1)$

두 칸에 각각 $1$ 부터 $N$ 까지의 수를 적는다. 두 수의 합이 목표값과 같은 경우의 수를 구하여라. 두 칸의 순서는 구분한다.

첫째 줄에 각 칸에 적을 수 있는 수의 최댓값 $N$ 과 목표 합 $S$ 가 공백을 사이에 두고 주어진다. $1\le N\le6$ ; $2\le S\le12$ 이다.

조건을 만족하는 경우의 수를 출력한다.