복잡도와 기초 문제
개념마다 확인(뜻을 맞게 알았나) → 추적(손으로 한 단계씩) → 응용(처음 보는 상황) 순서로 푼다. 풀이 보기를 누르기 전에 종이에 먼저 적어 보자.
빅오 표기
확인
f(n) = 3n² + 100n + 7을 빅오로 적으면 무엇인가? n = 10이면 100n(1,000)이 3n²(300)보다 큰데도 100n을 버려도 되는 까닭을 아래 그래프로 설명해 보라.
풀이 보기
O(n²)이다. 두 항은 3n² = 100n, 곧 n = 100/3 ≈ 33에서 만난다. 그 뒤로는 3n²이 앞서고, 둘의 비 3n²/100n = 3n/100은 n이 커질수록 끝없이 커진다. n = 100이면 30,000 대 10,000, n = 1,000이면 3,000,000 대 100,000으로 30배다.
빅오는 n이 충분히 클 때의 모양만 본다. 어느 지점을 넘으면 가장 빨리 크는 항이 나머지를 모두 덮으므로 작은 항(100n, 7)은 버린다. 앞의 상수 3도 버린다. 3이든 30이든 n이 두 배가 될 때 네 배가 된다는 모양은 같기 때문이다. 다만 n이 33보다 작은 입력만 다룬다면 실제로는 100n 쪽이 비용을 정한다는 점도 기억해 두자.
추적
아래 코드에서 n = 5일 때 반복이 끝난 뒤 count는 얼마인가? 일반적인 n에 대한 식과 빅오도 적어 보라.
count = 0
for i in range(n):
for j in range(i + 1, n):
count += 1풀이 보기
10이다. 안쪽 반복은 i = 0일 때 4번, 1일 때 3번, 2일 때 2번, 3일 때 1번, 4일 때 0번 돈다. 4 + 3 + 2 + 1 + 0 = 10이다.
일반적으로는 (n − 1) + (n − 2) + … + 1 = n(n − 1)/2이다. 서로 다른 두 원소를 고르는 쌍의 수와 같다. 전개하면 n²/2 − n/2이고, 상수 1/2과 작은 항을 버리면 O(n²)이다. 안쪽 반복이 바깥보다 짧아져도, 격자의 절반은 여전히 n²에 비례한다.
추적
아래 코드에서 n = 100이면 반복문 몸통이 몇 번 실행되는가? 이 코드의 시간 복잡도는?
i = 1
steps = 0
while i < n:
i *= 2
steps += 1풀이 보기
7번이다. 조건을 검사할 때 i는 1, 2, 4, 8, 16, 32, 64로 일곱 번 100보다 작고, 몸통을 일곱 번 돈 뒤 128이 되어 멈춘다.
i가 매번 두 배가 되므로 k번 돈 뒤 i = 2k이다. 2k ≥ n이 되는 가장 작은 k가 반복 횟수이니 ⌈log₂ n⌉ = ⌈log₂ 100⌉ = 7이다. 그래서 O(log n)이다. n이 100만이 되어도 20번이면 끝난다. 이진 탐색이 빠른 까닭도 같다. 남은 구간을 매번 절반으로 줄인다.
응용
입력 크기 n이 100만(10⁶)이고 제한 시간이 1초다. 컴퓨터가 1초에 단순 연산을 약 10⁸번 한다고 어림할 때, O(n log n), O(n√n), O(n²) 알고리즘 중 어느 것이 시간 안에 끝날까?
풀이 보기
O(n log n)만 안전하다. n log₂ n ≈ 10⁶ × 20 = 2×10⁷으로 10⁸보다 다섯 배쯤 작다.
O(n√n)은 10⁶ × 10³ = 10⁹로 약 10초, O(n²)은 10¹²로 약 10⁴초, 곧 세 시간 가까이 걸린다. 상수를 아무리 줄여도 O(n²)을 1초에 넣을 수는 없다. 그래서 문제를 받으면 먼저 n을 보고 "10⁶이면 O(n log n) 이하"처럼 허용되는 복잡도부터 정한다. 어림셈의 10⁸은 언어와 연산 종류에 따라 열 배쯤 오르내리므로, 경계에 걸친 복잡도(여기서는 10⁹)는 상수까지 따져 봐야 한다.
최선·평균·최악
확인
아래 배열을 앞에서부터 선형 탐색한다. 7, 5, 4를 각각 찾을 때 비교는 몇 번 하는가? 셋 중 최선과 최악에 해당하는 것은?
풀이 보기
7은 1번, 5는 5번, 4는 8번이다. 7은 0번 칸에 있어 첫 비교에서 끝난다. 5는 4번 칸이라 0~4번 칸을 본다. 4는 없으므로 8칸을 모두 보고 나서야 없다고 답한다.
7을 찾는 것이 최선(O(1)), 4를 찾는 것이 최악(O(n))이다. 맨 끝의 6을 찾을 때도 8번이라 최악이다. 없는 값을 찾는 일은 실제로 흔하므로(중복 검사 등) 최악을 가볍게 볼 수 없다.
추적
같은 배열에서 찾는 값이 배열의 8개 값 중 하나이고, 어느 값이든 같은 확률로 온다고 하자. 평균 비교 횟수는? 찾는 값의 절반은 배열에 없는 값이라면 평균은 어떻게 바뀌는가?
풀이 보기
있는 값만 찾으면 4.5번, 절반이 없는 값이면 6.25번이다. 있는 값의 평균은 (1 + 2 + … + 8) / 8 = 36 / 8 = 4.5다. 일반적으로 (n + 1)/2이므로 평균도 O(n)이다.
절반이 없는 값이면 0.5 × 4.5 + 0.5 × 8 = 6.25다. 평균은 "어떤 입력이 얼마나 자주 오는가"라는 가정에 따라 값이 바뀐다. 가정이 틀리면 평균도 틀리지만, 최악(8번)은 어떤 가정에서도 그대로다.
응용
삽입 정렬은 값을 하나씩 꺼내 왼쪽의 정렬된 부분에서 자리를 찾을 때까지 왼쪽 이웃과 비교한다. 아래 두 입력에서 비교는 각각 몇 번 하는가? n = 1,000이면 어떻게 될까?
풀이 보기
정렬된 입력은 4번, 거꾸로 된 입력은 10번이다. 정렬된 입력에서는 새 값마다 왼쪽 이웃과 한 번만 비교하고 멈춘다(n − 1번, 최선 O(n)). 거꾸로 된 입력에서는 새 값이 매번 맨 앞까지 가야 해서 1 + 2 + 3 + 4 = 10번이다(n(n − 1)/2번, 최악 O(n²)).
n = 1,000이면 999번 대 499,500번으로 500배 차이다. 같은 알고리즘이 입력 모양에 따라 O(n)과 O(n²)을 오간다. 실무 데이터는 "거의 정렬된" 경우가 흔해서, 최악이 O(n²)인데도 여러 표준 라이브러리 정렬이 작은 구간에는 삽입 정렬을 쓴다.
분할 상환 분석
확인
용량 1칸에서 시작해 가득 차면 두 배로 늘리는 동적 배열에 값 8개를 넣었다. 넣기마다 든 비용(쓰기 1 + 옮긴 칸 수)이 아래와 같다. 가장 비싼 넣기는 몇 번째인가? 8번 넣는 동안의 비용 합과 한 번당 평균은?
풀이 보기
5번째 넣기가 비용 5로 가장 비싸다. 합은 15, 평균은 1.875다. 5번째에 용량 4가 가득 차 있어 8칸으로 늘리며 4칸을 옮기고 하나를 쓴다.
넣기 한 번만 보면 최악은 O(n)이지만, 비싼 넣기는 용량이 두 배가 될 때만 오고 그 사이에는 싼 넣기가 점점 길게 이어진다. 그래서 n번 넣는 비용의 합은 3n을 넘지 않고, 한 번당 분할 상환 비용은 O(1)이다. 개별 연산의 최악과, 연산을 이어 했을 때의 평균 보장은 다른 질문이다.
추적
이번에는 용량 2칸에서 시작해 두 배씩 늘린다. 값 9개를 넣을 때 용량은 몇 번째 넣기에서 늘어나고, 그때마다 몇 칸을 옮기는가? 마지막 용량과 누적 비용은?
풀이 보기
3번째(2칸 옮김, 용량 4), 5번째(4칸 옮김, 용량 8), 9번째(8칸 옮김, 용량 16)에 늘어난다. 마지막 용량은 16, 누적 비용은 23이다.
빈 배열. 용량은 2칸이다.
쓰기 9번에 옮기기 2 + 4 + 8 = 14칸을 더해 23이다. 한 번당 23 / 9 ≈ 2.56으로 역시 3 아래다. 처음 용량을 키우면 늘리는 횟수가 줄 뿐, 옮기는 양이 등비수열이라는 구조는 그대로다.
응용
메모리를 아끼려고 동적 배열을 "가득 차면 2칸씩 더 늘리는" 방식으로 바꿨다. 용량 2칸에서 시작해 값 16개를 넣을 때 누적 비용을 두 배씩 늘리는 방식과 비교해 보라. n이 커지면 넣기 한 번의 분할 상환 비용은 어떻게 되는가?
풀이 보기
2칸씩 더하면 72, 두 배씩 늘리면 30이다. 2칸씩은 용량 2, 4, …, 14에서 가득 찰 때마다 늘려 2 + 4 + … + 14 = 56칸을 옮긴다. 두 배씩은 2 + 4 + 8 = 14칸만 옮긴다. 둘 다 쓰기 16번을 더한 값이다.
2칸씩이면 늘릴 때마다 옮기는 양이 2칸씩 커지는 등차수열이라, n개를 넣는 동안 옮기는 총량이 약 n²/4로 n²에 비례한다. 그러면 한 번당 비용이 O(n)이 된다. 곱으로 늘려야 옮기는 양이 등비수열이 되어 합이 n에 비례한다. 메모리가 걱정이면 늘리는 비율을 1.5배처럼 줄이는 것이 맞고, 더하는 방식으로 바꾸면 안 된다.
메모리 계층과 캐시 지역성
확인
4×4 정수 배열이 행 우선(한 행이 메모리에 이어져 있음)으로 놓여 있고, 캐시 라인 하나에 정수 4개, 곧 한 행이 들어간다고 하자. 캐시가 라인 하나만 기억할 때, 가로로 돌기와 세로로 돌기의 캐시 미스는 각각 몇 번인가? 캐시가 라인 4개를 기억하면?
풀이 보기
라인 하나만 기억하면 가로 4번, 세로 16번이다. 가로로 돌면 라인 하나를 가져와 네 칸을 연달아 쓰고 다음 라인으로 간다. 세로로 돌면 칸마다 다른 행, 곧 다른 라인이라 직전에 가져온 라인을 한 번도 다시 쓰지 못한다.
라인 4개를 기억하면 둘 다 4번이다. 배열 전체가 캐시에 들어가니 순서가 상관없다. 실제 문제는 배열이 캐시보다 클 때 생긴다. 1000×1000 배열을 세로로 돌면 다음 열로 돌아올 무렵 첫 행의 라인은 이미 밀려나 있어, 거의 모든 읽기가 미스가 된다. 그래서 2차원 배열은 메모리에 놓인 순서대로 돈다.
추적
16바이트짜리 노드 8개로 된 연결 리스트를 따라간다. 방문 순서대로 노드의 주소가 아래와 같고, 캐시 라인은 64바이트다. 캐시가 라인 하나만 기억할 때와, 넉넉해서 한 번 가져온 라인을 끝까지 기억할 때 미스는 각각 몇 번인가?
풀이 보기
라인 하나만 기억하면 8번, 넉넉하면 3번이다. 라인 번호는 주소 ÷ 64의 몫으로 0, 11, 0, 11, 22, 0, 11, 22다. 쓰는 라인은 0, 11, 22 셋뿐이지만 방문할 때마다 라인이 바뀐다.
같은 라인을 곧 다시 쓰는 시간 지역성은 있지만, 라인 하나짜리 캐시에서는 그 사이에 다른 라인이 끼어들어 소용이 없다. 노드 8개 × 16바이트 = 128바이트를 방문 순서대로 이어 놓으면(배열처럼) 라인 2개, 미스 2번으로 끝난다. 실제 캐시는 넉넉한 쪽에 가깝지만, 리스트가 캐시보다 커지면 라인 하나짜리처럼 행동한다.
응용
게임에 객체 1,000개가 있고, 객체 하나는 64바이트 구조체다. 그중 위치는 12바이트다. 매 프레임 위치만 읽어 갱신할 때, 객체를 구조체 배열(AoS)로 둘 때와 위치만 따로 모은 배열(SoA)로 둘 때 캐시 라인(64바이트)을 각각 몇 개 가져와야 하는가?
풀이 보기
AoS는 1,000개, SoA는 188개다. AoS에서는 객체 하나가 라인 하나를 꽉 채우므로, 위치 12바이트를 읽으려고 64바이트를 통째로 가져온다. SoA에서는 위치 1,000개가 12,000바이트에 이어져 있어 12,000 ÷ 64 = 187.5, 곧 라인 188개면 된다.
가져오는 메모리가 5분의 1 남짓으로 줄고, 이어진 주소라 프리페처도 잘 맞는다. 두 방식 모두 O(n)이지만 실제 시간은 크게 다르다. 게임 엔진의 ECS가 컴포넌트를 종류별 배열로 두는 까닭이 이것이다(게임 엔진 노트). 반대로 한 객체의 모든 필드를 함께 쓰는 코드라면 AoS가 낫다. 함께 쓰는 값끼리 붙여 두는 것이 원칙이다.
재귀와 호출 스택
확인
아래 함수로 fact(3)을 부르면 어떻게 되는가? 무엇이 빠졌고, 어떻게 고치면 되는가?
def fact(n):
return n * fact(n - 1)풀이 보기
끝나지 않고 스택이 넘친다. 바닥 조건이 없어 fact(1)에서도 멈추지 않고 fact(0), fact(−1), …로 계속 부른다. 부를 때마다 프레임이 쌓이다 스택 한도에 닿으면 프로그램이 죽는다. 파이썬은 깊이가 기본 한도(1,000) 근처에 이르면 RecursionError를 낸다.
재귀가 끝나려면 두 가지가 필요하다. 더 부르지 않고 답하는 바닥 조건, 그리고 부를 때마다 그 바닥에 가까워지는 것이다. if n <= 1: return 1을 맨 앞에 두면 둘 다 갖춘다. n == 1 대신 n <= 1로 쓰면 fact(0)이나 음수가 들어와도 끝난다.
추적
바닥 조건이 factorial(1) = 1인 재귀 팩토리얼로 factorial(5)를 계산한다. 호출 스택은 최대 몇 칸까지 쌓이는가? 프레임이 걷히면서 돌려주는 값을 순서대로 적어 보라.
풀이 보기
최대 5칸이고, 돌려주는 값은 1, 2, 6, 24, 120 순서다. factorial(5)부터 factorial(1)까지 다섯 프레임이 쌓인 뒤, 맨 위부터 하나씩 걷히며 답을 아래로 넘긴다.
factorial(5) 호출. 답을 내려면 먼저 factorial(4)의 값이 필요하다.
스택 깊이가 n이므로 공간도 O(n)이다. 반복문으로 쓰면 곱을 담을 변수 하나만 있으면 되어 O(1)이다. 값을 먼저 다 부른 뒤 돌아오면서 계산한다는 점, 곧 마지막에 부른 것이 먼저 끝나는 후입선출을 단계 그림에서 확인해 두자.
응용
fib(n) = fib(n − 1) + fib(n − 2), fib(0) = 0, fib(1) = 1을 그대로 재귀로 쓰면 fib(5)를 구하는 동안 함수가 모두 몇 번 불리는가? fib(2)는 몇 번 다시 계산되는가? 한 번 구한 답을 사전에 적어 두면(메모이제이션) 호출 수는 어떻게 바뀌는가?
풀이 보기
모두 15번 불리고, fib(2)는 3번 계산된다. fib(3)은 2번, fib(1)은 5번, fib(0)은 3번이다. 같은 부분 문제를 거듭 풀어 호출 수가 피보나치 수처럼 늘어난다. fib(20)이면 21,891번이고, n이 1 늘 때마다 약 1.6배가 되어 지수 시간이다.
메모이제이션을 쓰면 9번으로 준다. fib(5), fib(4), fib(3), fib(2), fib(1), fib(0)을 한 번씩 계산하고(6번), fib(3)·fib(2)·fib(1)을 두 번째로 부를 때는 사전에서 바로 꺼낸다(3번). 서로 다른 부분 문제가 n + 1개뿐이라 O(n)이다. 이 생각을 넓힌 것이 설계 기법 노트의 동적 계획법이다.