[Python] 알고리즘 설계 기초

 

동빈나 채널의 파이썬 문법 부수기 유튜브 강의를 참고하여 정리한 내용이다.

 

코딩테스트를 준비하면서 이코테(이것이 취업을 위한 코딩 테스트다) 강의를 들으며 정리한 내용이다.

본격적인 자료구조나 알고리즘 문법 공부에 앞서 먼저 알아야 할 알고리즘 설계 기초 내용을 정리했다.

 

---

 

알고리즘 설계 Tip

시간복잡도와 수행시간 감각

코딩테스트에서 가장 먼저 봐야 할 건 시간 제한이다.

보통 1~2초가 주어지는데, 이걸 그냥 넘겨버리면 아무리 정확한 코드를 짜도 의미가 없다.

일반적으로 코딩테스트 채점 서버 기준으로 1초에 수행 가능한 연산 횟수는 대략 1억 번(10^8) 정도라고 보면 된다.

파이썬은 C/C++보다 느려서 같은 코드라도 파이썬 기준으로 더 넉넉하게 잡아야 한다.

언어	1초 기준 연산 횟수 (대략)
C / C++	10^8 ~ 10^9
Java	10^8
Python	10^7 ~ 10^8

 

파이썬으로 코딩테스트를 볼 때 시간 초과가 자주 뜨는 이유가 이 때문이다.

인터프리터 언어 특성상 같은 알고리즘이라도 C보다 5~10배 정도 느리다.

 

N 범위로 시간복잡도 추측하기

문제를 받으면 N의 범위를 보고 어떤 시간복잡도 알고리즘을 써야 하는지 역추산할 수 있다.

N의 범위	가능한 시간복잡도	알고리즘 예시
N ≤ 10	O(N!) 이하	완전탐색, 순열
N ≤ 20	O(2^N)	비트마스크, 백트래킹
N ≤ 500	O(N^3)	플로이드-워셜
N ≤ 3,000	O(N^2)	이중 반복문
N ≤ 100,000	O(N log N)	정렬, 세그먼트 트리
N ≤ 1,000,000	O(N) 또는 O(N log N)	해시, 투 포인터
N ≤ 10,000,000	O(N)	단순 반복, 선형 탐색

 

예를 들어 N이 100만이면 O(N^2) 알고리즘은 10^12번의 연산이 필요해서 절대 통과가 안 된다.

N log N 이하로 해결해야 한다.

문제를 보자마자 N 범위 확인 → 가능한 시간복잡도 추산 → 알고리즘 선택 순서로 접근한다.

 

---

 

알고리즘 문제 해결 과정

이코테에서 제시하는 4단계 문제 해결 과정이다.

 

1단계 : 지문 읽기 및 핵심 내용 파악

문제를 천천히 읽고 무엇을 구해야 하는지 파악한다. 조건과 예외 케이스도 이 단계에서 체크한다. 급하게 코드 짜다가 엣지 케이스 놓치면 WA(오답) 뜨고 시간만 버린다.

 

2단계 : 요구사항에 맞는 알고리즘 설계

N 범위를 보고 어떤 알고리즘을 써야 할지 정한다. 손으로 로직을 먼저 그려보는 게 좋다. 머릿속에서만 설계하면 구현하다가 막힐 때 방향을 잃기 쉽다.

 

3단계 : 코드 구현

설계한 로직을 실제 코드로 옮긴다. 이 단계에서 문법 실수나 인덱스 오류가 자주 나온다. 차분하게 짜고, 주요 변수에 print를 찍어가며 확인하는 게 효율적이다.

 

4단계 : 테스트 및 디버깅

제공된 예제 케이스로 먼저 테스트하고, 직접 엣지 케이스(N=0, N=1, 최댓값 등)를 추가로 만들어 검증한다.

 

---

 

수행 시간 측정

코드가 실제로 얼마나 걸리는지 확인하고 싶을 때 time 모듈을 사용한다.

import time

start_time = time.time()

# 측정하고 싶은 코드
result = 0
for i in range(1000000):
    result += i

end_time = time.time()

print(f"수행 시간: {end_time - start_time:.5f}초")

수행 시간: 0.06843초

 

time.time()은 유닉스 타임스탬프(1970년 1월 1일부터의 초)를 반환한다.

