# [06-01] 완전 탐색 (Brute Force)
완전 탐색은 가능한 모든 경우를 직접 확인하여 답을 찾는 가장 확실한 방법입니다.
완전 탐색을 알아보기 전에 알고리즘 설계 기법에 대해 먼저 살펴보겠습니다.
알고리즘 설계 기법 개요
알고리즘 설계 기법은 다양한 문제를 효율적으로 해결하기 위한 체계적인 접근 방법입니다.
🎯 알고리즘 설계 기법이란
왜 설계 기법을 배우는가
프로그래밍에서 마주하는 문제는 무궁무진합니다.
하지만 놀랍게도 대부분의 문제는 몇 가지 기본 패턴으로 해결할 수 있습니다.
실생활 비유:
- 요리법: 볶음, 튀김, 조림 등의 기본 조리법으로 수많은 음식 만들기
- 건축 설계: 기본 구조 (기둥, 보, 벽)의 조합으로 다양한 건물 짓기
- 음악 작곡: 기본 화성 진행과 리듬 패턴으로 무한한 곡 만들기
알고리즘 설계 기법도 마찬가지입니다. 기본적인 몇 가지 사고 패턴을 익히면, 새로운 문제를 만나도 "아, 이건 분할 정복으로 풀면 되겠구나" 하고 접근할 수 있습니다.
설계 기법의 핵심 가치
1. 문제 해결의 틀 제공
복잡한 문제를 보고 막막할 때, "어떤 기법을 쓸까?"라고 생각하면 실마리가 보입니다.
문제: "배열에서 가장 큰 합을 가진 연속 부분 배열을 찾아라"
해결 과정: 막막함 → "음... 동적 계획법으로 접근하면?" → 점화식 세우기 → 해결!2. 최적화의 방향 제시
처음엔 느린 알고리즘이라도, 설계 기법을 바꾸면 극적으로 빨라질 수 있습니다.
완전 탐색: O(n!) → 너무 느림
분할 정복: O(n log n) → 빠름!3. 알고리즘 분석 능력 향상
남이 짠 코드를 보고 "아, 이건 그리디 알고리즘이네"라고 파악할 수 있습니다.
🎨 기법 선택 가이드
문제를 보고 기법 선택하기
문제 특성 → 추천 기법
------------------------------------------------
경우의 수가 적음 → 완전 탐색
문제를 나눌 수 있음 → 분할 정복
매 순간 최선의 선택 → 그리디
중복 계산이 많음 → 동적 계획법
제약 조건이 복잡함 → 백트래킹
최적화 + 가지치기 필요 → 분기 한정
그래프/네트워크 문제 → 그래프 알고리즘
문자열 패턴/검색 → 문자열 알고리즘복잡도로 기법 선택하기
허용 시간 경우의 수 추천 기법
------------------------------------------------
1초 10^8 이하 완전 탐색
1초 10^6 O(n log n) - 분할 정복
1초 10^4 O(n^2) - 동적 계획
1초 10^3 O(n^3) - 동적 계획주요 기법 요약
기법 핵심 아이디어 복잡도 예시
------------------------------------------------------
완전 탐색 모두 확인 O(n!), O(2^n)
분할 정복 나누어 해결 O(n log n)
그리디 지금 최선 선택 O(n), O(n log n)
동적 계획법 중복 제거 O(n), O(n^2)
백트래킹 되돌아가기 O(2^n) 개선
분기 한정 한계값 계산 최적화 문제문제 해결 프로세스
- 문제 이해 및 제약 조건 파악
- 완전 탐색 먼저 생각 (정확성 확인)
- 시간 복잡도 계산 (느리면 다른 기법)
- 문제 특성에 맞는 기법 선택
- 구현 및 테스트
- 최적화 (필요시)
🎯 완전 탐색이란 무엇인가
완전 탐색의 기본 개념
완전 탐색(Brute Force)은 문제의 모든 가능한 경우를 하나도 빠짐없이 확인하여 답을 찾는 방법입니다.
실생활 비유:
- 자물쇠 비밀번호: 0000부터 9999까지 모두 시도
- 미로 탈출: 모든 길을 다 가보기
- 카드 게임: 가능한 모든 조합 확인하기
완전 탐색의 특징:
- ✅ 확실성: 답이 존재하면 반드시 찾습니다
- ✅ 단순성: 구현이 직관적이고 쉽습니다
- ⚠️ 비효율성: 경우의 수가 많으면 매우 느립니다
# 4자리 비밀번호 찾기 (완전 탐색)
def find_password(correct_password):
"""0000 ~ 9999 모두 시도"""
for password in range(10000):
if password == correct_password:
return password
return None
# 최악의 경우 10,000번 시도!왜 완전 탐색을 배우는가
완전 탐색은 비효율적인데 왜 배울까요?
1. 정답을 보장합니다
다른 알고리즘이 복잡하거나 불확실할 때, 완전 탐색은 항상 정답을 찾습니다.
2. 기준점이 됩니다
다른 알고리즘의 성능을 비교할 때 완전 탐색을 기준으로 사용합니다.
완전 탐색: O(2^n)
최적화: O(n log n)
→ 얼마나 빨라졌는지 확인 가능!3. 실제로 충분히 빠를 수 있습니다
경우의 수가 적으면 완전 탐색이 가장 좋은 선택입니다.
경우의 수가 1,000개 → 완전 탐색으로 충분!
경우의 수가 1,000,000,000개 → 다른 방법 필요4. 다른 알고리즘의 기초입니다
백트래킹, 분기한정 등은 완전 탐색을 개선한 것입니다.
🔢 완전 탐색의 유형
유형 1: 단순 반복
가장 기본적인 형태로, 모든 경우를 순차적으로 확인합니다.
예시: 배열에서 최댓값 찾기
def find_max(arr):
"""
모든 원소를 확인하여 최댓값 찾기: 모든 원소를 한 번씩 확인
"""
max_val = arr[0]
# 모든 원소를 확인
for num in arr:
if num > max_val:
max_val = num
return max_val
# 시간복잡도: O(n)예시: 두 수의 합이 target인 쌍 찾기
def find_pair(arr, target):
"""
두 원소의 합이 target인 쌍 찾기: 모든 쌍을 확인
"""
n = len(arr)
# 모든 쌍 (i, j)를 확인
for i in range(n):
for j in range(i + 1, n):
if arr[i] + arr[j] == target:
return (arr[i], arr[j])
return None
# 시간복잡도: O(n^2)
# 쌍의 개수: n * (n-1) / 2유형 2: 순열 (Permutation)
순서가 있는 모든 배열을 생성합니다.
순열이란?
n개 중에서 r개를 순서를 고려하여 선택하는 경우의 수입니다.
*순열에서 '순서를 고려한다'는 말은 똑같은 구성 요소를 뽑더라도 나열된 차례가 다르면 서로 다른 경우로 취급하겠다는 뜻임.
*순서를 고려하지 않는 경우 조합(Combination)
[1, 2, 3]에서 2개를 뽑는 순열:
(1, 2), (1, 3)
(2, 1), (2, 3)
(3, 1), (3, 2)
총 3 × 2 = 6가지
공식: nPr = n! / (n-r)!순열 생성 방법:
def permutations(arr, r):
"""
arr에서 r개를 뽑는 모든 순열 생성: [1,2,3]에서 2개 → (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)
arr: 원소 리스트
r: 선택할 개수
Returns: 모든 순열의 리스트
방법: 재귀
- 하나를 선택하고
- 나머지에서 (r-1)개 선택
시간복잡도: O(n!)
"""
result = []
# 기저 조건: 0개를 선택하는 경우
if r == 0:
return [[]] # 빈 리스트 하나만 반환 (아무것도 선택 안 함)
# arr의 각 원소를 "첫 번째 선택"으로 시도
for i in range(len(arr)):
elem = arr[i] # 선택한 현재 원소
# 현재 원소를 제외한 나머지 원소(rest) = 현재 원소 앞의 모든 원소(arr[:i]) + 현재 원소 뒤의 모든 원소(arr[i+1:])
rest = arr[:i] + arr[i+1:] # 예: arr=[1,2,3], i=1이면 rest = [1] + [3] = [1,3]
# 나머지 원소들에서 (r-1)개를 선택하는 모든 순열
# 재귀 호출로 부분 문제 해결: 예를 들어 rest=[1,3], r-1=1이면 [[1], [3]] 반환
for p in permutations(rest, r - 1):
result.append([elem] + p) # 현재 원소를 맨 앞에 붙이기
# 예: elem=2, p=[1]이면 [2] + [1] = [2, 1]
return result
# 실행 예시로 이해하기:
# permutations([1, 2, 3], 2) 호출
# 1단계: i=0, elem=1, rest=[2,3]
# permutations([2,3], 1) 호출 → [[2], [3]] 반환
# [1] + [2] = [1,2]
# [1] + [3] = [1,3]
# 2단계: i=1, elem=2, rest=[1,3]
# permutations([1,3], 1) 호출 → [[1], [3]] 반환
# [2] + [1] = [2,1]
# [2] + [3] = [2,3]
# 3단계: i=2, elem=3, rest=[1,2]
# permutations([1,2], 1) 호출 → [[1], [2]] 반환
# [3] + [1] = [3,1]
# [3] + [2] = [3,2]
# 최종 결과: [[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]]Python 내장 함수 사용:
from itertools import permutations
arr = [1, 2, 3]
perms = list(permutations(arr, 2))
print(perms)
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]유형 3: 조합 (Combination)
순서를 고려하지 않고 선택합니다.
조합이란?
n개 중에서 r개를 순서 상관없이 선택하는 경우의 수입니다.
[1, 2, 3]에서 2개를 뽑는 조합:
{1, 2}, {1, 3}, {2, 3}
총 3가지
공식: nCr = n! / (r! × (n-r)!)
순열 vs 조합:
순열: (1, 2)와 (2, 1)은 다름
조합: {1, 2}와 {2, 1}은 같음조합 생성 방법:
def combinations(arr, r):
"""
arr에서 r개를 뽑는 모든 조합 생성: [1,2,3]에서 2개 → {1,2}, {1,3}, {2,3}
arr: 원소 리스트
r: 선택할 개수
Returns: 모든 조합의 리스트
방법: 재귀 + 인덱스
- 현재 원소를 포함하거나
- 포함하지 않거나
시간복잡도: O(2^n)
"""
result = []
def combine(start, current):
"""
조합 생성 헬퍼 함수
start: 탐색을 시작할 인덱스 (이전에 선택한 원소 다음부터 선택)
current: 현재까지 선택한 원소들
핵심 아이디어:
- start 인덱스를 유지하여 "뒤에 있는 원소만 선택" → 중복 조합 방지
- 예: [1,2]와 [2,1]은 같은 조합이므로 [1,2]만 생성
"""
# 기저 조건: r개를 모두 선택했으면
if len(current) == r:
# 현재 조합을 결과에 추가
result.append(current[:]) # current[:]는 current의 복사본(그냥 current를 추가하면 나중에 변경될 수 있음)
return
# start부터 배열 끝까지 탐색 → 이전에 선택한 원소는 다시 안 봄
for i in range(start, len(arr)):
current.append(arr[i]) # 1. 현재 원소(arr[i])를 선택에 추가
combine(i + 1, current) # 2. 다음 원소부터 탐색 (i+1)
# i+1: 같은 원소를 두 번 선택 방지 + 순서 없는 조합이므로 뒤의 원소만 고려
current.pop() # 3. 백트래킹: 선택 취소(다른 경우를 시도하기 위해 마지막 원소 제거)
combine(0, []) # 인덱스 0부터 시작, 빈 리스트에서 시작
return result
# 실행 예시로 이해하기:
# combinations([1, 2, 3], 2) 호출
# combine(0, []) 시작
# 1단계: i=0, arr[0]=1
# current = [1]
# combine(1, [1]) 호출
#
# i=1, arr[1]=2
# current = [1, 2] ← 길이가 2이므로 result에 추가
# combine(2, [1, 2]) 호출 → 즉시 return
# current = [1] (pop)
#
# i=2, arr[2]=3
# current = [1, 3] ← 길이가 2이므로 result에 추가
# combine(3, [1, 3]) 호출 → 즉시 return
# current = [1] (pop)
#
# current = [] (pop)
# 2단계: i=1, arr[1]=2
# current = [2]
# combine(2, [2]) 호출
#
# i=2, arr[2]=3
# current = [2, 3] ← 길이가 2이므로 result에 추가
# combine(3, [2, 3]) 호출 → 즉시 return
# current = [2] (pop)
#
# current = [] (pop)
# 3단계: i=2, arr[2]=3
# current = [3]
# combine(3, [3]) 호출 → range(3, 3)이므로 반복문 실행 안 됨
# current = [] (pop)
# 최종 result: [[1, 2], [1, 3], [2, 3]]
# 왜 start 인덱스가 중요한가?
# start 없이 매번 0부터 시작하면: [1,2], [2,1]이 둘 다 생성됨 (중복!)
# start를 사용하면: i=0일 때 1을 선택 → 다음은 i=1부터 (2, 3만 고려)
# i=1일 때 2를 선택 → 다음은 i=2부터 (3만 고려)
# → [1,2]는 생성되지만 [2,1]은 생성 안 됨 (중복 방지!)Python 내장 함수:
from itertools import combinations
arr = [1, 2, 3]
combs = list(combinations(arr, 2))
print(combs)
# [(1, 2), (1, 3), (2, 3)]유형 4: 부분집합 (Subset)
모든 부분집합을 생성합니다.
부분집합이란?
집합의 원소 중 일부 (또는 전부, 또는 하나도 없이)를 선택한 집합입니다.
{1, 2, 3}의 모든 부분집합: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}
총 2^3 = 8가지
공식: 2^n방법 1: 재귀
def subsets_recursive(arr):
"""
모든 부분집합 생성 (재귀)
각 원소마다:
- 포함하거나
- 포함하지 않거나
"""
result = []
def generate(index, current):
"""
index: 현재 확인할 원소의 인덱스
current: 현재까지 선택한 원소들
"""
# 모든 원소를 확인했으면
if index == len(arr):
result.append(current[:])
return
# 현재 원소를 포함하지 않음
generate(index + 1, current)
# 현재 원소를 포함
current.append(arr[index])
generate(index + 1, current)
current.pop()
generate(0, [])
return result
# 사용 예시
arr = [1, 2, 3]
print(subsets_recursive(arr)) # [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]방법 2: 비트마스크
비트마스크를 사용하면 부분집합을 매우 효율적으로 생성할 수 있습니다.
def subsets_bitmask(arr):
"""
모든 부분집합 생성 (비트마스크)
원리:
- n개 원소 → 2^n개의 부분집합을 가짐
- 2^n을 이진수로 변환 → 각 비트가 원소 포함여부를 표현(0: 없음, 1: 있음)
- 예: 3개 원소 집합 → 8개 부분집합 → 0 ~ 7을 이진수로 000 ~ 111 표현
"""
n = len(arr)
result = []
# mask는 0부터 2^n - 1까지
for mask in range(1 << n): # 1 << n = 2^n
subset = []
# 각 비트 확인
for i in range(n):
if mask & (1 << i): # i번째 비트가 1이면 arr[i] 포함
# & 연산이므로 mask와 i가 모두 1일 때 1
subset.append(arr[i])
result.append(subset)
return result
# 사용 예시
arr = [1, 2, 3] # [1번 원소, 2번 원소, 3번 원소]
print(subsets_bitmask(arr))
# 비트마스크 동작 원리: mask 이진수 3자리와 대응되는 arr 은 (3번 원소, 2번 원소, 1번 원소)
# mask=0 (000): [] * 해당 원소 없음
# mask=1 (001): [1] * 1번 원소만 존재
# mask=2 (010): [2] * 2번 원소만 존재
# mask=3 (011): [1, 2] * 1, 2번 원소 존재
# mask=4 (100): [3] * 3번 원소만 존재
# mask=5 (101): [1, 3] * 1, 3번 원소 존재
# mask=6 (110): [2, 3] * 2, 3번 원소 존재
# mask=7 (111): [1, 2, 3] * 1, 2, 3번 원소 존재비트마스크의 원리와 다양한 활용법은 다음 섹션에서 자세히 다룹니다.
🎨 비트마스크 (Bitmask) 완전 이해
플래그(Flag)란 무엇인가
비트마스크를 이해하려면 먼저 플래그(Flag) 개념을 알아야 합니다.
플래그는 켜짐/꺼짐을 나타내는 표시입니다.
실생활 예시:
전등 스위치:
- ON (1) 또는 OFF (0)
체크리스트:
할일1: ☑ (완료)
할일2: ☐ (미완료)
할일3: ☑ (완료)
→ 각 항목이 하나의 플래그프로그래밍에서 플래그:
# 일반적인 플래그 사용
has_apple = True # 사과가 있는가?
has_banana = False # 바나나가 있는가?
has_orange = True # 오렌지가 있는가?
# 문제점: 과일이 100개면? 변수 100개?여러 개의 플래그를 효율적으로 관리하는 방법이 바로 비트마스크입니다.
비트마스크란?
비트마스크(Bitmask)는 정수의 각 비트를 플래그로 사용하는 기법입니다.
마스크(mask)는 특정 비트 패턴을 사용하여 데이터의 원하는 부분만 선택, 수정, 삭제, 조회하기 위해 필터 역할을 하는 이진수입니다.
핵심 아이디어:
정수 하나로 여러 개의 플래그 관리!
10진수 5 = 2진수 101
비트 위치: 2 1 0
비트 값: 1 0 1
↓ ↓ ↓
의미: ON OFF ON예시: 과일 바구니
# 3가지 과일: 사과(0번), 바나나(1번), 오렌지(2번)
# 5 = 101(2진수)
# 비트 2: 1 → 오렌지 있음 * 오른쪽부터 3번째 비트(1)
# 비트 1: 0 → 바나나 없음 * 가운데 비트(0)
# 비트 0: 1 → 사과 있음 * 오른쪽부터 1번째 비트(1)
basket = 5 # 사과와 오렌지가 있음
# 단 하나의 정수로 3가지 상태 표현!왜 비트마스크를 사용하나?
1. 메모리 효율적
# 일반 방법: 3개 변수
has_apple = True
has_banana = False
has_orange = True
# 메모리: 3 × 1바이트 = 3바이트 (최소)
# 비트마스크: 1개 정수
basket = 5 # 0b101
# 메모리: 4바이트에 32가지 상태 저장 가능!2. 연산이 빠름
비트 연산은 CPU가 직접 지원하는 하드웨어 명령어입니다.
# 일반 방법
if has_apple and has_orange:
print("사과와 오렌지 있음")
# 비트마스크 (더 빠름)
if basket & 0b101 == 0b101:
print("사과와 오렌지 있음")3. 집합 연산이 간편
basket1 = 5 # 0b101: 사과, 오렌지
basket2 = 3 # 0b011: 사과, 바나나
# 합집합 (OR)
basket1 | basket2 # 0b111: 사과, 바나나, 오렌지
# 교집합 (AND)
basket1 & basket2 # 0b001: 사과
# 차집합 (XOR)
basket1 ^ basket2 # 0b110: 바나나, 오렌지비트 연산 기초
비트마스크를 사용하려면 비트 연산을 알아야 합니다.
AND 연산 (&): 둘 다 1이면 1
a = 5 # 0b0101
b = 3 # 0b0011
& # ------
# 0b0001 = 1
print(a & b) # 1
# 활용: 특정 비트가 켜져 있는지 확인
# "사과가 있는가?"
if basket & 0b001: # 0번 비트 확인
print("사과 있음")OR 연산 (|): 하나라도 1이면 1
a = 5 # 0b0101
b = 3 # 0b0011
| # ------
# 0b0111 = 7
print(a | b) # 7
# 활용: 특정 비트 켜기
# "바나나 추가"
basket = basket | 0b010 # 1번 비트 켜기
# 또는: basket |= 0b010XOR 연산 (^): 다르면 1
a = 5 # 0b0101
b = 3 # 0b0011
^ # ------
# 0b0110 = 6
print(a ^ b) # 6
# 활용: 특정 비트 토글 (반전)
# "사과 있으면 제거, 없으면 추가"
basket = basket ^ 0b001 # 0번 비트 반전NOT 연산 (~): 모든 비트 반전
a = 5 # 0b0101
print(~a) # -6
# 주의: Python은 부호 있는 정수라 음수로 표현됨
# 비트마스크에서는 주로 다른 연산과 함께 사용시프트 연산 (<<, >>): 비트 이동
# 왼쪽 시프트: 2를 곱하는 효과
a = 5 # 0b0101
a << 1 # 0b1010 = 10 (5 × 2)
a << 2 # 0b10100 = 20 (5 × 4)
# 오른쪽 시프트: 2로 나누는 효과
a = 5 # 0b0101
a >> 1 # 0b0010 = 2 (5 ÷ 2)
a >> 2 # 0b0001 = 1 (5 ÷ 4)
# 활용: 특정 비트 위치의 마스크 만들기
1 << 0 # 0b0001: 0번 비트만 1
1 << 1 # 0b0010: 1번 비트만 1
1 << 2 # 0b0100: 2번 비트만 1비트마스크 기본 연산
비트마스크로 자주 하는 4가지 연산입니다.
1. i번째 비트 확인 (Check)
"i번째 플래그가 켜져 있는가?"
def check_bit(mask, i):
"""
mask의 i번째 비트가 1인가?
방법:
1. (1 << i): i번째만 1인 마스크 생성
2. mask & (1 << i): i번째 비트만 추출
3. 0이 아니면 True
"""
return (mask & (1 << i)) != 0
# 예시: 과일 바구니(사과(0번), 바나나(1번), 오렌지(2번))
basket = 5 # 0b101
print(check_bit(basket, 0)) # True (사과 있음)
print(check_bit(basket, 1)) # False (바나나 없음)
print(check_bit(basket, 2)) # True (오렌지 있음)
# 동작 원리:
# basket = 5 = 0b101
# 1 << 0 = 0b001
# 0b101 & 0b001 = 0b001 ≠ 0 → True2. i번째 비트 켜기 (Set)
"i번째 플래그를 ON으로"
def set_bit(mask, i):
"""
mask의 i번째 비트를 1로 설정
방법: OR 연산으로 특정 비트만 1로 (다른 비트는 그대로 유지)
"""
return mask | (1 << i)
# 예시: 바나나 추가
basket = 5 # 0b101 (사과, 오렌지)
basket = set_bit(basket, 1) # 바나나 추가
print(basket) # 7 = 0b111 (사과, 바나나, 오렌지)
# 동작 원리:
# basket = 5 = 0b101
# 1 << 1 = 0b010
# 0b101 | 0b010 = 0b111 = 73. i번째 비트 끄기 (Clear)
"i번째 플래그를 OFF로"
def clear_bit(mask, i):
"""
mask의 i번째 비트를 0으로 설정
방법:
1. (1 << i): i번째만 1인 마스크
2. ~(1 << i): i번째만 0인 마스크
3. AND 연산으로 i번째만 0으로
"""
return mask & ~(1 << i)
# 예시: 사과 제거
basket = 5 # 0b101 (사과, 오렌지)
basket = clear_bit(basket, 0)
print(basket) # 4 = 0b100 (오렌지만)
# 동작 원리:
# basket = 5 = 0b101
# 1 << 0 = 0b001
# ~(0b001) = 0b...11110 (모든 비트 1, 0번만 0)
# 0b101 & 0b...11110 = 0b100 = 44. i번째 비트 토글 (Toggle)
"i번째 플래그를 반전 (ON ↔ OFF)"
def toggle_bit(mask, i):
"""
mask의 i번째 비트 반전
방법: XOR 연산 (같으면 0, 다르면 1)
"""
return mask ^ (1 << i)
# 예시: 사과 토글
basket = 5 # 0b101 (사과 있음)
basket = toggle_bit(basket, 0)
print(basket) # 4 = 0b100 (사과 제거)
basket = toggle_bit(basket, 0)
print(basket) # 5 = 0b101 (사과 다시 추가)
# 동작 원리:
# XOR의 특성: A ^ 0 = A, A ^ 1 = ~A
# 0b101 ^ 0b001 = 0b100
# 0b100 ^ 0b001 = 0b101비트마스크로 부분집합 생성하기
이제 비트마스크로 부분집합을 생성하는 원리를 완전히 이해할 수 있습니다.
핵심 아이디어:
원소 3개: [1, 2, 3]
부분집합 개수: 2^3 = 8개
0 ~ 7을 이진수로 표현:
0 = 000 → 아무것도 선택 안 함 → []
1 = 001 → 0번만 선택 → [1]
2 = 010 → 1번만 선택 → [2]
3 = 011 → 0, 1번 선택 → [1, 2]
4 = 100 → 2번만 선택 → [3]
5 = 101 → 0, 2번 선택 → [1, 3]
6 = 110 → 1, 2번 선택 → [2, 3]
7 = 111 → 모두 선택 → [1, 2, 3]
각 비트 = 각 원소의 포함 여부!상세한 구현:
def subsets_bitmask_explained(arr):
"""
비트마스크로 모든 부분집합 생성 (상세 설명 버전)
"""
n = len(arr)
result = []
# 0부터 2^n - 1까지 모든 정수
# 각 정수가 하나의 부분집합을 나타냄
for mask in range(1 << n): # 1 << n = 2^n
subset = []
# 각 비트 확인
for i in range(n):
if mask & (1 << i): # i번째 비트가 1이면
subset.append(arr[i]) # arr[i]를 부분집합에 포함
result.append(subset)
return result
# 상세 실행 과정
arr = ['A', 'B', 'C']
# mask=0 (0b000), i=0: 0 & 1 = 0 (포함 안 함)
# i=1: 0 & 2 = 0 (포함 안 함)
# i=2: 0 & 4 = 0 (포함 안 함)
# → []
# mask=5 (0b101), i=0: 5 & 1 = 1 ≠ 0 (포함!) → 'A'
# i=1: 5 & 2 = 0 (포함 안 함)
# i=2: 5 & 4 = 4 ≠ 0 (포함!) → 'C'
# → ['A', 'C']비트마스크 실전 팁
1. 전체 집합 표현
# n개 원소를 모두 선택한 상태
n = 3
full_set = (1 << n) - 1 # 2^n - 1
# 예: n=3
# (1 << 3) = 8 = 0b1000
# 8 - 1 = 7 = 0b0111 (모든 비트 1)2. 공집합 확인
# 아무것도 선택 안 함
if mask == 0:
print("공집합")3. 부분집합 개수
# mask에서 1인 비트 개수 (선택된 원소 수)
def count_bits(mask):
count = 0
while mask:
count += mask & 1 # 최하위 비트 확인
mask >>= 1 # 오른쪽으로 1비트 이동
return count
# 또는 Python 내장 함수
bin(mask).count('1')4. 두 집합의 합집합/교집합/차집합
set1 = 5 # 0b101
set2 = 3 # 0b011
# 합집합
union = set1 | set2 # 0b111
# 교집합
intersection = set1 & set2 # 0b001
# 차집합 (set1에만 있는 것)
difference = set1 & ~set2 # 0b100
# 대칭 차집합 (둘 중 하나에만)
symmetric_diff = set1 ^ set2 # 0b110⚡ 완전 탐색 최적화
완전 탐색 최적화는 가능한 모든 경우의 수를 확인하는 방식에서 가지치기(Pruning) 등을 적용해 불필요한 연산을 줄여 효율성을 극대화하는 기법입니다.
즉, 탐색 범위를 좁혀 시간 복잡도를 개선하는 핵심적인 알고리즘 설계 전략입니다.
가지치기 (Pruning)
가지치기는 명백히 답이 될 수 없는 경우를 미리 제외하는 기법입니다.
실생활 비유:
미로 탈출을 생각해 봅시다. 모든 길을 다 가보는 대신:
- "이 길은 막다른 골목이네" → 더 이상 안 가봄
- "이 길은 이미 와본 곳이네" → 건너뛰기
- "이 방향은 출구 반대쪽이네" → 제외
이렇게 불필요한 탐색을 미리 차단하는 것이 가지치기입니다.
전체 탐색:
├─ 경로 A (막힘) ✗
├─ 경로 B
│ ├─ B-1 (이미 방문) ✗
│ └─ B-2 (계속 탐색)
└─ 경로 C (출구 반대) ✗
가지치기로 3개 경로 제외!예시: N-Queen 문제
문제 설명:
N×N 체스판에 N개의 퀸(Queen)을 배치하되, 서로 공격할 수 없게 놓아야 합니다.
체스에서의 퀸:
퀸의 이동 규칙: 가로, 세로, 대각선 방향으로 무제한 이동 가능
4×4 체스판에서 퀸의 공격 범위:
0 1 2 3
┌───┬───┬───┬───┐
0 │ X │ X │ X │ X │
├───┼───┼───┼───┤
1 │ X │ X │ X │ X │
├───┼───┼───┼───┤
2 │ X │ X │ Q │ X │ ← (2,2)에 퀸
├───┼───┼───┼───┤
3 │ X │ X │ X │ X │
└───┴───┴───┴───┘
(2,2) 퀸이 공격 가능한 곳:
- 같은 행(2행): 모든 칸
- 같은 열(2열): 모든 칸
- 대각선: 모든 대각선 칸
→ 표시된 X 위치에는 다른 퀸을 놓을 수 없음!가지치기 없이 완전 탐색:
# 4×4 체스판에 4개 퀸 배치
# 각 칸에 놓거나 안 놓거나 → 2^16 = 65,536가지
# 문제점: 대부분이 규칙 위반!
# 예: 같은 행에 2개 퀸 → 즉시 공격 → 불가능가지치기 적용:
# 각 행마다 정확히 1개씩만 놓기
# → 4 × 4 × 4 × 4 = 256가지로 줄어듦!
# 더 나아가: 공격 범위 확인
# "이미 다른 퀸이 공격 가능한 위치면" → 건너뛰기
# → 실제 확인: 훨씬 적은 경우만 확인가지치기 구현:
def is_safe(board, row, col, n):
"""
(row, col)에 퀸을 놓을 수 있는가?
체스 규칙상 확인할 것:
1. 같은 열에 다른 퀸이 있는가?
2. 왼쪽 위 대각선에 다른 퀸이 있는가?
3. 오른쪽 위 대각선에 다른 퀸이 있는가?
(같은 행은 확인 불필요 - 각 행에 1개씩만 놓으므로)
board: board[i] = j는 i번 행의 퀸이 j번 열에 있음
row: 현재 퀸을 놓을 행
col: 현재 퀸을 놓을 열
n: 체스판 크기
"""
# 1. 같은 열 확인
# 이전 행들(0 ~ row-1)에서 같은 열에 퀸이 있는가?
for i in range(row):
if board[i] == col:
return False # 같은 열에 있음 → 공격 가능 → 불가
# 2. 왼쪽 위 대각선 확인 (\ 방향)
# (row, col)에서 왼쪽 위로 올라가면서 확인
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i] == j:
return False # 대각선에 있음 → 공격 가능 → 불가
i -= 1
j -= 1
# 3. 오른쪽 위 대각선 확인 (/ 방향)
# (row, col)에서 오른쪽 위로 올라가면서 확인
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i] == j:
return False # 대각선에 있음 → 공격 가능 → 불가
i -= 1
j += 1
# 모든 확인 통과 → 놓을 수 있음
return True
def solve_n_queens(n):
"""
N-Queen 문제 해결 (가지치기 적용)
전략:
- 각 행에 정확히 1개씩 퀸 배치
- 놓을 수 없는 위치는 미리 제외 (가지치기!)
n: 체스판 크기 (n×n)
Returns: 모든 가능한 배치의 리스트
"""
result = []
board = [-1] * n # board[i]: i번 행의 퀸이 어느 열에 있는지
def backtrack(row):
"""
row번 행에 퀸 배치
가지치기 핵심:
- 각 열을 시도하되
- is_safe로 먼저 확인
- 불가능하면 아예 시도 안 함!
"""
# 기저 조건: 모든 행에 퀸을 배치했으면 성공
if row == n:
result.append(board[:]) # 현재 배치 저장
return
# 현재 행의 각 열에 퀸을 놓아보기
for col in range(n):
# 🌟 가지치기: 놓을 수 없으면 건너뛰기
if not is_safe(board, row, col, n):
continue # 다음 열 시도
board[row] = col # 퀸 배치
backtrack(row + 1) # 다음 행으로 이동
board[row] = -1 # 복원 (백트래킹)
backtrack(0)
return result
# 4×4 체스판 예시
solutions = solve_n_queens(4)
print(f"해의 개수: {len(solutions)}") # 2가지
print("해:", solutions)
# [[1, 3, 0, 2], [2, 0, 3, 1]]
# 해석:
# [1, 3, 0, 2]는:
# 0행 1열, 1행 3열, 2행 0열, 3행 2열에 퀸 배치
# 시각화:
# 0 1 2 3
# 0 - Q - -
# 1 - - - Q
# 2 Q - - -
# 3 - - Q -가지치기의 효과:
가지치기 없이:
- 모든 경우: 2^16 = 65,536가지 확인
가지치기 적용:
- 실제 확인: 약 수십 가지만 확인
- 100배 이상 빠름!
핵심: "어차피 안 되는 경우"를 미리 걸러냄다른 예시: 숫자 합 만들기
목표 합을 만들 수 없으면 조기 종료:
def subset_sum_with_pruning(arr, target):
"""
합이 target인 부분집합 찾기 (가지치기)
가지치기:
- 현재 합이 이미 target 초과 → 더 추가해도 소용없음
- 남은 원소를 다 더해도 target 미달 → 불가능
"""
n = len(arr)
arr.sort() # 정렬하면 가지치기 효과적
def backtrack(index, current_sum, selected):
# 목표 달성
if current_sum == target:
return selected[:]
# 🌟 가지치기 1: 이미 목표 초과
if current_sum > target:
return None # 더 이상 진행 불가
# 끝까지 확인
if index == n:
return None
# 🌟 가지치기 2: 남은 것 다 더해도 부족
remaining_sum = sum(arr[index:])
if current_sum + remaining_sum < target:
return None # 불가능
# 현재 원소 포함
selected.append(arr[index])
result = backtrack(index + 1, current_sum + arr[index], selected)
if result:
return result
selected.pop()
# 현재 원소 미포함
result = backtrack(index + 1, current_sum, selected)
if result:
return result
return None
return backtrack(0, 0, [])
arr = [3, 34, 4, 12, 5, 2]
print(subset_sum_with_pruning(arr, 9)) # [3, 4, 2] 또는 [4, 5]
# 가지치기 효과:
# - "합이 20인데 target이 9?" → 즉시 중단
# - "남은 원소 합쳐도 5인데 9 필요?" → 즉시 중단가지치기 설계 팁:
- 불가능 조건 찾기: "이 경우는 절대 답이 안 돼" 파악
- 빠른 확인: 비용이 적게 드는 조건부터 확인
- 정렬 활용: 정렬하면 가지치기가 더 효과적
- 경계값 계산: 최댓값/최솟값을 미리 계산하여 활용
조기 종료 (Early Termination)
답을 찾으면 즉시 종료합니다.
def find_subset_sum(arr, target):
"""
합이 target인 부분집합 찾기
조기 종료: 하나만 찾으면 종료
"""
n = len(arr)
# 모든 부분집합 확인
for mask in range(1 << n):
subset_sum = 0
for i in range(n):
if mask & (1 << i):
subset_sum += arr[i]
# 조기 종료: 찾으면 바로 반환
if subset_sum == target:
subset = [arr[i] for i in range(n) if mask & (1 << i)]
return subset
return None
arr = [3, 34, 4, 12, 5, 2]
print(find_subset_sum(arr, 9)) # [4, 5] 또는 [3, 4, 2]🔄 정렬: 완전 탐색 접근
정렬 문제란?
정렬(Sorting)은 배열의 원소들을 특정 순서(보통 오름차순이나 내림차순)로 재배치하는 문제입니다.
왜 정렬이 중요한가?
정렬된 데이터:
- 탐색이 빠름 (이진 탐색 가능)
- 중복 제거 쉬움
- 패턴 발견 용이
- 많은 알고리즘의 전처리 단계
실생활 예시:
- 파일 목록 정렬
- 성적 순위
- 가격 비교
- 검색 결과 순위완전 탐색 방식으로 정렬하면 어떻게 될까요? 가장 단순하지만 비효율적인 기초 정렬 알고리즘들을 살펴 봅시다.
버블 정렬 (Bubble Sort)
버블 정렬은 인접한 두 원소를 비교하며 큰 것을 뒤로 보내는 방법입니다.
핵심 아이디어:
거품(Bubble)이 위로 떠오르듯, 큰 값이 배열 끝으로 이동
한 번 순회할 때마다 가장 큰 원소가 맨 뒤로 확정됨동작 과정:
[5, 2, 8, 1, 9]
1회전: 인접 원소 비교 & 교환
5, 2 비교 → [2, 5, 8, 1, 9]
5, 8 비교 → [2, 5, 8, 1, 9] (교환 X)
8, 1 비교 → [2, 5, 1, 8, 9]
8, 9 비교 → [2, 5, 1, 8, 9] (교환 X)
→ 9 확정!
2회전:
2, 5 비교 → [2, 5, 1, 8, 9]
5, 1 비교 → [2, 1, 5, 8, 9]
5, 8 비교 → [2, 1, 5, 8, 9]
→ 8 확정!
3회전:
2, 1 비교 → [1, 2, 5, 8, 9]
2, 5 비교 → [1, 2, 5, 8, 9]
→ 5 확정!
4회전:
1, 2 비교 → [1, 2, 5, 8, 9]
→ 완료!구현:
def bubble_sort(arr):
"""
버블 정렬
arr: 정렬할 배열
시간복잡도: O(n²)
- 외부 루프: n-1번
- 내부 루프: n-1번
- 총: (n-1) × (n-1) ≈ n²
공간복잡도: O(1)
- 제자리 정렬 (추가 배열 불필요)
특징:
- 가장 단순한 정렬
- 안정 정렬 (같은 값의 순서 유지)
- 실무에서는 거의 사용 안 함
"""
n = len(arr)
# 외부 루프: n-1번 회전
# 왜 n-1번? 마지막 원소는 자동 정렬됨
for i in range(n - 1):
# 최적화: 교환이 없으면 이미 정렬됨
swapped = False
# 내부 루프: 인접 원소 비교
# 왜 n-1-i? 뒤에서부터 i개는 이미 확정됨
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]: # 왼쪽이 오른쪽보다 크면 교환
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # 교환이 없었다면 이미 정렬됨 (최적화)
break
return arr
# 사용 예시
arr = [5, 2, 8, 1, 9]
print(f"정렬 전: {arr}")
bubble_sort(arr)
print(f"정렬 후: {arr}")
# 실행 과정 시각화
def bubble_sort_verbose(arr):
"""버블 정렬 과정을 출력하는 버전"""
n = len(arr)
print(f"초기 상태: {arr}")
for i in range(n - 1):
print(f"\n{i+1}회전 시작:")
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
print(f" {arr[j]} > {arr[j+1]} → 교환")
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
else:
print(f" {arr[j]} ≤ {arr[j+1]} → 유지")
print(f" 결과: {arr}")
if not swapped:
print(" → 정렬 완료!")
break
return arr
arr = [5, 2, 8, 1, 9]
bubble_sort_verbose(arr)버블 정렬의 특징:
장점:
- 구현이 매우 간단
- 안정 정렬 (같은 값의 순서 유지)
- 제자리 정렬 (추가 메모리 불필요)
단점:
- O(n²)로 매우 느림
- 교환 횟수가 많음
언제 사용?
- 교육용 (정렬 개념 이해)
- 데이터가 거의 정렬된 경우 (최적화 버전)
- 절대 실무에서는 사용 X선택 정렬 (Selection Sort)
선택 정렬은 매번 최솟값을 찾아서 앞으로 보내는 방법입니다.
핵심 아이디어:
1. 전체에서 최솟값 찾기
2. 맨 앞과 교환
3. 나머지에서 반복동작 과정:
[5, 2, 8, 1, 9]
1회전: 최솟값 1 찾기
[5, 2, 8, 1, 9] → 1과 5 교환
[1, 2, 8, 5, 9] → 1 확정!
2회전: 나머지에서 최솟값 2 찾기
[1, 2, 8, 5, 9] → 이미 위치 맞음
[1, 2, 8, 5, 9] → 2 확정!
3회전: 나머지에서 최솟값 5 찾기
[1, 2, 8, 5, 9] → 5와 8 교환
[1, 2, 5, 8, 9] → 5 확정!
4회전: 나머지에서 최솟값 8 찾기
[1, 2, 5, 8, 9] → 이미 위치 맞음
[1, 2, 5, 8, 9] → 8 확정!
→ 9 자동 확정! 완료!구현:
def selection_sort(arr):
"""
선택 정렬
arr: 정렬할 배열
시간복잡도: O(n²)
- 외부 루프: n-1번
- 내부 루프: n-1, n-2, ..., 1번
- 총: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²
공간복잡도: O(1)
특징:
- 교환 횟수가 적음 (최대 n-1번)
- 불안정 정렬 (같은 값의 순서 바뀔 수 있음)
- 어떤 경우든 항상 O(n²)
"""
n = len(arr)
# 외부 루프: 확정할 위치 (0부터 n-2까지)
for i in range(n - 1):
min_idx = i # 현재 위치를 최솟값 인덱스로 가정
# 내부 루프: i+1부터 끝까지 중 최솟값 찾기
for j in range(i + 1, n):
if arr[j] < arr[min_idx]: # 더 작은 값을 찾으면 인덱스 갱신
min_idx = j
# 최솟값을 현재 위치와 교환
# 자기 자신이면 교환 불필요
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 사용 예시
arr = [5, 2, 8, 1, 9]
print(f"정렬 전: {arr}")
selection_sort(arr)
print(f"정렬 후: {arr}")
# 실행 과정 시각화
def selection_sort_verbose(arr):
"""선택 정렬 과정을 출력하는 버전"""
n = len(arr)
print(f"초기 상태: {arr}")
for i in range(n - 1):
print(f"\n{i+1}회전:")
min_idx = i
# 최솟값 찾기
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
print(f" 최솟값: {arr[min_idx]} (인덱스 {min_idx})")
# 교환
if min_idx != i:
print(f" {arr[i]} ↔ {arr[min_idx]} 교환")
arr[i], arr[min_idx] = arr[min_idx], arr[i]
else:
print(f" 이미 위치 맞음")
print(f" 결과: {arr}")
print(f" 확정: {arr[:i+1]}")
return arr
arr = [5, 2, 8, 1, 9]
selection_sort_verbose(arr)선택 정렬의 특징:
장점:
- 교환 횟수가 적음 (최대 n-1번)
- 메모리 쓰기가 비싼 환경에서 유리
단점:
- O(n²)로 느림
- 불안정 정렬
- 어떤 경우든 항상 O(n²) (최적화 불가)
버블 정렬과 비교:
- 버블: 비교 많고 교환 많음
- 선택: 비교 많고 교환 적음
언제 사용?
- 메모리 쓰기 비용이 비쌀 때
- 교환 횟수를 최소화해야 할 때
- 실무에서는 거의 사용 X삽입 정렬 (Insertion Sort)
삽입 정렬은 이미 정렬된 부분에 새 원소를 올바른 위치에 삽입하는 방법입니다.
핵심 아이디어:
카드 게임에서 패 정리하는 방법:
1. 왼손에 정렬된 카드들
2. 오른손에서 카드 하나 뽑기
3. 왼손의 적절한 위치에 삽입동작 과정:
[5, 2, 8, 1, 9]
초기: [5] | 2, 8, 1, 9
정렬됨 | 미정렬
1회전: 2를 삽입
[5] → 2 삽입 → [2, 5] | 8, 1, 9
5를 오른쪽으로 → 2 삽입
2회전: 8을 삽입
[2, 5] → 8 삽입 → [2, 5, 8] | 1, 9
이미 위치 맞음
3회전: 1을 삽입
[2, 5, 8] → 1 삽입 → [1, 2, 5, 8] | 9
8, 5, 2를 오른쪽으로 → 1 삽입
4회전: 9를 삽입
[1, 2, 5, 8] → 9 삽입 → [1, 2, 5, 8, 9]
이미 위치 맞음
완료!구현:
def insertion_sort(arr):
"""
삽입 정렬
arr: 정렬할 배열
시간복잡도:
- 최선: O(n) - 이미 정렬된 경우
- 평균: O(n²)
- 최악: O(n²) - 역순 정렬된 경우
공간복잡도: O(1)
특징:
- 안정 정렬
- 거의 정렬된 데이터에 매우 빠름
- 온라인 알고리즘 (실시간 데이터 정렬 가능)
- Timsort (Python 기본 정렬)의 일부
"""
n = len(arr)
# i: 삽입할 원소의 인덱스 (1부터 시작)
# 왜 1부터? 0번째는 이미 "정렬됨"으로 간주
for i in range(1, n):
key = arr[i] # 삽입할 값을 임시 저장
j = i - 1 # j: 정렬된 부분에서 비교할 인덱스
# key보다 큰 원소들을 오른쪽으로 이동
# 조건 2개:
# 1. j >= 0: 배열 범위 체크
# 2. arr[j] > key: key보다 큰 원소 찾기
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # 오른쪽으로 이동
j -= 1
arr[j + 1] = key # 빈 자리에 key 삽입
return arr
# 사용 예시
arr = [5, 2, 8, 1, 9]
print(f"정렬 전: {arr}")
insertion_sort(arr)
print(f"정렬 후: {arr}")
# 실행 과정 시각화
def insertion_sort_verbose(arr):
"""삽입 정렬 과정을 출력하는 버전"""
n = len(arr)
print(f"초기 상태: {arr}")
print(f"정렬됨: [{arr[0]}] | 미정렬: {arr[1:]}\n")
for i in range(1, n):
key = arr[i]
print(f"{i}회전: {key}를 삽입")
print(f" 정렬됨: {arr[:i]}")
j = i - 1
moves = 0
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
moves += 1
arr[j + 1] = key
if moves > 0:
print(f" {moves}개 원소를 오른쪽으로 이동")
else:
print(f" 이미 위치 맞음")
print(f" 결과: {arr}")
print(f" 정렬됨: {arr[:i+1]} | 미정렬: {arr[i+1:]}\n")
return arr
arr = [5, 2, 8, 1, 9]
insertion_sort_verbose(arr)삽입 정렬의 특징:
장점:
- 거의 정렬된 데이터에 매우 빠름 (O(n))
- 안정 정렬
- 온라인 알고리즘 (실시간 처리 가능)
- 작은 배열에 효율적
- 실무에서 실제 사용됨!
단점:
- 일반적으로 O(n²)
언제 사용?
- 작은 배열 (< 50개)
- 거의 정렬된 데이터
- 온라인 정렬 (데이터가 계속 들어올 때)
- Timsort, Introsort의 부분 알고리즘
실무 활용:
- Python의 Timsort: 작은 부분에 삽입 정렬 사용
- Java의 Arrays.sort(): 작은 배열에 삽입 정렬기초 정렬 비교
시간복잡도:
알고리즘 최선 평균 최악
-----------------------------------------------
버블 정렬 O(n) O(n²) O(n²)
선택 정렬 O(n²) O(n²) O(n²)
삽입 정렬 O(n) O(n²) O(n²)특징 비교:
특징 버블 선택 삽입
--------------------------------------------------
구현 난이도 쉬움 쉬움 쉬움
안정 정렬 O X O
제자리 정렬 O O O
교환 횟수 많음 적음 중간
실무 사용 X X O (작은 배열)
거의 정렬된 데이터 느림 느림 빠름!언제 어떤 정렬?
교환 비용이 비쌀 때 → 선택 정렬 (교환 최소)
거의 정렬된 데이터 → 삽입 정렬 (O(n))
작은 배열 (< 50) → 삽입 정렬
큰 배열 → 다음 글의 병합/퀵 정렬 사용!왜 이렇게 느릴까?
공통점: 이중 반복문 → O(n²)
개선 방법: 분할 정복(병합 정렬, 퀵 정렬) 사용! → O(n log n)
예:
n = 1,000일 때
O(n²) = 1,000,000 연산
O(n log n) = 약 10,000 연산 → 100배 빠름!
다음 글에서 배울 내용!핵심 교훈:
완전 탐색 방식의 정렬:
- 모든 쌍을 비교
- 이중 반복문
- O(n²)
더 나은 방법:
- 분할 정복 (다음 글)
- 병합 정렬: O(n log n)
- 퀵 정렬: O(n log n)💡 실무 팁
완전 탐색을 사용할 때
- 경우의 수를 먼저 계산 (1초에 10^8 연산 가능)
- 1,000개 이하: 완전 탐색으로 충분
- 1,000,000개 이상: 다른 방법 고려
순열 vs 조합 선택
- 순서가 중요하면: 순열 (비밀번호, 순위)
- 순서가 무관하면: 조합 (팀 구성, 메뉴 선택)
비트마스크 활용
- 원소 개수가 20개 이하일 때 유용
- 상태를 정수로 표현할 수 있음 (동적계획법과 조합)
- 집합 연산이 필요할 때
최적화 순서
- 일단 완전 탐색으로 구현 (정확성 확인)
- 가지치기 추가 (불필요한 탐색 제거)
- 조기 종료 추가 (하나만 찾으면 충분)
- 그래도 느리면 다른 알고리즘 고려
🎯 핵심 정리
완전 탐색의 본질
- 모든 경우를 빠짐없이 확인하여 답을 찾음
- 확실하지만 비효율적일 수 있음
- 다른 알고리즘의 기준점이 됨
주요 유형
유형 경우의 수 예시
--------------------------------------------
순열 (nPr) n!/(n-r)! 비밀번호, 순위
조합 (nCr) n!/r!(n-r)! 팀 구성
부분집합 2^n 메뉴 선택
정렬 (기초) O(n²) 버블/선택/삽입정렬 알고리즘 (완전 탐색 방식)
알고리즘 시간복잡도 특징
--------------------------------------------
버블 정렬 O(n²) 가장 단순
선택 정렬 O(n²) 교환 최소
삽입 정렬 O(n²) 거의 정렬된 데이터에 빠름비트마스크
- 정수의 비트로 집합 표현
- 빠르고 메모리 효율적
- 부분집합 생성에 최적
최적화 기법
- 가지치기: 불가능한 경우 미리 제외
- 조기 종료: 답 찾으면 즉시 반환
- 중복 제거: 같은 경우 여러 번 확인 방지
시간복잡도
단순 반복: O(n), O(n^2)
순열: O(n!)
조합: O(2^n)
부분집합: O(2^n)🔗 다음 글에서는
[06-02] 분할 정복 (Divide & Conquer)
- 분할 정복의 개념: 큰 문제를 작은 문제로 나누어 해결하는 전략
- 병합 정렬: 배열을 반으로 나누어 정렬하는 O(n log n) 알고리즘
- 퀵 정렬: 피벗을 기준으로 분할하는 평균 O(n log n) 정렬
- 이진 탐색: 정렬된 배열에서 O(log n)에 원소 찾기
이전 글: [05-05] 특수 자료구조
다음 글: [06-02] 분할 정복
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자