내일배움캠프 56일차 - 자료구조 & 알고리즘 10주차 : 완전 탐색
완전 탐색 - "빠짐없이 전부 확인"
가능한 모든 경우를 하나씩 확인하여 답을 찾는 방법.
이름의 유래는 Brute Force(무차별 대입) - 원래 암호학 용어.
장점: 정확성 보장 - "답이 있다면 반드시 찾는다."
단점: 경우의 수가 많으면 시간이 오래 걸린다.
비유: 방 100개짜리 호텔에서 잃어버린 열쇠 찾기. 1호부터 100호까지 다 열어보면 반드시 찾는다. 시간이 좀 걸릴 뿐.
이진 탐색 vs 완전 탐색 - 성격이 다른 문제
이진 탐색이 통하는 문제 - "정렬된 배열에서 값 찾기"
- 구조가 있다 (단조성)
- 절반을 버릴 수 있다.
- O(log n)
완전 탐색이 필요한 문제 - "비밀번호 찾기"
※경우의 수가 충분히 작으면, 완전 탐색이 최선이다.
핵심 판단 - "1초에 1억 번"
1억번 이하의 연산
- 완전 탐색이 최선 (1초 이내 해결)
1억번 초과의 연산
- 더 똑똑한 방법 필요
패턴1)순열 - "줄 세우기"
n명을 한 줄로 세우는 경우의 수: n! (n 팩토리얼)
5! = 120
10! = 약 360만
12! = 약 5억 - 1초 한계 근처
13! = 약 62억 - 불가능
12명까지는...
패턴2)조합 - "팀 뽑기"
n명 중 r명을 뽑는 경우의 수: C(n, r) = n! / (r! × (n-r)!)
C(20,5) = 15,504 -> 여유
C(30, 15) = 약 1.5억 -> 간신이 가능
C(40, 20) = 약 1,378억 -> 불가능
순열은 "순서가 있다"(ABC != BAC), 조합은 "순서가 없다"(ABC = BAC).
5명 중 3명을 줄 세우면 60가지, 그냥 뽑으면 10가지 - 6배 차이
패턴3)부분집합 - "넣거나 빼거나"
각 원소마다 "포함" 또는 "불포함" 두 가지 선택: 2^n
2^10 = 1,024
2^20 = 약 100만
2^25 = 약 3,300만 -> 약간 걸림
2^30 = 약 10억 -> 한계 초과
25개까지는 완전 탐색 가능. n이 1 증가할 때마다 경우의 수가 2배로 증가(8주차에서 본 그 곱셈 폭발)
n 순열n! 부분집합2^n 가능?
5
10
15
20
25
30
순열은 n >= 13이면 1초 초과.
부분집합은 n >= 27이면 1초 초과.
문제를 보면 먼저 경우의 수를 세라 - 완전 탐색의 첫 단추
5명을 한 줄로 세우는 방법
5명을 한 줄로 세우는 모든 경우를 만들어보자.
핵심 아이디어
첫 번째 자리에 누가 올 수 있는가? -> 5명 중 1명
첫 번째를 고정하면, 나머지...
순열의 재귀 트리 - 3명 {A,B,C}
사진 필요
...
순열의 재귀 의사 코드
순열 vs 조합 - 사고방식이 다르다
순열 (Permutation)
- 순서가 있다. (ABC != BAC)
- "한 자리를 채우고 다음 자리"
ex) 5명 중 3명 줄 세우기 -> 60가지
조합 (Combination)
- 순서가 없다.
- 포함하느냐, 안 하느냐"
ex)
조합의 재귀 트리 - {A,B,C,D}에서 2개 뽑기
(재귀 트리 사진 필요)
각 원소에서 "포함" or "미포함" 두 갈래.
총 6가지 = C(4,2)
조합의 핵심 트릭 - start 인덱스
코드 사진 필요
완전 탐색 판단 프레임
문제 발생 -> [1] 경우의 수 계산 ->
완전 탐색이 첫 번째 시도인 이유
완전 탐색은 "느린 방법"이 아니라 "가장 확실한 첫 번째 시도"
코딩 테스트의 정석:
- 먼저 완전 탐색이 가능한지 확인
- 가능하면 -> 바로 구현 (정확하고 빠르게 풀림)
- 불가능 하면 -> Level 3 기법 (백트래킹/그리디/DP 등)
완전 탐색이 유효한 경우의 특징
: n이 작다 (<= 20 정도) / "모든 경우를 확인해야 답을 보장하는" 문제 / "정답"을 확실히 찾아야 하는 경우.
CS 돋보기
조합 폭발 - n이 조금만 커져도
순열 n!의 증가 속도를 다시 보면:
n n! 의미
10 약306만 1초 이내
...
P 문제 vs NP 문제
P 문제
빠르게 풀 수 있다 (다항 시간)
정렬 O(n log n)
이진 탐색 O(log n)
최단 경로(다익스트라 O(n log n)
NP 문제
검증은 빠르지만 풀이가?
외판원(TSP) O(n!)
부분합 O(2^n)
스도쿠, 일정 짜기 등
※ 외판원 문제(TSP): N개 도시...
P = NP? - CS 최대의 미해결 문제
빠르게 검증할 수 있으면 빠르게 풀 수도 있을까?
: P = NP 문제 - 풀면 백만 달러 상금 (Cl...
Level 3으로 연결되는 세 방법
백트래킹
: 완전 탐색 + "이 길은 답 아님" 가지 치기
그리디
: 매 순간 최선의 선택으로 답 도달
DP
: 이미 계산...
실전에서는?
게임 개발
전략 게임 AI가 "최선의 수"를 찾을 때 완전 탐색을 사용한다.
체스에서 가능한 모든 수를 몇 수 앞까지 탐색하는 것이 대표적
체스의 경우의 수는 천문학적이라, 실전에서는 가지치기(pruning)를 적용 -> Level3 백트래킹
...
웹/서버
항공권 검색의 "최저가 경로" 찾기 - 경유지 조합을 완전 탐색
경유 가능한 공항 <= 10개 -> C(10,3) = 120가지 -> 순식간
A/B 테스트: 변수(버튼 색상/...
CS 전반
완전 탐색은 모든 알고리즘의 출발점.
어떤 문제든 완전 탐색으로 "정답"을 구할 수 있고, 거기서 "어떻게 줄일 것인가?"를 고민하는 것이 알고리즘 설계의 핵심.
코딩 테스트의 정석: 완전 탐색 가능 -> 바로 구현 / 불가능 -> 최적화
보안 / 암호학: "비밀번호를 완전 탐색으로 찾으려면?" - 암호 강도 측정 기준 (그래서 비밀번호 갈수록 안전)
형식 검증: 작은 입력 공간을 완전 탐색해 정확성 입증...
오늘의 핵심
완전 탐색 = "가능한 모든 경우를 빠짐없이 확인"
Brute Force. 느리지만 정확
핵심 판단: "경우의 수가 얼마인가?"
순열 / 조합/ 부분집합 생성에 재귀가 빛난다
완전 탐색은 첫 번째 시도
문제를 보면 먼저 경우의 수를 세라. 감당 가능하면 가장 확실한 방법
Level 2 완주
정렬(7) -> 재귀(8) -> 이진 탐색(9) -> 완전 탐색(10) - 알고리즘 사고의 기초 완성
댓글
댓글 쓰기