Skip to content

Latest commit

 

History

History
409 lines (282 loc) · 20 KB

File metadata and controls

409 lines (282 loc) · 20 KB

2주차 실습 — 복잡도 분석 실습

레포지토리 안내 | English | 한국어

최종 수정일: 2026-11-18

학습 목표:

  1. 알고리즘 실행 시간을 측정하는 재사용 가능한 타이머 유틸리티를 만들 수 있다
  2. 중복 찾기 문제에 대한 O(n²) 풀이와 O(n) 풀이를 구현하고 비교할 수 있다
  3. 복잡도 증가 곡선을 시각화하고 실험 데이터로부터 알고리즘 클래스를 식별할 수 있다
  4. 알고리즘 선택이 실제 웹 API 응답 시간에 미치는 영향을 설명할 수 있다

목차



1. 개요

1.1 실습 목표

  • 타이머 유틸리티를 만들어 실행 시간을 측정한다.
  • O(n²)와 O(n) 접근법으로 중복 찾기를 비교한다.
  • matplotlib으로 복잡도 곡선을 시각화한다.
  • 선형 탐색과 이진 탐색을 웹 API 맥락에서 비교한다.
  • 이 실습은 2주차 이론의 시간 복잡도와 Big-O 표기법을 바탕으로 하며, Python 3이 필요하다. 웹 API 절에는 선택적으로 Flask(pip install flask)가 필요하다.

실습 구성:

섹션 주제
A-1 타이머 유틸리티
A-2 중복 찾기: O(n²) → O(n)
A-3 실행 시간 그래프
B-1 웹 검색 API 비교

표 1. 실습 섹션별 주제



2. Type A: 알고리즘 구현

2.1 A-1: 타이머 유틸리티 작성

문제

목표: 다른 함수의 실행 시간을 측정하는 재사용 가능한 함수를 작성한다.

요구사항:

  • 어떤 함수와 그 인자든 받을 수 있어야 한다.
  • 함수를 여러 번 실행하여(기본 3회) 평균을 낸다.
  • 평균 경과 시간과 함수의 결과를 모두 반환한다.
  • time.perf_counter()를 사용하여 고해상도 타이밍을 수행한다.
flowchart TD
    A["measure_time(func, *args, repeat=3)"] --> B["func(*args)를 3번 실행"]
    B --> C["(평균_시간, 결과) 반환"]
Loading

그림 1. measure_time의 실행 흐름

time.perf_counter()는 Python에서 가장 정밀한 시간 측정 함수이다. time.time()보다 해상도가 높아서 매우 짧은 실행 시간도 정확하게 측정할 수 있다. 여러 번 반복 실행하는 이유는 운영체제의 스케줄링, 캐시 효과 등으로 인한 측정 노이즈를 줄이기 위해서이다.

풀이

import time

def measure_time(func, *args, repeat=3):
    """func(*args)를 여러 번 실행하고 평균 시간(초)을 반환."""
    times = []
    for _ in range(repeat):
        start = time.perf_counter()
        result = func(*args)
        end = time.perf_counter()
        times.append(end - start)
    avg = sum(times) / len(times)
    return avg, result

주의: func가 배열을 제자리에서 정렬(in-place) 하는 함수라면, 첫 실행 후 두 번째 실행에서는 이미 정렬된 배열을 받게 되어 측정이 왜곡될 수 있다. 이 경우 매 반복마다 데이터를 복사(data[:])하여 새 복사본을 전달해야 정확한 벤치마크가 된다.

# 잘못된 방법: data가 변경되어 두 번째 실행 결과가 달라진다
# 올바른 방법: data[:]로 매번 새 복사본을 만든다
data_copy = data[:]

사용법:

import random

def sum_list(lst):
    """모든 원소를 합산하는 간단한 O(n) 함수."""
    total = 0
    for x in lst:
        total += x
    return total

for n in [1_000, 10_000, 100_000, 1_000_000]:
    data = [random.randint(1, 100) for _ in range(n)]
    elapsed, _ = measure_time(sum_list, data)
    print(f"N={n:>10,}: {elapsed:.6f} sec")

*args는 Python의 가변 인자(variable arguments)이다. 이 기법을 사용하면 measure_time(my_func, arg1, arg2)처럼 어떤 함수든 인자와 함께 전달할 수 있다. _는 관례적으로 사용하지 않는 변수를 나타낸다.

