망고

- 보통 재귀로 구현하며 조건이 맞지 않으면 종료한다. - DFS(깊이 우선 탐색) 기반 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. 코딩에서 반복문의 횟수까지 줄일 수 있으므로 효율적이다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 즉 답이 될만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것을 백트래킹이라고 생각하면 된다. 예를 들어 A,B,C라는 사람이 각각 순서를 정할때 가능한 모든 경우의 수를 찾는 것으로 첫번째 순서가 A일경우 ,B일경우, C일경우 각각 차례대로 따지는 식이다.

완전 탐색은 모든 경우의 수를 다 시도해 보는 것으로 상대적으로 구현이 간단하고, 해가 존재하면 항상 찾게된다. 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용하다. 📍 단순 Brute-force 단순히 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법 이 방법만을 사용하는 문제는 거의 나오지 않는다. 📍 비트마스크 (Bitmask) 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두가지 선택으로 구성되는 경우 유용하게 사용 ex) '원소가 n개인 집합의 모든 부분 집합' 을 구한다고 할 경우, 각 원소가 포함되는지 포함되지 않는지를 0,1로 구분하여 배열에 저장해둘 수 있음 📍 재귀함수 비트마스크와 마찬가지로 각 원소가 두 가지 선택지를 ..