2026-05-26 TIL (64일차)

알고리즘: 이진 탐색 (Binary Search) 및 파라메트릭 서치

---

이진 탐색 (Binary Search) 알고리즘

개념 및 특징

이진 탐색은 배열 내부의 데이터가 이미 “정렬”되어 있는 상황에서 특정한 데이터를 매우 빠르게 찾을 수 있는 탐색 알고리즘입니다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하기 때문에 속도가 매우 빠릅니다.

• 전제 조건: 데이터가 반드시 오름차순 또는 내림차순으로 정렬되어 있어야 합니다.
• 시간 복잡도: O(log N)
  • 단계마다 탐색 범위를 반으로 나누기 때문에, 연산 횟수는 log₂N에 비례합니다. (예: 데이터가 32개일 때 1단계 후 16개, 2단계 후 8개, 3단계 후 4개…)

동작 원리 (3가지 변수 사용)

이진 탐색은 시작점(start), 끝점(end), 중간점(mid) 세 개의 변수를 사용합니다.

1. 시작점과 끝점을 이용해 중간점 = (시작점 + 끝점) // 2 (소수점 이하 버림)을 찾습니다.
2. 중간점의 값과 찾고자 하는 값(Target)을 비교합니다.
   • Target == 중간점 값: 탐색 완료 (인덱스 반환).
   • Target < 중간점 값: 중간점보다 큰 오른쪽 범위는 볼 필요가 없으므로 끝점 = 중간점 - 1로 옮겨 왼쪽 구간을 탐색합니다.
   • Target > 중간점 값: 중간점보다 작은 왼쪽 범위는 볼 필요가 없으므로 시작점 = 중간점 + 1로 옮겨 오른쪽 구간을 탐색합니다.
3. 값을 찾거나, 시작점이 끝점보다 커질 때까지(데이터가 없을 때까지) 1~2번을 반복합니다.

---

파라메트릭 서치 (Parametric Search)

코딩 테스트에서 이진 탐색이 가장 빛을 발하는 유형입니다.

• 개념: 최적화 문제(가장 알맞은 값을 찾는 문제)를 결정 문제(Yes/No)로 바꾸어 해결하는 기법입니다.
• 적용 시점: ‘최댓값’이나 ‘최솟값’을 구하는 문제에서, 탐색 범위가 극단적으로 클 때(예: 10억, 20억) 이진 탐색을 떠올려야 합니다.
• 원리: 탐색 범위를 절반씩 좁혀가면서, “현재 이 값(중간점)으로 조건을 만족하는가?(Yes/No)”를 지속적으로 체크하며 최적의 해를 찾아갑니다.

[대표적인 예: 떡볶이 떡 만들기]

• 문제: 손님이 M 길이의 떡을 요청했을 때, 이 M을 맞추기 위한 절단기 높이(H)의 최댓값 구하기.
• 해결 알고리즘:
  1. 시작점(0)과 끝점(가장 긴 떡의 길이)을 잡고 중간점(절단기 높이)을 설정합니다.
  2. 중간점 높이로 떡을 잘랐을 때 얻는 떡의 양을 계산합니다.
  3. (조건 불만족) 떡의 양이 M보다 작다면? 더 많이 잘라야 하므로 높이를 낮춥니다. (end = mid - 1)
  4. (조건 만족) 떡의 양이 M보다 크거나 같다면? 일단 조건을 만족하므로 현재 높이를 기록(결과 저장)하고, 높이를 더 높여봅니다(덜 잘라봅니다). (start = mid + 1)
  5. 시작점이 끝점을 역전할 때까지 반복하면, 기록된 높이가 최적의 최대 높이가 됩니다.

팀 프로젝트 마무리 작업

팀 발표를 어떻게 해야할지 팀원들과 조율을 통해 틀을 잡고 시연영상을 통해 상세 설명을 하고 각자 트러블 슈팅 하나만 간단하게 적어서 발표하기로 틀을 정했습니다.