2.2 A-2: 중복 찾기, O(n²)에서 O(n)으로

문제

정수 배열에 중복이 있는지 판별하라.

교실에서 이름이 겹치는 학생이 있는지 확인하는 상황을 생각할 수 있다. 완전 탐색 방법은 모든 학생을 다른 모든 학생과 일일이 비교하는 것으로, 매우 번거롭다. 똑똑한 방법은 이름을 한 명씩 불러 가면서 이미 불린 이름이면 손을 드는 것으로, 한 번의 순회로 즉시 확인할 수 있다.

두 가지 접근법:

접근법 1: 완전 탐색 O(n²)                   접근법 2: 해시 집합 O(n)
+----------------------------+          +----------------------------+
| for i in range(n):         |          | seen = set()               |
|   for j in range(i+1, n):  |          | for x in arr:              |
|     if arr[i] == arr[j]:   |          |   if x in seen:            |
|       return True          |          |     return True            |
|                            |          |   seen.add(x)              |
+----------------------------+          +----------------------------+
  모든 쌍을 비교                             한 번 순회, O(1) 조회

그림 2. 완전 탐색과 해시 집합 접근법의 비교

실습 과제:

  • 두 접근법을 모두 구현한다.
  • N = 100, 1000, 10000, 50000에서 실행 시간을 비교한다.
  • 속도 향상 비율(Speedup)을 계산한다.

완전 탐색 O(n²)

def has_duplicate_bruteforce(arr):
    """O(n²): 모든 쌍을 비교."""
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                return True
    return False

비교 횟수:

N = 5:   arr = [3, 1, 4, 1, 5]

  i=0: 비교 (0,1) (0,2) (0,3) (0,4)      4번 비교
  i=1: 비교 (1,2) (1,3) (1,4)            3번 비교
  i=2: 비교 (2,3) (2,4)                  2번 비교
  i=3: 비교 (3,4)                        1번 비교
                                    합계: 10 = n(n-1)/2

이 이중 루프 패턴은 자료구조와 알고리즘에서 매우 흔하다. 핵심은 $j = i+1$부터 시작한다는 것이다. 이렇게 하면 (i, j)와 (j, i)를 중복 비교하지 않는다. 비교 횟수 $\frac{n(n-1)}{2}$는 조합론에서 $\binom{n}{2}$(n개에서 2개를 뽑는 조합의 수)와 같다.

해시 집합 O(n)

def has_duplicate_hashset(arr):
    """O(n): 집합 사용."""
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)
    return False

작동 방식:

arr = [3, 1, 4, 1, 5]

단계 1: x=3  seen={}        → 3 추가    seen={3}
단계 2: x=1  seen={3}       → 1 추가    seen={3,1}
단계 3: x=4  seen={3,1}     → 4 추가    seen={3,1,4}
단계 4: x=1  seen={3,1,4}   → 1이 있음! True 반환

10번 비교하는 대신 4단계 만에 끝난다.

집합(set)은 파티 참석자 명단처럼 생각할 수 있다. 새 손님이 오면 명단 전체를 훑지 않고도 이름이 이미 있는지 즉시 확인할 수 있다. Python의 set도 해싱이라는 기법으로 이와 같이 동작한다.

[자료구조] 해시 테이블(Hash Table) 은 키를 해시 함수로 변환한 값을 배열의 위치로 삼아 저장하므로 삽입과 조회가 평균 O(1)이며, 해시 충돌이 많은 최악의 경우에는 O(n)이 될 수 있지만 실무에서는 거의 항상 O(1)에 동작한다(10주차에서 자세히 다룬다). Python의 set은 내부적으로 해시 테이블로 구현되어 삽입(add)과 조회(in)가 평균 O(1) 이므로, 배열에서 값을 찾는 O(n) 탐색을 대신하여 중복 찾기 전체를 O(n²)에서 O(n)으로 줄인다.

벤치마크 결과

두 함수의 실행 시간을 N = 100, 1000, 10000, 50000에서 측정하면 다음과 같은 결과를 얻는다.

         N |        O(n²) |         O(n) |   Speedup
