C++ 알고리즘:: 완전 탐색(Brute-Force) & 백트레킹(Backtracking)

완전 탐색(Brute-Force)

 

완전히 탐색, 즉 가능한 경우의 수를 모두 조사하는 방법이다.

예시) 번호 자물쇠 (경우의 수 0000~9999). 최악의 경우 10000*1초 = 대략 166분

그러나 컴퓨터 연산속도는 1초에 1억(=10^8)

백만(1,000,000)은 10^6

 

 

완전 탐색의 장단점

 

장점: 답을 무조건 찾을 수 있다.

단점: 답을 찾는데 시간이 많이 걸린다.

따라서, 탐색할 요소가 많을 때는 다른 방법을 사용하는 것이 현명하겠지만

탐색할 요소가 적거나, N제한이 작은 경우에는 완전 탐색만큼 정확한 탐색 방법은 없다.

또한 완전 탐색 문제를 풀 때에는 시간 제한을 체크하는 것이 중요하다. 

 

 

재귀함수

 

어떤 함수에서 자기 자신을 호출하는 함수이다. (인셉션에서의 꿈 개념과 동일하다)

재귀함수에서 중요한 점은 사용할 때 탈출 조건(기저 조건- 경우의 수가 더이상 쪼개지지 않는 경우)을 명시해주어야 한다는 점이다.

또한, 이 탈출 조건 위치를 함수의 맨 앞에 세우는 것이 중요하다.

마지막에 자기를 호출한 다음으로 가는 것이 재귀함수의 중요한 성질이다.

지역변수를 설정한다는 것도 중요한 부분이다.

 

 

백트레킹

 

모든 가능한 경우의 수 중에서 현재 상태에서 가능한 후보군으로 가지를 치며 탐색하는 알고리즘이다.

예시) 배스킨라빈스 31게임.

백트레킹은 재귀함수의 성질을 이용하여 구현을 한다.

이를 가지치기라고도 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이기도 하다.

이렇게 가지치기를 얼마나 잘 하느냐에 따라 효율성이 결정되게 된다.