A-1: 복잡도 분석 — "이 풀이, 시간 안에 들어올까?"

안녕하세요! 코딩테스트와 CS의 길잡이, 홍순구 튜터입니다.

오늘부터 우리는 자료구조·알고리즘이라는 긴 여정을 함께 걷습니다. 언어 기초에서 변수·반복문·함수를 익히며 "문법을 읽고 쓰는 손"을 만들었다면, 이제는 그 손으로 "제한 시간 안에 정답을 내는 사고력"을 길러 볼 차례입니다. 한국 개발자 채용에는 거의 예외 없이 코딩테스트가 있고, 글로벌·대기업은 알고리즘 면접을 봅니다. 그 관문을 통과하는 힘을 20개 모듈에 걸쳐 차근차근 쌓아 갑니다.

그런데 코딩테스트를 처음 보는 사람이 가장 많이 만나는 화면이 있습니다. 바로 "시간 초과(Time Limit Exceeded)"입니다. 정답은 맞는데, 너무 느려서 떨어집니다. 분명히 돌아가는 코드인데 왜 떨어질까요?

"튜터님, 답이 맞으면 통과 아닌가요? 왜 속도까지 따지나요?"

바로 여기서 문법만 아는 사람과 알고리즘을 아는 사람이 갈립니다. 그 갈림길의 첫 도구가 오늘 배울 빅오(Big-O), 즉 복잡도 분석입니다. 빅오는 이 과목 전체를 떠받치는 척추예요. 앞으로 만날 모든 자료구조와 알고리즘마다 "이게 얼마나 빠른가"를 빅오로 따지게 됩니다.

 오늘의 여정 — "코드의 속도를 읽는 눈" 만들기

 [1] 왜 재나         →  시간 초과의 벽, 속도를 연산 횟수로 재기
 [2] 빅오 표기       →  상수·낮은 차수 버리고 성장률만 남기기
 [3] 7계급           →  O(1) · O(log n) · O(n) · O(n log n) · O(n²) · O(2ⁿ) · O(n!)
 [4] 코드에서 읽기   →  중첩=곱 · 순차=합 · 절반씩=log
 [5] 최악/평균/최선  →  무엇을 기준으로 잡나
 [6] 공간 복잡도     →  시간만이 아니라 메모리도 잰다
 [7] 1초 1억 연산    →  입력 크기 보고 복잡도 고르기 + 시간 초과 진단

자, 껍데기만 아는 코더에서 벗어나 "이 풀이가 통과할지 미리 아는 엔지니어"로 도약할 준비 되셨나요? 그럼 첫 모듈, 힘차게 출발합시다!

💡 오늘 수업의 핵심 — "정답이 맞느냐가 아니라, 입력이 커져도 시간 안에 끝나느냐 — 빅오로 코드의 속도를 읽는다"

🎯 학습 목표

• 시간·공간 복잡도를 빅오(O)로 표기하고, 상수·낮은 차수를 버려 성장률만 남깁니다.
• O(1)부터 O(n!)까지 대표 계급을 코드 모양으로 읽고, 최악·평균·최선을 구분합니다.
• "1초 ≈ 1억 연산" 잣대로 입력 크기를 보고 알맞은 복잡도를 고르며, 시간 초과(TLE)를 미리 진단합니다.

Step 1: "되긴 되는데, 시간 초과" — 왜 복잡도를 재는가

먼저 아주 흔한 상황 하나로 시작해 봅시다. "배열에 같은 값이 두 번 들어 있나?"를 판단하는 문제입니다. 가장 먼저 떠오르는 방법은 모든 쌍을 하나씩 맞대 보는 것입니다.

# complexity/growth_demo.py

def has_duplicate_pairs(nums):
    """모든 쌍을 비교해 중복을 찾는다. 시간 O(n^2) · 공간 O(1)."""
    ops = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            ops += 1                 # 비교 한 번 = 연산 한 번
            if nums[i] == nums[j]:
                return True, ops
    return False, ops


