[ 완전탐색 ] 알고리즘 내용 정리

✅ 완전탐색

- 모든 경우의 수를 다 고려해야 하는 경우를 의미 

- 시간복잡도가 큰 편!  

 

✅ 완전탐색 문제 판별법

1. 하나의 경우마다 따져야 할 게 명확한 경우

2. 어떤 상태를 구성하고, 그 상태가 특정 조건을 만족하는지 검토해야 하는 등의 문제

3. 나올 수 있는 경우의 수가 모두 탐색할 수 있을 만큼 크기가 적을 때

 

✅  완전 탐색 문제 접근 방식

1. 모든 경우를 생성할 수 있는 방법을 생각

2. 각각의 경우에 대해 그 문제의 조건을 만족하는지 체크 ( 문제에 따라 다름 )

 

✅ 완전탐색 방법

1. BruteForce : 반복문과 조건문을 이용하여 처음부터 끝까지 탐색하는 방법

2. 비트마스크

3. 순열 : 순열 시간 복잡도는 O(n!)

4. 재귀를 호출 -> 백트래킹

5. DFS / BFS

 

 

✅ 고려사항

1. 완전 탐색의 경우 주어지는 n의 크기가 작다. 

2. 답의 범위가 작고 임의의 답을 선택시 역추적이 가능!

 

 

🎯 관련 문제

1. 백준 14501 - 퇴사 : https://www.acmicpc.net/problem/14501

14501번: 퇴사

핵심 아이디어 : dfs  -> 오늘 상담하는 경우와 오늘 상담하지 않는 경우 모두 고려

 

2. 백준 2309 - 7명의 난쟁이 : https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

핵심 아이디어 : 9명 중 7명을 선택하는 모든 경우의 수를 고려해야 함. ( 글쓴이는 dfs + 백트래킹 사용 ) 

 

3. 백준 15651 - N과 M(3) : https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

핵심 아이디어 : 연속 중복 사용이 안되므로 마지막에 사용한 숫자를 알아야 함 ( 마지막에 사용한 숫자에 따라 다음 사용 가능한 경우가 달라짐 )

 

 

🎯 문제 풀어 보기!

- https://school.programmers.co.kr/learn/courses/30/parts/12230

프로그래머스

 

- https://www.acmicpc.net/workbook/view/9371

문제집: 코딩 테스트 준비 - 기초 (code.plus)

 

---