728x90
🔎 완전 탐색이란?
- 모든 경우의 수를 시도하여 정답을 찾는 방법
- 상대적으로 간단하지만 경우의 수가 많아지면 시간이 오래 걸림.
- 무식하게 푼다`는 의미로 Brute Force라고도 함.
완전 탐색 기법 종류
- Brute Force
- 비트 마스크
- 재귀함수
- 순열
단순 Brute-Force
- 특별한 기법 없이 for문과 if문으로 모든 경우의 수를 체크하여 답을 구함.
- 이 방법으로 해결할 수 있는 문제가 많지 않음
- 문제 일부분을 해결할 때 사용
비트마스크(Bitmask)
- 각 원소를 두 가지 상태로 분류 할 수 있을 때 사용
모든 경우의 수에서- 각각의 원소가 포함되는 경우
- 각각의 원소가 포함되지 않는 경우
- ex) 원소 n개인 집합의 부분 집합 구하기
재귀함수
재귀(Recursion) : 자기 자신을 호출한다.
함수가 자기 자신을 호출하여 작업을 수행
- 호출된 함수 스택에 저장
- 호출 완료 시, 스택에서 삭제
- for, while 같은 반복 코드를 간결하게 짤 수 있음
※ 주의 사항
사이클이 발생하지 않아야 함.- 재귀 탈출 조건이 없는 경우, 재귀함수는 계속하여 자기 자신을 호출하는
무한 루프에 갖혀 스택 오버플로우가 일어난다. - 재귀 탈출 조건을 적어주거나 재귀 발생 횟수를 정해줘야 한다.
순열
- 서로 다른 n개를 일렬로 나열하는 경우의 수 (순서有) :
n! - 서로 다른 n개 중, r개를 뽑아 일렬로 나열하는 경우의 수 (순서有) : $\frac{n!}{(r-1)!}\ =\ _{n}\mathrm{P}_{r}$
- 시간 복잡도: O(n!)
시간 복잡도가 높은 편이라 n이 한 자리 수인 경우 사용하자 - C++에서는 순열을 구하는
next_permutation()함수가 있지만
자바에는 따로 없음. (직접 구현해야 함.)
BFS/ DFS
- 너비 우선 탐색(BFS; Breadth-First Search)
하나 노드 방문 후, 인접한 모든 노드 우선 방문
- 두 노드 사이 최단 경로 구할 시, 자주 사용
- Queue를 사용하여 구현
- 깊이 우선 탐색(DFS; Depth-First Search)
하나 노드 방문 후, 그 노드의 모든 자식 노드 우선 방문
- BFS보다 검색 속도 느림
- 재귀함수 사용하여 구현
📚 References(참고 자료)
[알고리즘/Java] 완전탐색
[Java/알고리즘] 완전 탐색(Exhaustive Search) 이해하기 -1 : 정의 및 종류
[Java/알고리즘] 완전 탐색(Exhaustive Search) 이해하기 -2 : 종류 별 이해
728x90