def has_duplicate_seen(nums):
    """한 번 훑으며 '이미 본 값' 집합에 있는지 확인한다. 시간 O(n) · 공간 O(n)."""
    ops = 0
    seen = set()
    for x in nums:
        ops += 1                     # 원소 하나당 처리 한 번
        if x in seen:
            return True, ops
        seen.add(x)
    return False, ops

두 함수는 같은 답을 냅니다. 하지만 has_duplicate_pairs는 모든 쌍을 맞대느라 반복문이 두 겹이고, has_duplicate_seen은 "이미 본 값"을 기록해 두며 딱 한 번만 훑습니다. (집합 set이 어떻게 한 번에 찾아 주는지, 그 내부 원리는 B-3 해시 테이블에서 직접 만들어 봅니다. 오늘은 "한 번만 훑는 더 빠른 길이 있다"는 사실만 봅니다.)

그럼 이 둘의 차이를 속도로 재 볼까요? 여기서 중요한 점이 하나 있습니다. 속도를 "몇 초 걸렸나"로 재면 안 됩니다. 같은 코드라도 빠른 컴퓨터에선 0.1초, 느린 노트북에선 1초가 나오니까요. 그래서 우리는 "입력 크기 n에 대해 연산을 몇 번 하는가"로 잽니다. 연산 횟수는 컴퓨터를 안 타는, 알고리즘 자체의 성질이거든요.

중복이 없는 입력(끝까지 다 봐야 하는 최악의 경우)을 넣고, n을 키우며 두 풀이의 연산 횟수를 세어 봤습니다.

차이가 보이시나요? n을 10에서 5,000으로 500배 키웠더니, 두 겹 반복은 약 28만 배(대략 500² = 25만 배 꼴)로 폭발했고, 한 번 훑기는 딱 500배만 늘었습니다. 입력이 조금만 커져도 두 풀이의 운명이 갈립니다. 10만 개쯤 들어오면 두 겹 반복은 100억 번을 넘겨 시간 초과로 떨어지고, 한 번 훑기는 10만 번으로 가뿐히 통과합니다.

이렇게 입력 크기 n이 커질 때 연산 횟수가 어떤 속도로 늘어나는지를 나타내는 표기가 빅오(Big-O), 기호로 O(...)입니다. 두 겹 반복은 O(n²), 한 번 훑기는 O(n)이라고 적습니다. 빅오를 읽을 줄 알면, 코드를 제출하기 전에 통과 여부를 가늠할 수 있습니다.

💡 한 줄 정리

속도는 초가 아니라 연산 횟수로 잰다. 입력 n이 커질 때 연산이 늘어나는 속도가 빅오 — O(n²)는 입력이 커질수록 O(n)보다 가파르게 폭발한다.

Step 2: "3n+5를 그냥 n이라 부르는 이유" — 빅오(O) 표기

빅오에는 과감한 규칙이 하나 있습니다. 최고차항만 남기고, 상수배와 낮은 차수는 버린다는 것입니다. 예를 들어 어떤 풀이가 3n² + 5n + 100번 연산한다면, 빅오로는 그냥 O(n²)라고 적습니다. 3도 버리고, 5n도 버리고, 100도 버립니다.

너무 대충 같나요? 그런데 이 과감함에는 분명한 이유가 있습니다. 입력 n이 커지면, 최고차항이 나머지를 압도하기 때문입니다. Step 1의 has_duplicate_pairs는 실제로 n(n-1)/2번, 즉 0.5n² - 0.5n번 비교합니다. 여기서 최고차항 0.5n²이 전체에서 차지하는 비중을 볼까요?