----------------------------------------------------
       100 |     0.000150 |     0.000005 |     30.0x
     1,000 |     0.015000 |     0.000050 |    300.0x
    10,000 |     1.500000 |     0.000500 |  3,000.0x
    50,000 |    37.500000 |     0.002500 | 15,000.0x

(대략적인 값이며, 실제 결과는 다를 수 있다.)

핵심 통찰: Speedup이 N에 비례하여 증가한다.

N이 2배가 되면 O(n²)은 약 4배 느려지지만, O(n)은 약 2배만 느려진다.

핵심: 이 결과의 수학적 근거는 Speedup ≈ O(n²) / O(n), 즉 n²/n = n에 비례한다는 것이다. 즉, N이 커질수록 Speedup도 선형적으로 증가한다. 비례 상수를 1로 보면 N=50,000에서 약 50,000배가 예측되고, 실제 측정값(15,000x)은 상수 인자 차이로 그보다 작지만 N에 비례하여 커지는 경향은 같다. 표에서도 N이 10배 커질 때 Speedup이 10배 커진다. 이것이 알고리즘 선택이 중요하다는 것을 실제 데이터로 확인하는 과정이다.

실제 벤치마크에서 Speedup이 이론값(≈ n)과 다를 수 있는 이유는 다음과 같다. (1) 해시 테이블의 상수 오버헤드가 작은 N에서는 무시할 수 없고, (2) CPU 캐시 효과로 배열 순회가 예상보다 빠를 수 있으며, (3) Python의 set은 C로 구현되어 Python 이중 루프보다 상수 인자가 훨씬 작다. 이론적 복잡도와 실측값은 추세는 일치하지만 정확한 배수는 달라진다.

2.3 A-3: 실행 시간 그래프

matplotlib으로 각 복잡도 클래스의 실행 시간 증가율을 그래프로 시각화한다.

matplotlib은 Python의 대표적 데이터 시각화 라이브러리이다. 설치되어 있지 않다면 pip install matplotlib으로 설치할 수 있다.

시간
 ^
 |                                        .  O(n²)
 |                                    .
 |                                .
 |                           .
 |                      .            ....... O(n log n)
 |                .          ........
 |           .        .......
 |       .     .......
 |    . ........ . . . . . . . . . . . . .   O(n)
 | .....
 |.......................................... O(1)
 +-----------------------------------------> N

그림 3. O(1), O(n), O(n log n), O(n²)의 실행 시간 증가 곡선

O(n log n)은 병합 정렬(3주차) 같은 효율적인 정렬 알고리즘의 복잡도이다. 여기서는 O(n)과 O(n²) 사이 어디에 위치하는지 참고하기 위해 포함했다.

관찰할 점:

  • O(1)은 평평하며, 입력 크기에 무관하게 일정하다.
  • O(n)은 선형으로 증가하며, N이 2배면 시간도 2배이다.
  • O(n log n)은 선형보다 약간 빠르게 증가한다.
  • O(n²)은 극적으로 증가하며, 금방 비실용적이 된다.

핵심: 이 그래프를 직접 보면 복잡도의 차이를 실감할 수 있다. 특히 주목할 점은 O(n)과 O(n²) 사이의 간극이다. 작은 N에서는 큰 차이가 없지만, N이 커질수록 격차가 가속도로 벌어진다. 이것이 점근적 분석이 중요한 이유이다. 작은 입력에서는 느린 알고리즘도 괜찮지만, 데이터가 커지면 알고리즘의 복잡도가 결정적인 차이를 만든다.



3. Type B: 웹 코드 분석

2절에서는 알고리즘의 성능을 개별적으로 측정하고 시각화하였다. 이 절에서는 상품 검색 쿼리를 처리하는 웹 API를 통해 이러한 차이가 실제 상황에서 어떻게 나타나는지 확인한다.

3.1 B-1: 상품 검색 API 비교

설정

Flask 앱을 실행하여 웹 맥락에서 검색 전략을 비교한다.

