완전 탐색 솔루션

[1. 개요]

재귀 호출 등을 이용하여 모든 경우의 수를 탐색하여 원하는 답을 구한다.

반복문 중첩 대신 재귀 호출로 해결해야 하는 이유는

물리적으로 반복문 N 번 중첩하는 코드를 작성 할 수 없기 때문이며,

재귀적으로 작성하는 편이 더 간단함.

재귀 함수는 반드시(?) 아래와 같이 구현하도록 한다.

부분 문제를 정의한다.
=> 함수의 프로토 타입을 선언 (입력, 출력)
=> 전체 문제 중 일부 문제를 해결한다.
재귀 함수의 종료를 함수 상단에 두도록 한다.
=> 보통, 함수의 입력이 배열의 인덱스로 사용 되는데,
=>> 배열의 범위를 벗어나는 입력 등인 경우 종료 시키도록 한다.
=>> 특정 조건을 만족하는 경우 종료 시키도록 한다. (가지 치기 적용을 통한 early termination 가능.)
현재 선택을 결정하고 다음 문제를 풀기 위해 재귀 호출을 한다.
=> 선택의 가지수에 따라, 시간 복잡도가 정해진다.
ex) 현재 상태에서 선택 할 수 있는 경우가 2가지 (yes or no) 이면? => O(2^N)
중복인 경우를 세지 않도록 주의 한다.
=> 특정 순서를 지키면서, ...(앞에서부터 뒤로, 위에서 부터 아래로...)

순회 할 배열의 순서가 중요하지 않은 경우, 정렬하여 접근 해볼 수 있다.

문제 조건 상 탐색 범위를 줄일 수 있다.

완전 탐색으로 풀 수 있는 문제는 보통 경우의 수가 현실적인 경우이다.

[2. 구현 패턴]

아래 예제에서 구현 시 다소 헷갈릴 수 있는 부분이 있어서 정리한다.

=== 구현 패턴 1 ===

# 매 Ai 마다 해당 원소를 선택 혹은 선택하지 않는. 단, 두가지 경우만 있는 경우

=== 구현 패턴 2 ===

# 현재 재귀에서 원소를 택하는 경우가 여러 가지 일 때,

# 혹은, 이차원 배열에서

# 혹은, 쌍을 선택해야 할 때,

# 이번 차례에서 선택이 현재 원소를 기준으로 전, 후 원소의 상태를 확인 후 결정 할 수 있을 때,

기저 사례를 정의한다.
=> 보통 index 가 배열의 범위를 벗어나는 경우이며
=> 한가지 조합이 완성되었음을 의미한다.
=> 이 조합으로 주어진 조건이 만족하는지 확인한다.
(탐색 도중에 답을 업데이트 하면 중복 처리되는 경우가 발생할 수 있다.)
반복문 내부에서 재귀를 호출한다.
=> 호출 전, 데이터를 설정하고
=> 종료 후, 설정한 데이터를 해제한다.

완전 탐색 시 한가지 조합을 찾기 위해 재귀의 한 depth 에서 선택에 따라 구현 패턴이 바뀐다(?).

부분 문제 정의 및 결과 갱신 구현 패턴 비교

아래는 구해야하는 것이 무엇인가에 따라 적용 할 만한 구현 패턴, (상황에 따라 적절히 변형 필요...)

경우의 수를 따지는 문제에서...

최대 혹은 최소를 따지는 문제에서...

[3. 예제]

test_kernelv2