n이 커질수록 낮은 차수 -0.5n의 영향이 1%, 0.1%로 사라집니다. 상수배 0.5도 마찬가지예요. O(n²)와 O(100n²)는 입력이 충분히 커지면 둘 다 "n의 제곱에 비례해 커진다"는 같은 운명을 따릅니다. 그래서 빅오는 세부 숫자를 지우고 성장률만 봅니다. 코드의 큰 그림을 빠르게 읽기 위한 일부러의 단순화인 셈입니다.

⚠️ 단, 상수를 버린다고 실측 속도까지 똑같다는 뜻은 아닙니다. 같은 O(n)이라도 상수가 큰 풀이는 실제로 더 느립니다. 입력이 작을 땐 오히려 상수가 결과를 좌우하기도 하고요. 이 경계는 마지막 Step과 생각해볼 주제에서 다시 짚겠습니다. 빅오는 "큰 입력에서의 성장률"을 보는 도구라는 점을 기억해 두세요.

💡 한 줄 정리

빅오는 최고차항만 남긴다 — 3n² + 5n + 100 → O(n²). 입력이 커지면 최고차항이 나머지를 압도하므로, 상수·낮은 차수를 버려도 성장률은 그대로다.

Step 3: "복잡도 7계급" — O(1)부터 O(n!)까지 코드 모양으로

이제 자주 만나는 복잡도들을 한데 모아 보겠습니다. 빠른 것부터 느린 것까지 일곱 계급이 있는데, 각각 코드 모양과 짝지어 외워 두면 평생 씁니다.

# complexity/big_o_shapes.py

def logarithmic(n):
    """O(log n) — 남은 범위를 매번 반으로 줄인다."""
    ops = 0
    while n > 1:
        n //= 2                      # 절반으로
        ops += 1
    return ops


def quadratic(n):
    """O(n^2) — 모든 쌍을 본다 (반복문 안에 반복문)."""
    ops = 0
    for _ in range(n):
        for _ in range(n):
            ops += 1
    return ops

logarithmic은 남은 범위를 매번 절반으로 접습니다. 1,000개를 절반씩 줄이면 10번이면 1이 됩니다. 100만 개도 20번이면 끝나요. 이렇게 "반으로 줄이는 구조"가 O(log n)입니다. quadratic은 반복문이 두 겹이라, 바깥이 n번 돌 때마다 안쪽이 n번 도니 n × n = n²번입니다.

나머지 계급도 코드 모양으로 정리하면 이렇습니다.

• O(1) — 입력 크기와 무관하게 정해진 횟수만. 배열의 첫 원소 보기, 딕셔너리 한 번 조회.
• O(n) — 처음부터 끝까지 한 번 훑기. 합 구하기, 최댓값 찾기.
• O(n log n) — n번 훑기를 log n 단계만큼. 좋은 정렬(병합·퀵)의 속도 (D-1에서 직접 구현).
• O(2ⁿ) — 매 단계 경우의 수가 두 배. 가지치기 없는 완전탐색 (E-1에서 만남).
• O(n!) — 가능한 모든 순서(순열)를 만들기. 외판원 문제의 단순 풀이.

실제로 각 계급이 입력 n=16에서 연산을 몇 번 하는지 세어 봤습니다.

겨우 16밖에 안 되는 입력인데 O(2ⁿ)는 벌써 13만을 넘고, O(n!)은 8만 넣어도 4만이 넘습니다. 이 둘은 입력이 조금만 커져도 손쓸 수 없이 폭발하니, 보이면 "다른 길이 있나?"부터 의심해야 합니다. 입력이 커질 때 각 계급이 어떻게 벌어지는지 한눈에 비교하면 이렇습니다.

빠른 정도를 한 줄로 세우면 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)입니다. 이 순서가 머릿속에 있으면 "어떤 풀이를 골라야 하나"의 절반이 잡힙니다.

💡 한 줄 정리

일곱 계급을 코드 모양으로 — 절반씩=O(log n), 한 번 훑기=O(n), 두 겹 반복=O(n²), 두 배씩=O(2ⁿ). O(2ⁿ)·O(n!)은 입력이 작아도 폭발한다.