먼저 Flask를 설치한다(pip install flask). 서버가 실행되면(보통 http://127.0.0.1:5000) 브라우저에서 접속하거나 curl http://127.0.0.1:5000/search/linear?q=abc로 테스트할 수 있다.

두 개의 엔드포인트:

엔드포인트 알고리즘 복잡도
GET /search/linear?q=name 선형 탐색 O(n)
GET /search/binary?q=name 이진 탐색 O(log n)

표 2. 선형 탐색과 이진 탐색 엔드포인트

sequenceDiagram
    participant C as 클라이언트
    participant S as 서버
    C->>S: GET /search/linear?q=abc
    Note right of S: N개 상품 전부 스캔...
    S-->>C: 찾음! (느림)
    C->>S: GET /search/binary?q=abc
    Note right of S: 정렬된 리스트에서 이진 탐색...
    S-->>C: 찾음! (빠름)
Loading

그림 4. 두 검색 엔드포인트의 요청과 응답 흐름

이진 탐색은 탐색 범위를 반복적으로 절반으로 줄이는 방식이다. 대상을 중간 원소와 비교하여 왼쪽 또는 오른쪽 절반만 탐색한다. 이 절반씩 줄이는 과정은 최대 log₂(n)번 정도면 끝난다. 자세한 내용은 4주차에서 다룬다.

Flask는 Python의 경량 웹 프레임워크이다. 여기서는 실제 웹 서비스에서 알고리즘 선택이 응답 시간에 미치는 영향을 체감하기 위해 사용한다. GET 요청의 ?q=name은 쿼리 파라미터로, 검색할 상품명을 전달한다. 선형 탐색은 모든 상품을 처음부터 끝까지 확인하고, 이진 탐색은 정렬된 데이터에서 절반씩 줄여 가며 찾는다.

차이 측정

데이터 크기를 늘려 가며 테스트한다.

N (상품 수) 선형 O(n) 이진 O(log n) 비율
100 ~0.1 ms ~0.01 ms ~10x
10,000 ~10 ms ~0.02 ms ~500x
1,000,000 ~1,000 ms ~0.03 ms ~33,000x

표 3. 상품 수에 따른 선형 탐색과 이진 탐색의 응답 시간

(근사값이며, 실제 결과는 하드웨어에 따라 다를 수 있다.)

토론 질문:

데이터가 커질수록 두 접근법의 차이는 어떻게 변하는가?

선형 탐색 시간은 N에 비례하여 증가하지만, 이진 탐색 시간은 로그적으로 증가한다. 100만 개의 상품에서 선형 탐색은 쿼리당 약 1초가 걸리며, 이는 실제 웹 서비스에서 용납할 수 없는 수준이다.

참고: 실제 서비스에서의 의미를 분석하면 다음과 같다. 웹 서비스는 보통 200ms 이내 응답을 목표로 한다. 100만 개 상품에서는 다음과 같다.

  • 선형 탐색(1,000ms)에서는 사용자가 느리다고 느끼고 이탈한다.
  • 이진 탐색(0.03ms)에서는 사용자가 즉시 응답을 받는다.

이것이 데이터베이스에서 인덱스(index) 를 만드는 이유이다. 인덱스는 본질적으로 데이터를 정렬된 상태로 유지하여 이진 탐색과 같은 빠른 탐색을 가능하게 하는 자료구조이다(실제로는 B-Tree 등 더 정교한 구조를 사용한다).

참고: 이진 탐색은 정렬된 데이터에서만 작동한다. 정렬하는 비용(O(n log n))이 문제가 되지 않느냐는 의문이 들 수 있지만, 한 번 정렬해 놓으면 이후 모든 검색이 O(log n)이므로 검색이 자주 발생하는 서비스에서는 정렬 비용을 충분히 상쇄한다. 이것이 데이터베이스가 인덱스를 미리 만들어 두는 이유이다.



4. 3주차 실습과의 연결

3주차 실습에서는 정렬 알고리즘을 구현하고 벤치마크한다.



요약

개념 핵심 요약
타이머 유틸리티 time.perf_counter()로 고해상도 시간을 측정하며, 여러 번 반복 실행하여 평균을 내면 측정 노이즈를 줄일 수 있다.
O(n²)와 O(n) 중복 찾기 완전 탐색(이중 루프)은 O(n²), 해시 집합을 쓰면 O(n)이며, Speedup이 n에 비례하므로 N이 커질수록 격차가 선형으로 커진다.
해시 테이블의 역할 set의 삽입과 조회가 평균 O(1)이므로 O(n²)를 O(n)으로 최적화하는 핵심이다.
복잡도 시각화 O(1), O(n), O(n log n), O(n²) 곡선을 그래프로 비교하면 점근적 차이가 직관적으로 드러난다.
선형 탐색과 이진 탐색 (웹 API) 선형 탐색 O(n)은 데이터가 커지면 응답 시간이 비례하여 증가하고, 이진 탐색 O(log n)은 로그적으로 증가하여 대규모 데이터에서 압도적으로 유리하다.
DB 인덱스와 정렬 이진 탐색은 정렬된 데이터가 필요하지만, 한 번 정렬(O(n log n))하면 이후 검색마다 O(log n)이므로 검색이 빈번한 서비스에서는 정렬 비용이 충분히 상쇄된다.
핵심 교훈 알고리즘 복잡도는 단순한 이론이 아니며, 특히 데이터가 커질수록 사용자 경험에 직접적인 영향을 미친다.


점검 문제

  1. 중복 찾기에서 해시 집합 접근법은 왜 O(n)이고 완전 탐색 접근법은 왜 O(n²)인가?

    정답

    완전 탐색은 j > i인 모든 쌍 (i, j) 를 비교하므로 n(n-1)/2 = Θ(n²)회의 비교를 수행한다. 반면 해시 집합 접근법은 배열을 한 번만 순회(n번 반복)하며, 매 반복에서 해시 테이블에 대해 평균 O(1) 인 in 확인과 add 연산만 수행한다. 총 작업량은 n × O(1) = O(n)이다. 점근적 속도 향상은 O(n)짜리 배열 조회를 O(1)짜리 해시 조회로 대체한 데서 나온다. 이것이 이 문제에서 set의 핵심 역할이다.

  2. 벤치마크 결과에서 O(n²) 접근법이 눈에 띄게 느려지기 시작한 입력 크기는 얼마인가? 이론적 분석과 어떻게 관련되는가?

    정답

    N = 10,000 부근에서 격차가 뚜렷이 드러난다. 완전 탐색은 약 1.5초가 걸리지만 해시 집합은 1ms 미만에 끝나, 약 3,000배의 Speedup이 측정된다. 이는 Speedup이 O(n²)/O(n), 즉 n에 비례한다는 이론적 예측과 일치하며, 비율이 N에 선형적으로 증가한다. N = 1,000에서는 약 300배, N = 50,000에서는 약 15,000배에 도달한다. 추세는 이론과 일치하지만, 정확한 배수는 상수 인자(C로 구현된 set, CPU 캐시 효과) 때문에 차이가 난다.

  3. 제자리 수정 알고리즘을 벤치마크할 때 data[:] (복사본)를 사용하는 것이 왜 중요한가?

    정답

    많은 알고리즘, 특히 정렬은 입력을 제자리에서 수정(in-place) 한다. 두 번째 실행에서는 배열이 이미 정렬되어 있어 함수가 훨씬 적은 일을 하게 되고, 측정값이 왜곡된다(실제 첫 실행보다 훨씬 빠르게 측정된다). data[:]로 매 반복마다 새 복사본을 만들면, 모든 실행이 동일한 미정렬 상태에서 시작한다. 이렇게 해야 알고리즘 자체의 비용을 우연한 상태 재사용과 분리할 수 있어, repeat 횟수에 걸친 공정한 평균을 얻을 수 있다.

  4. 웹 API 실습에서 N=100,000일 때 선형 탐색과 이진 탐색의 응답 시간 차이는 어떠했는가? 그 이유는 무엇인가?

    정답

    선형 탐색은 약 100 ms, 이진 탐색은 약 0.025 ms로 약 4,000배의 차이가 난다. 선형 탐색은 O(n)이라 10만 개 상품을 모두 스캔하지만, 이진 탐색은 O(log n)이라 정렬된 리스트에서 log₂(100,000) ≈ 17번의 비교만 수행한다. 실용적으로는 이 규모에서 이미 선형 탐색이 허용 가능한 웹 지연(latency)의 경계에 근접하지만, 이진 탐색은 여전히 즉각적이다. 이것이 데이터베이스가 인덱스(index) 를 구축하는 이유이며, 큰 테이블에서 로그 시간 조회를 가능하게 하기 위함이다.