시작과 끝에서 각각 찍고 빼면 수행 시간이 나온다.

 

더 정밀한 측정 : timeit

작은 코드 조각의 성능을 비교할 때는 timeit이 더 정확하다.

import timeit

# 리스트 컴프리헨션 vs for 반복문 속도 비교
code1 = "[i * 2 for i in range(1000)]"
code2 = """
result = []
for i in range(1000):
    result.append(i * 2)
"""

t1 = timeit.timeit(code1, number=10000)
t2 = timeit.timeit(code2, number=10000)

print(f"컴프리헨션: {t1:.4f}초")
print(f"for + append: {t2:.4f}초")

컴프리헨션: 0.3821초
for + append: 0.6514초

 

리스트 컴프리헨션이 일반적으로 더 빠르다.

코딩테스트에서 시간이 촉박할 때 컴프리헨션을 쓰면 유리한 경우가 있다.

 

---

 

파이썬 성능 개선 팁

다음은 코딩테스트에서 파이썬으로 시간 초과가 날 때 시도해볼 수 있는 방법들이다.

input() 대신 sys.stdin.readline()

input()은 느리다. 입력이 많을 때는 sys.stdin.readline()을 사용한다.

import sys
input = sys.stdin.readline

n = int(input())
data = list(map(int, input().split()))

# 주의: readline은 줄 끝에 \n이 붙어 있다
line = sys.stdin.readline()
line = line.strip()  # \n 제거 필요

 

PyPy vs Python

플랫폼에 따라 PyPy 제출이 가능한 경우가 있다.

PyPy는 JIT 컴파일러를 사용해서 순수 반복문 위주 코드에서 Python보다 3~5배 빠르다.

단, 메모리를 더 많이 쓴다.

 

재귀 깊이 제한

파이썬의 기본 재귀 깊이 제한은 1000이다.

DFS나 재귀 알고리즘에서 이 제한을 넘으면 RecursionError가 발생한다.

import sys
sys.setrecursionlimit(10000)  # 재귀 깊이 제한 늘리기

# RecursionError 예시
def factorial(n):
    return n * factorial(n - 1)  # 종료 조건 없음

factorial(5)
# RecursionError: maximum recursion depth exceeded

# 올바른 재귀 함수 - 종료 조건 필수
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))   # 120
print(factorial(10))  # 3628800

 

---

 

자주 하는 실수들

정수 오버플로우는 없지만 속도 문제는 있다

파이썬은 정수 크기에 제한이 없다.

C에서 int 오버플로우를 걱정하는 것과 달리 파이썬에서는 아무리 큰 수도 그냥 계산된다.

print(2 ** 100)
# 1267650600228229401496703205376

 

대신 숫자가 커지면 연산이 느려진다. 불필요하게 큰 수를 다루지 않도록 주의한다.

 

반복문 안에서 리스트 수정

반복문으로 순회하면서 리스트를 직접 수정하면 예상치 못한 결과가 나온다.

# 잘못된 예시 - 반복 중 리스트 수정
nums = [1, 2, 3, 4, 5]
for num in nums:
    if num % 2 == 0:
        nums.remove(num)

print(nums)  # [1, 3, 5] 가 되어야 하지만
# 실제: [1, 3, 5] ... 운이 좋으면 맞지만 요소 건너뜀 가능

# 올바른 예시 - 새 리스트로 필터링
nums = [1, 2, 3, 4, 5]
nums = [num for num in nums if num % 2 != 0]
print(nums)  # [1, 3, 5]

 

가변 기본 인수 함정

함수 기본 인수에 리스트나 딕셔너리 같은 가변 객체를 쓰면 호출 간 상태가 공유된다.

# 잘못된 예시
def append_to(element, to=[]):
    to.append(element)
    return to

print(append_to(1))  # [1]
print(append_to(2))  # [1, 2] - 예상은 [2]였는데!

# 올바른 예시
def append_to(element, to=None):
    if to is None:
        to = []
    to.append(element)
    return to

print(append_to(1))  # [1]
print(append_to(2))  # [2]

 

---

 

알고리즘 설계 기초는 문법이나 자료구조보다 먼저 머릿속에 넣어두어야 하는 내용이다.

N 범위 보고 시간복잡도 추산하는 것만 잘 해도 불필요한 삽질을 많이 줄일 수 있다.