Step 4: "반복문을 보면 빅오가 보인다" — 코드에서 읽기

이제 코드를 보고 빅오를 읽어내는 법입니다. 규칙은 단순합니다.

• 반복문 한 겹 = O(n) — n번 도니까.
• 중첩 반복 = 곱 — 바깥 n번 × 안쪽 n번 = O(n²). 세 겹이면 O(n³).
• 순차 반복 = 합, 큰 쪽 — 반복문 두 개가 따로 돌면 O(n) + O(n) = O(2n) = O(n). 더해도 차수는 안 오릅니다.
• 반으로 줄이기 = O(log n) — 절반씩 접는 while.

곱과 합을 가르는 게 핵심입니다. "반복문이 두 개니까 무조건 n²"이 아니라, 안에 들어 있으면(중첩) 곱, 나란히 있으면(순차) 합입니다. 예를 들어 n번 훑기를 log n 단계만큼 반복하면 곱해져서 O(n log n)이 됩니다.

# complexity/big_o_shapes.py

def linearithmic(n):
    """O(n log n) — n번 훑기를 log n 단계만큼 반복한다."""
    ops = 0
    step = n
    while step > 1:
        for _ in range(n):           # 각 단계마다 n번
            ops += 1
        step //= 2                   # 단계 수는 log n
    return ops

바깥 while은 step을 절반씩 줄이니 log n 단계, 그 안에서 for가 매번 n번 도니, 곱하면 n × log n입니다. 좋은 정렬들이 바로 이 속도예요.

이 곱셈 규칙이 Step 1의 폭발을 설명합니다. has_duplicate_pairs의 두 겹 반복이 곱해져 O(n²)가 됐고, 그래서 n을 500배 키우자 연산이 500²인 25만 배 꼴로 터진 겁니다. 반대로 has_duplicate_seen은 한 겹이라 딱 n배만 늘었고요.

그럼 연산 횟수를 알면 시간도 어림할 수 있을까요? 대략 1초에 1억 번 연산한다고 보면, n=5,000에서의 1,249만 번은 0.2초쯤입니다. 이 "1초 1억" 잣대를 Step 7에서 본격적으로 다룹니다 — 코딩테스트에서 가장 자주 쓰는 도구거든요.

💡 한 줄 정리

코드에서 빅오 읽기: 중첩 = 곱, 순차 = 합(큰 쪽), 반으로 줄이기 = log. 반복문이 두 개여도 나란히 있으면 O(n), 포개져 있으면 O(n²).

Step 5: "운이 좋을 때 vs 나쁠 때" — 최악·평균·최선

같은 알고리즘이라도 입력에 따라 빠를 때와 느릴 때가 있습니다. 앞에서부터 하나씩 찾는 선형 탐색으로 보겠습니다.

# complexity/search_cases.py

def linear_search(nums, target):
    """앞에서부터 target을 찾는다. (찾은 위치, 비교 횟수)를 돌려준다."""
    ops = 0
    for i, x in enumerate(nums):
        ops += 1                     # 비교 한 번
        if x == target:
            return i, ops
    return -1, ops                   # 끝까지 못 찾음

길이 100짜리 배열에서 찾는 값의 위치를 바꿔 가며 비교 횟수를 세어 봤습니다.

운이 좋아 맨 앞에서 찾으면 단 1번(O(1)), 운이 나빠 맨 끝이거나 아예 없으면 끝까지 100번(O(n))입니다. 평균을 내도 (n+1)/2라 상수배 1/2를 떼면 여전히 O(n)이고요.

그럼 우리는 보통 어느 경우를 기준으로 빅오를 말할까요? 최악입니다. 코딩테스트 채점은 가장 까다로운 입력으로 들어오고, 우리는 "어떤 입력이 와도 최소한 이만큼 안에는 끝난다"를 보장해야 하니까요. 그래서 별다른 말이 없으면 빅오는 곧 최악의 경우를 가리킵니다.

