반복문과 중첩 반복문 분석
단일 반복문, 중첩 반복문, 이진 검색이나 삼각형 반복처럼 범위가 줄어드는 반복문의 시간 복잡도를 계산합니다.
반복문과 중첩 반복문 분석은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
단일 반복문: O(n)
가장 단순한 반복문은 본문을 n번 실행하므로 O(n)입니다. 보폭이 커지면 실행 횟수는 달라지지만 복잡도 분류는 달라지지 않습니다. 항상 본문이 몇 번 실행되는지 세는 것부터 시작하세요. 코드를 확인해 보세요.
# O(n): body runs n times
def count_ops_linear(n):
ops = 0
for i in range(n):
ops += 1 # constant work
return ops
print(count_ops_linear(100)) # 100
# Still O(n): step=2 halves count but same class
def count_ops_half(n):
ops = 0
for i in range(0, n, 2):
ops += 1
return ops
print(count_ops_half(100)) # 50 => O(n)중첩된 반복문: O(n²) 이상
각각 n번 실행되는 반복문 두 개를 중첩하면 n x n = O(n^2)이 되고, 세 개를 중첩하면 O(n^3)이 됩니다. 하지만 내부 반복문이 고정된 횟수만큼 실행된다면 전체 복잡도는 여전히 선형입니다.
def count_pairs(n):
ops = 0
for i in range(n): # n iterations
for j in range(n): # n iterations each
ops += 1
return ops
print(count_pairs(10)) # 100 = 10^2
print(count_pairs(100)) # 10000 = 100^2
# Doubling n quadruples ops: classic O(n^2)삼각형 반복문: O(n²/2) = O(n²)
내부 반복문이 i+1에서 시작하면 반복 횟수는 삼각형 모양을 이룹니다. 즉 n(n-1)/2가 되며, 절반을 제외하면 여전히 O(n^2)입니다. 모든 고유 쌍을 다루는 문제는 이런 형태로 나타납니다.
def count_unique_pairs(n):
ops = 0
for i in range(n): # n iterations
for j in range(i+1, n): # n-1, n-2, ..., 0
ops += 1
return ops
print(count_unique_pairs(10)) # 45 = 10*9/2
print(count_unique_pairs(100)) # 4950
# Still O(n^2) -- constant factor 1/2 dropped범위가 줄어드는 반복문: O(log n)
반복문 변수가 각 단계에서 절반으로 줄어들면 O(log n)이 됩니다. 핵심 질문은 범위가 곱셈 방식으로 줄어드는지(log n), 덧셈 방식으로 줄어드는지(n)입니다. 코드를 확인해 보세요.
def count_log_ops(n):
ops = 0
i = n
while i >= 1:
ops += 1
i //= 2 # halve each iteration
return ops
import math
for n in [8, 16, 64, 1024]:
ops = count_log_ops(n)
print(f'n={n}, ops={ops}, log2={int(math.log2(n))}')
# ops tracks log2(n) closely내부 범위가 줄어드는 중첩 반복문: O(n log n)
n번 실행되는 외부 반복문 안에 O(log n)의 내부 반복문이 있으면 O(n log n)이 됩니다. 이는 병합 정렬의 형태입니다. 정렬 알고리즘을 분석할 때는 내부 단계가 O(log n)인지 알아보는 것이 핵심입니다.
import math
def count_n_log_n(n):
ops = 0
for i in range(n): # n iterations
j = n
while j >= 1: # log n iterations
ops += 1
j //= 2
return ops
for n in [8, 32, 128]:
ops = count_n_log_n(n)
predicted = int(n * math.log2(n))
print(f'n={n}: actual={ops}, n*log2(n)~={predicted}')종속된 내부 반복문
내부 반복문의 범위가 외부 인덱스에 따라 달라지면 단계별 횟수가 아니라 전체 반복 횟수를 세어야 합니다. 내부 반복문이 0..i까지 실행되면 합은 n(n-1)/2 = O(n^2)입니다. 코드를 확인해 보세요.
# Inner loop runs i times: total = 0+1+2+...+(n-1) = n(n-1)/2 => O(n^2)
def sum_inner_i(n):
ops = 0
for i in range(n):
for j in range(i): # runs 0,1,2,...,n-1 times
ops += 1
return ops
print(sum_inner_i(10)) # 45 = 10*9/2 => O(n^2)
# Inner loop runs n/i times (i doubles): sum ≈ n*log n => O(n log n)
def sum_inner_n_over_i(n):
ops = 0
i = 1
while i <= n:
for j in range(n // i):
ops += 1
i *= 2
return ops
print(sum_inner_n_over_i(64)) # ~ 64*6 = 384버블 정렬 분석 단계별로 보기
버블 정렬은 n(n-1)/2번 비교하므로 O(n^2)입니다. 조기 종료를 사용하더라도 역순으로 정렬된 입력에서는 모든 비교가 필요합니다. 큰 입력에는 너무 느립니다.
def bubble_sort(arr):
n = len(arr)
comparisons = 0
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # early exit if sorted
break
return comparisons
arr = list(range(10, 0, -1)) # worst case: reversed
ops = bubble_sort(arr)
print(f'Sorted: {arr}')
print(f'Comparisons: {ops}') # 45 = 10*9/2문자열과 부분 문자열에 대한 반복문
주의하세요. 파이썬의 슬라이싱은 O(k)이며 비용이 없는 연산이 아닙니다. 반복문에서 +로 문자열을 연결하면 매번 복사하므로 O(n^2)이 됩니다. 대신 ''.join(parts)를 사용하세요. 코드를 확인해 보세요.
# O(n^2): string concat in loop
def build_bad(n):
s = ''
for i in range(n):
s += str(i) # copies s each time!
return s
# O(n): join is a single pass
def build_good(n):
parts = []
for i in range(n):
parts.append(str(i))
return ''.join(parts)
print(build_good(10)) # '0123456789'여러 입력 매개변수
입력이 두 개이면 복잡도에 두 입력이 모두 사용될 수 있습니다. 서로 분리된 작업은 O(m + n), 중첩된 작업은 O(m x n)입니다. 그래프는 보통 O(V + E)로 표현합니다. 각 변수를 명확하게 이름 붙이세요.
# O(m + n): two independent loops
def independent(m, n):
a = sum(range(m)) # O(m)
b = sum(range(n)) # O(n)
return a + b # total O(m + n)
# O(m * n): nested
def nested(m, n):
count = 0
for i in range(m): # O(m)
for j in range(n): # O(n) each
count += 1
return count # O(m * n)
print(independent(5, 10)) # 10 + 45 = 55
print(nested(5, 10)) # 50반복문 속 반복문과 순차 호출
함수 호출은 비용이 없는 것이 아니므로 함수 내부의 반복문도 계산해야 합니다. O(n)인 도우미 함수를 n번 호출하면 O(n^2)이 됩니다. 분석할 때는 항상 블랙박스 호출 내부도 살펴보세요.
# Naive string matching: O(n*m)
def naive_search(text, pattern):
n, m = len(text), len(pattern)
matches = []
for i in range(n - m + 1): # O(n)
if text[i:i+m] == pattern: # O(m) comparison + O(m) slice
matches.append(i)
return matches
# Total: O(n*m)
print(naive_search('abcabcabc', 'abc')) # [0, 3, 6]실전: 한눈에 복잡도 파악
습관을 만들어 보세요. 반복문의 중첩 수준을 세고, 내부 반복문이 외부 반복문에 의존하는지 확인하며, 함수 호출과 슬라이싱에 숨은 비용이 있는지 살펴보세요. 코드를 퍼즐처럼 직접 풀어 보세요.
# What is the complexity of this function?
def mystery(nums):
result = []
for i in range(len(nums)): # O(n)
for j in range(i, len(nums)): # O(n) worst
if sum(nums[i:j+1]) == 0: # O(n) slice + sum!
result.append((i, j))
return result
# Answer: O(n^3) -- three nested n-proportional ops
# Outer O(n) x inner O(n) x sum/slice O(n) = O(n^3)빠른 확인
빠르게 확인해 보겠습니다. 반복문 분석 요령을 얼마나 잘 익혔는지 확인해 보세요. 여기서는 자신의 추론을 믿으세요. 💪
학습 내용 복습
복습해 보겠습니다. 중첩된 반복문은 곱하고 독립적인 반복문은 더합니다. 절반씩 줄어드는 내부 반복문은 O(n log n)을 만들며, 호출과 슬라이싱 내부의 숨은 비용도 반드시 계산해야 합니다.
자주 묻는 질문
“반복문과 중첩 반복문 분석” 강의는 무료인가요?
네 — “반복문과 중첩 반복문 분석” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“반복문과 중첩 반복문 분석”에서 뭘 배우나요?
단일 반복문, 중첩 반복문, 이진 검색이나 삼각형 반복처럼 범위가 줄어드는 반복문의 시간 복잡도를 계산합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“반복문과 중첩 반복문 분석” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- Big-O 표기법 기초
- 반복문과 중첩 반복문 분석
- 재귀와 재귀 트리 방법
- 공간 복잡도와 트레이드오프