[c++] 알고리즘 개념공부 :: 재귀호출 (완전탐색)

재귀호출

 재귀함수란 함수 내에서 자기 자신을 다시 호출하는 함수이다. 프로그래밍할 때 반복되는 작업들이 대해서는 반복문을 사용하거나 재귀함수를 이용해서 표현한다.

 

 기저 사례란 더 이상 쪼개지지 않는 가장 작은 작업으로, 이에 도달했을 때는 재귀호출을 멈추고 답을 곧장 반환해야한다. 기저 사례를 정할 때는 모든 사례의 답이 기저 사례를 이용하여 계산될 수 있도록 해야한다.

 

1. 완전 탐색

(== Brute Force, Exhaustive search)

 완전탐색은 컴퓨터의 연산능력을 이용하여 가능한 경우의 수를 모두 나열하면서 답을 찾는 알고리즘이다. 입력의 크기가 작을 때 적절한 알고리즘이며 더 빠른 알고리즘의 기반이 된다. 답을 무조건 찾을 수 있다는 장점이 있지만, 찾는데에 오랜 시간이 걸린다는 단점이 있다.

 

1.1. 방법

1. Brute Force
2. 비트 마스크
3. 순열 / 조합
4. 백트래킹
5. BFS / DFS

[비트 마스크] : https://hini7.tistory.com/101

(순열 / 조합)(백트래킹)(BFS, DFS)

 

 

(문제 풀이 추가)