참고로 면접에서 가끔 묻는 기호 구분만 한 줄로 짚자면, 상한을 O(빅오), 하한을 Ω(오메가), 둘이 같을 때를 Θ(세타)라고 합니다. 실무·코테에서는 거의 항상 상한인 O를 씁니다.

💡 한 줄 정리

같은 알고리즘도 입력에 따라 최선·평균·최악이 다르다. 빅오는 보통 최악을 기준으로 잡는다 — "어떤 입력이 와도 이건 보장된다"를 말하기 위해서.

Step 6: "시간만 비싼 게 아니다" — 공간 복잡도

지금까지 시간(연산 횟수)만 봤지만, 메모리도 빅오로 잽니다. 이걸 공간 복잡도라고 합니다. 기준은 "입력 말고 추가로 얼마나 더 쓰나"예요. 같은 "배열 뒤집기"를 두 가지로 짜 보겠습니다.

# complexity/space_demo.py

def reverse_in_place(nums):
    """제자리 뒤집기 — 새 배열 없이 입력 안에서 양 끝을 맞바꾼다. 추가 공간 O(1)."""
    i, j = 0, len(nums) - 1
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]   # 임시 변수 없이 교환
        i, j = i + 1, j - 1
    return nums


def reverse_copy(nums):
    """복사 뒤집기 — 크기 n짜리 새 배열을 만들어 채운다. 추가 공간 O(n)."""
    result = []
    for x in reversed(nums):
        result.append(x)             # 원소 n개를 새 배열에 쌓는다
    return result

reverse_in_place는 입력 배열 안에서 양 끝을 맞바꾸기만 합니다. 추가로 쓰는 건 인덱스 변수 i, j 두 개뿐이라, 입력이 100만 개든 1억 개든 추가 메모리는 그대로입니다. 이게 O(1) 공간입니다. 반대로 reverse_copy는 크기 n짜리 새 배열을 하나 더 만드니, 입력에 비례해 메모리를 더 씁니다. 이게 O(n) 공간이고요.

실제로 추가로 잡은 메모리의 정점을 재 봤습니다.

제자리 뒤집기는 입력이 100배 커져도 추가 메모리가 거의 0으로 평평한데, 복사 뒤집기는 n에 비례해 8KB → 80KB → 800KB로 또박또박 늘어납니다. 두 풀이 모두 시간은 O(n)으로 같지만, 공간이 다른 겁니다. 여기서 시간↔공간 트레이드오프의 첫 맛을 봅니다. 메모리를 더 써서 시간을 버는 기법(같은 계산을 저장해 두고 재활용하는 메모이제이션)은 동적 계획법(E-4)에서 본격적으로 만납니다.

코딩테스트도 시간 제한과 함께 메모리 제한(보통 256MB쯤)을 둡니다. 시간은 통과하는데 메모리 초과로 떨어지는 경우도 있으니, 큰 입력에서는 "굳이 새 배열을 또 만들 필요가 있나?"를 한 번 점검하는 습관이 좋습니다.

💡 한 줄 정리

공간 복잡도는 입력 외에 추가로 쓰는 메모리를 빅오로 잰 것. 제자리 처리=O(1), 새 배열을 만들면=O(n). 시간이 같아도 공간은 다를 수 있다.

Step 7: "1초에 1억 번" — 입력 크기로 복잡도 고르기 + 시간 초과 진단

드디어 오늘의 결론입니다. 코딩테스트에서 문제를 받으면 가장 먼저 하는 일이 입력 제한을 보고 허용 복잡도를 가늠하는 것입니다. 그 잣대가 "1초 ≈ 1억(10⁸) 연산"이에요. 컴퓨터가 1초에 대략 1억 번쯤 단순 연산을 한다고 보면, 각 복잡도가 1초 안에 감당하는 입력 크기 n의 한계가 나옵니다.

