이분 탐색 (Binary Search)
- 정렬된 배열에서 탐색 구간을 절반씩 줄이며 값을 찾는 알고리즘
- *O(log N)**의 빠른 탐색 성능
- 조건을 만족하는 최소/최댓값을 찾는 문제에도 자주 사용됨
전제 조건
- 입력 배열은 반드시 오름차순 정렬되어 있어야 함
주요 활용
- 값 존재 여부 확인
- 파라메트릭 서치
- lower_bound, upper_bound 구현
구현 방식
- 반복문, 재귀 함수
- 파이썬 내장:
bisect(단 실전에서는 직접 구현 연습 필수)
분할 정복 (Divide and Conquer)
- 큰 문제를 작게 나누고(분할) → 해결(정복) → 결과를 합침
- 재귀 기반 알고리즘 설계의 핵심 패턴
대표 알고리즘
- 병합 정렬 (Merge Sort)
- 거듭제곱 계산 (aⁿ)
- 최대 구간합 문제
시간 복잡도
- O(log N) 또는 O(N log N)
특징
- 문제를 나눌 수 있어야 하며, 나눈 결과를 다시 합쳐서 정답을 만들어야 함
스택 (Stack)
- LIFO 구조: 나중에 들어온 데이터가 먼저 나감
- 시간 복잡도: O(1) (삽입, 삭제)
기본 연산
push(),pop(),peek(),is_empty()
주요 활용
- 괄호 유효성 검사
- 수식 후위 표기법 계산
- 오큰수, 탑 문제 등
파이썬 구현
- 리스트
append(),pop()
큐 (Queue)
- FIFO 구조: 먼저 들어온 데이터가 먼저 나감
- 시간 복잡도: O(1) (deque 기준)
기본 연산
enqueue(),dequeue(),peek(),is_empty()
주요 활용
- BFS 탐색
- 프린터 대기열
- 생산자-소비자 구조, 캐시 시스템
파이썬 구현
collections.deque사용append(),popleft()
우선순위 큐 (Priority Queue)
- 값의 크기(우선순위)에 따라 먼저 꺼내는 큐
- 일반 큐와 달리 최소값 또는 최대값을 빠르게 꺼낼 수 있음
- Heap 자료구조로 구현됨
시간 복잡도
- 삽입 / 삭제: O(log N)
파이썬 구현
heapq모듈 사용 (heappush(),heappop())
주요 활용
- 다익스트라 알고리즘
- K번째 큰 수
- 스케줄링, 대기열 처리 문제
연결 리스트 (Linked List)
- 각 노드가 다음 노드를 가리키는 포인터 기반의 선형 자료구조
- 중간 삽입/삭제가 O(1) 로 매우 빠름 (단 탐색은 O(N))
종류
- 단일 연결 리스트 (singly)
- 이중 연결 리스트 (doubly)
주요 활용
- LRU 캐시
- 내부적으로 큐, 스택 구현 시 활용
- 노드 삭제/삽입, 역순 연결 등
파이썬 구현
Node클래스 +LinkedList클래스 구성
해시 테이블 (Hash Table)
- Key → Hash Function → Index → Value 저장
- 탐색/삽입/삭제 평균 O(1)
주요 특징
- Key는 immutable 타입이어야 함
- 충돌이 발생할 수 있으므로 충돌 처리 필요 (chaining, open addressing 등)
파이썬 구현
dict,defaultdict,get(),in
주요 활용
- 등장 횟수 세기
- 중복 체크
- 빠른 조회, 맵핑
Week2 실전 대비 핵심 요약
| 주제 | 평균 시간 복잡도 | 주요 활용 |
|---|---|---|
| 이분 탐색 | O(log N) | 정렬 배열 탐색, 조건 만족 최소값 |
| 분할 정복 | 문제마다 다름 | 정렬, 제곱, 영역 분할 |
| 스택 | O(1) | 괄호검사, 수식변환, 오큰수 |
| 큐 | O(1) | BFS, 대기열 처리 |
| 우선순위 큐 | O(log N) | 최단경로, 실시간 정렬 |
| 연결 리스트 | 삽입/삭제 O(1), 탐색 O(N) | 캐시, 중간 삽입 |
| 해시 테이블 | 평균 O(1) | 등장 횟수, 키-값 매핑 |
복습 가이드
- 각 구조/알고리즘의 시간복잡도, 활용 사례, 구현 방식을 중심으로 다시 정리
- 파이썬 기본 모듈(
collections,heapq,bisect) 활용법 연습 - C로 전환할 경우 직접 구현 방식도 병행 학습
안녕하세요.