2025.03.21
TIL(TODAY I LEARN)
2주차의 첫날 새로운 알고리즘 문제를 풀어보자.
-
WEEK02 :
이분 탐색, 분할 정복, 스택, 큐, 우선순위 큐, Linked List, 해시 테이블 -
재귀에 대한 알고리즘 특강을 들었다.
이분 탐색, 결정 문제, 파라메트릭 서치
🧭 개념 정리
| 용어 | 정의 | 언제 쓰이는가 |
|---|---|---|
| 이분 탐색 | 정렬된 범위에서 절반씩 잘라가며 탐색 | 값의 정확한 위치, 존재 여부 찾기 |
| 결정 문제 | 어떤 조건을 만족하는지 참/거짓을 판별 | 조건을 만족하는지 판단할 수 있을 때 |
| 파라메트릭 서치 | 결정 문제를 활용해서 최적의 값을 찾는 탐색 | 어떤 수가 "최적의 해"인지 찾고 싶을 때 |
1️⃣ 이분 탐색 (Binary Search)
✔️ 정의
정렬된 배열에서 값을 찾기 위해, 중간 값을 기준으로 절반씩 탐색 범위를 줄여가는 알고리즘
📌 조건
- 데이터가 정렬되어 있어야 함
- 시간 복잡도: O(log N)
🔍 예시
python
복사편집
arr = [1, 3, 5, 7, 9]
target = 5
- 중간값: 5 → 찾음!
2️⃣ 결정 문제 (Decision Problem)
✔️ 정의
어떤 조건을 만족하는지에 대한 "예/아니오(참/거짓)" 문제
✔️ 형태
- "이 값으로 가능합니까?"
- 조건:
True또는False로 판단
🔍 예시
"절단기 높이를 15로 했을 때, 잘린 나무 길이가 20 이상인가?"
→ 가능하면 True, 아니면 False
3️⃣ 파라메트릭 서치 (Parametric Search)
✔️ 정의
결정 문제를 활용해서 최적의 값을 찾는 탐색 기법
즉, "가능한 값들 중 가장 큰(혹은 작은) 값"을 찾기 위해 이분 탐색을 적용하는 것
📌 특징
- 탐색 대상은 값 자체 (ex. 절단기 높이, 시간, 개수 등)
- 핵심: 가능 여부를 판별하는 결정 문제를 이용
🔍 나무 자르기 문제(백준 2805) 예시로 정리
| 개념 | 설명 |
|---|---|
| 이분 탐색 | 절단기 높이(H)를 0~최댓값 범위에서 반씩 줄이며 탐색 |
| 결정 문제 | 어떤 H 값에서 잘린 나무 길이가 M 이상인지? (True/False) |
| 파라메트릭 서치 | 가능한 H 값 중 가장 큰 값 찾기 (조건 만족하는 최대값) |
🧠 요약 정리표
| 개념 | 핵심 질문 | 결과 | 사용 목적 |
|---|---|---|---|
| 이분 탐색 | 이 값이 있나? | 위치 또는 여부 | 특정 값 찾기 |
| 결정 문제 | 이 조건을 만족하나? | True / False | 조건 판별 |
| 파라메트릭 서치 | 조건 만족하는 최대/최소 값은? | 값 | 최적해 찾기 |
챗지피티가 알려준 개념들이다.
문제를 결정문제로 바꾸고 이분 탐색을 통해서 문제를 해결하는 과정.
결정문제로 바꾸는 아이디어를 떠올리는게 어렵다. 문제를 많이 풀면 해결이 되려나?
2110 - 공유기 설치
문제 링크 - https://www.acmicpc.net/problem/2110
내 코드
import sys
input = sys.stdin.readline
N, C = map(int,input().split())
houses = []
for i in range(N):
houses.append(int(input().strip()))
houses.sort()
min_dist = 1
max_dist = houses[-1] - houses[0]
result = 0
while min_dist <= max_dist:
try_dist = (min_dist + max_dist) // 2
last_installed = houses[0]
count = 1
for i in range(1, N):
if houses[i] - last_installed >= try_dist:
count += 1
last_installed = houses[i]
if count >= C:
result = try_dist
min_dist = try_dist + 1
else:
max_dist = try_dist - 1
print(result)
- 이 문제는 공유기를 설치할 수 있는 거리에 대한 이분탐색을 진행하는 것이 포인트!
- 공유기가 설치 가능한 거리를 절반부터 탐색하고 설치가 가능하면 공유기 설치 거리를 늘리고 설치가 덜되면 공유기 설치 거리를 줄인다.
- 설치 가능/불가능에 대한 결정문제로 바꾸어 생각해야함
- 매개변수탐색
알고리즘 특강(경기대 배상원 교수님)
-
알고리즘 : 목적을 위한 레시피
-
알고리즘 이전에 문제를 명확히
-
알고리즘 기술하기
자연어 → 수도 코드 → programing code
- 알고리즘 분석하기
- correctness proof : 수학적 귀납법(induction)을 통해 증명
- running time analysis : 점화식을 구하고 증명
-
Recursion(재귀)
- 모든 알고리즘은 재귀에 대한 이해가 필요
- 반복문 ↔ 재귀 서로 표현이 가능
-
Reduction
- x를 풀기위한 알고리즘을 기술할 때 y의 알고리즘을 이용한다
- 일종의 함수를 호출 / x는 y의 결과만을 받고 y의 동작과정은 몰라도 된다(blackbox)
ex) 배열 a[0-n] 에서 최솟값 찾기 → 1. 정렬하기 2. A[0] 출력
- selection 문제를 sorting 문제로 reduce
- 문제의 단계를 나눠 세부 문제로 나눔. 세부 문제의 리턴을 명확하게
-
결국 recursion은 자신 스스로의 reduction
-
결국 reduction 된 함수의 동작 과정을 신경쓰지마라!(Delegate)
- 재귀는 재귀의 요정이 해준다.
재귀에 대한 자신감을 얻고 좀더 명확해진 느낌이 든다.
^_^