이 표를 거꾸로 쓰면 강력한 도구가 됩니다. 문제의 입력 제한을 넣으면 "어떤 복잡도까지 허용되나"가 바로 나오거든요. 실제로 n을 넣어 1초 안에 드는 복잡도만 추려 봤습니다.

핵심은 가운데 줄입니다. 문제에 n ≤ 100,000이 보이면, O(n²)는 100억 번이라 시간 초과예요. 그러니 "O(n log n) 이하로 풀어야 한다"가 곧장 읽혀야 합니다. 이 한 줄 판단이 모든 풀이 설계의 출발점입니다. 그래서 시간 초과(TLE)를 진단하는 절차는 이렇게 굳혀 두세요.

# complexity/tle_estimator.py

OPS_PER_SECOND = 10 ** 8             # 대략적인 1초 처리량

def fits_in_time(complexity, n, seconds=1):
    return estimate_ops(complexity, n) <= OPS_PER_SECOND * seconds

🎯 시간 초과 진단 4단계 (코테에서 풀이를 짜기 전에 매번):

1. 문제의 입력 제한 n을 확인한다 (n ≤ ?).
2. "1초 1억" 표로 허용 복잡도 상한을 읽는다 (예: n ≤ 10⁵ → O(n log n) 이하).
3. 내가 떠올린 풀이의 빅오를 읽는다 (Step 4의 반복문 읽기).
4. 상한을 넘으면 더 빠른 접근으로 갈아탄다. 통과 범위면 자신 있게 제출한다.

이 잣대는 오늘로 끝이 아니라, 앞으로 19개 모듈 내내 바닥에 깔립니다. 어떤 자료구조를 배우든 어떤 알고리즘을 짜든, "이게 시간 안에 들어오나?"를 늘 이 표로 되짚게 됩니다.

💡 한 줄 정리

"1초 ≈ 1억 연산"으로 입력 제한을 보면 허용 복잡도가 보인다 — n ≤ 10⁵면 O(n²)는 시간 초과, O(n log n) 이하로. 풀기 전에 빅오로 통과를 미리 진단한다.

마무리

첫 모듈, 정말 수고 많으셨습니다. 오늘 우리는 코드를 짜는 것을 넘어, 코드의 속도를 읽는 눈을 얻었습니다. 이 눈이 앞으로 모든 모듈에서 길잡이가 됩니다.

오늘 배운 핵심 세 가지

💡 하나 — 빅오는 성장률이다. 상수·낮은 차수를 버리고 최고차항만 남겨, 입력이 커질 때 연산이 늘어나는 속도를 본다.

💡 둘 — 코드 모양으로 빅오를 읽는다. 중첩=곱, 순차=합, 절반씩=log. 그리고 빅오는 보통 최악의 경우를 기준으로 잡는다. 시간만이 아니라 공간(메모리)도 같은 방식으로 잰다.

💡 셋 — "1초 1억 연산"으로 통과를 미리 진단한다. 입력 제한을 보면 허용 복잡도가 보이고, 풀이의 빅오와 견주면 시간 초과를 짜기 전에 막을 수 있다.

다음 시간 예고

다음 시간(A-2)에는 드디어 첫 자료를 직접 만집니다. 배열과 문자열이에요. 방금 쥔 빅오 잣대를 들고, 배열을 인덱싱·슬라이싱하고 2차원 격자를 순회하며 구현·시뮬레이션 문제에 접근합니다. 그리고 입력이 클 때 시간 초과를 피하는 코테 단골 기법, sys.stdin으로 빠르게 읽는 법도 익힙니다.

참고로 이 과목에는 자주 떠올릴 그림이 셋 있습니다. 오늘 본 ① 빅오 성장 비교가 첫 번째였고, ② 자료구조 지도(선형 B와 비선형 C)와 ③ 재귀 호출 스택(E 패러다임)은 해당 모듈에서 펼칩니다.

과제

