제2장: 알고리즘과 논리 - 정렬과 탐색

수많은 데이터를 어떻게 정렬하고 탐색하느냐에 따라 프로그램의 성능은 천차만별이 됩니다. 현대의 검색 엔진과 추천 시스템 뒤에는 고도의 정렬 및 탐색 알고리즘이 숨어 있습니다.

1. 데이터 정렬 (Sorting)

정렬은 데이터를 특정 기준(오름차순, 내림차순)에 따라 나열하는 과정입니다.

정렬의 핵심 원리: 분할 정복 (Divide & Conquer)

복잡한 문제를 작은 문제로 나누어 해결하는 방식입니다. 퀵 정렬과 병합 정렬이 이 원리를 사용하여 $O(n \log n)$이라는 효율적인 속도를 달성합니다.

2. 데이터 탐색 (Searching)

탐색은 데이터 집합에서 원하는 조건의 데이터를 찾는 과정입니다.

(1) 선형 탐색 (Linear Search)

맨 앞부터 순서대로 하나씩 비교하는 방식입니다.

• 특징: 데이터가 정렬되어 있지 않아도 사용 가능.
• 성능: $O(n)$ (데이터가 많아질수록 찾는 시간도 비례하여 증가).

(2) 이진 탐색 (Binary Search)

정렬된 데이터의 ==중간값==을 기준으로 탐색 범위를 절반씩 줄여나가는 방식입니다.

• 특징: 반드시 데이터가 정렬되어 있어야 함.
• 성능: $O(\log n)$ (데이터가 100만 개라도 단 20번의 비교로 탐색 가능).

3. 왜 알고리즘의 효율성이 중요한가?

데이터가 1,000배 늘어날 때, $O(n)$ 알고리즘은 1,000배 느려지지만, $O(n^2)$ 알고리즘은 1,000,000배 느려집니다. 알고리즘 선택은 단순한 코딩 테크닉이 아니라, 시스템의 ‘한계’를 결정하는 중요한 설계 요소입니다.

키 체크리스트

• 데이터를 정렬할 때 피벗(Pivot)값을 기준으로 좌우로 나누어 정렬하는 방식은? (정답: 퀵 정렬)
• 정렬된 데이터에서 중간값을 확인하며 탐색 범위를 계속 반으로 줄여나가는 탐색법은? (정답: 이진 탐색)
• 데이터가 $n$개일 때, 이진 탐색의 시간 복잡도는 무엇입니까? (정답: $O(\log n)$)