오늘 배운 빅오 읽기와 "1초 1억" 진단을 확실히 익히는 문제들입니다. 직접 풀어 본 뒤 예시 답안과 맞춰 보세요.

[기초] 코드 조각의 빅오 판정하기

아래 다섯 함수 각각의 시간 복잡도를 빅오로 판정하세요. 함정이 숨어 있으니 "반복문 개수"만 세지 말고, 중첩인지 순차인지·안쪽이 입력에 비례하는지를 따져야 합니다.

def ex_a(n):
    ops = 0
    for _ in range(n):
        ops += 1
    return ops

def ex_b(n):
    ops = 0
    for i in range(n):
        for _ in range(i):
            ops += 1
    return ops

def ex_c(n):
    ops = 0
    i = n
    while i >= 1:
        ops += 1
        i //= 2
    return ops

def ex_d(n):
    ops = 0
    for _ in range(n):
        ops += 1
    for _ in range(n):
        ops += 1
    return ops

def ex_e(n):
    ops = 0
    for _ in range(n):
        for _ in range(100):
            ops += 1
    return ops

[응용] 같은 문제를 O(n²)와 O(n)으로 짜 보기

두 배열 a, b에 공통 원소가 하나라도 있는지 판단하는 함수를 두 가지로 만들어 보세요. ① 모든 쌍을 맞대 보는 O(n²) 풀이, ② 한 배열을 집합에 담아 두고 다른 배열을 한 번만 훑는 O(n) 풀이. 그리고 공통 원소가 없을 때(최악) 두 풀이의 연산 횟수가 얼마나 차이 나는지 직접 세어 비교하세요.

[심화] 입력 제한을 보고 시간 초과 진단하기

어떤 문제의 입력 제한이 n ≤ 200,000이라고 합시다. 아래 세 후보 풀이의 빅오를 각각 판정하고, "1초 1억" 잣대로 통과 / 시간 초과를 가르세요. 그리고 시간 초과인 풀이는 어느 복잡도까지 낮춰야 통과하는지도 적어 보세요.

• 후보 1: 모든 원소 쌍을 한 번씩 확인하는 풀이
• 후보 2: 배열을 한 번 정렬한 뒤 한 번 훑는 풀이 (정렬은 O(n log n)이라고 알려져 있다고 가정)
• 후보 3: 배열을 그대로 한 번만 훑는 풀이

생각해볼 주제

정답이 하나가 아닌 질문들입니다. 혼자 고민해도 좋고, 스터디에서 토론해도 좋아요.

1. 빅오는 상수를 버리는데, 실무에선 상수가 중요할 때가 있다 — 언제 빅오만으로 부족할까?

빅오는 입력이 충분히 클 때의 성장률만 봅니다. 그런데 입력이 작거나, 차수는 같은데 상수배가 크게 다른 두 풀이를 고를 땐 빅오만으로 결론이 안 납니다. 어떤 상황에서 빅오 위에 실측·상수를 더 봐야 하는지 생각해 보세요.

2. O(n log n) 정렬이 항상 O(n²) 정렬보다 빠를까?

차수만 보면 O(n log n)이 O(n²)보다 빠릅니다. 하지만 입력이 아주 작거나 거의 정렬돼 있을 때는 역전이 일어나기도 합니다. 왜 그런 일이 생길 수 있는지, 빅오와 실제 속도의 관계로 따져 보세요. (정렬 알고리즘 자체는 D-1에서 다루니, 여기서는 "차수가 같지 않아도 실측이 뒤집힐 수 있는 이유"에 집중)

3. 시간 복잡도가 같으면 같은 속도일까?

둘 다 O(n)인 두 풀이가 있습니다. 실제로 돌려 보면 한쪽이 훨씬 빠를 수 있습니다. 빅오가 같은데도 속도가 갈리는 이유는 무엇일까요? 상수배 말고도 영향을 주는 게 있을지 떠올려 보세요.