수업 목표
본 수업은 알고리즘 해결을 위한 파이썬 환경을 분석하고, 문제 풀이에 필수적인 입출력 속도 향상 기법과 시간 복잡도 개념을 학습하는 것을 목표로 합니다.
- 파이썬의 표준 입출력과 고속 입출력 기법의 구조적 차이를 이해하고 적용합니다.
- 파이썬 기본 자료형(리스트, 딕셔너리, 집합)의 주요 연산별 Big-O 시간 복잡도를 습득합니다.
- CSES 및 CP-Python 교재에 수록된 기초 문제들을 분석하고 파이썬으로 구현합니다.
학습 동기부여
알고리즘 문제 풀이(PS)와 프로그래밍 대회에서는 설계한 알고리즘이 제한 시간 내에 동작해야만 정답으로 인정됩니다. 파이썬은 개발 편의성이 높은 언어이지만 C++에 비해 실행 속도가 상대적으로 느립니다. 이로 인해 동일한 복잡도의 알고리즘을 설계했음에도 단순한 입출력 병목으로 인해 시간 초과(Time Limit Exceeded) 판정을 받는 억울한 상황이 자주 발생합니다. 첫 단계에서 입출력을 최적화하고 자료구조의 연산별 시간 비용을 정확히 인지하는 것은, 실행 속도 제약을 극복하고 알고리즘 논리 자체에만 온전히 집중할 수 있도록 돕는 필수적인 예방 주사입니다.
도입 스토리
정보를 처리하는 컴퓨터 프로그램을 물건을 하역하고 가공하는 공장에 비유해 봅시다. 아무리 내부 가공 기계의 성능이 우수하고 조립 라인이 논리적으로 설계되어 있더라도, 원자재를 싣고 오는 화물 트럭이 공장 입구에서 한 장씩 물건을 검사받으며 느리게 들어온다면 공장 전체의 생산량은 크게 저하될 수밖에 없습니다. 파이썬의 기본 입력 함수인 input()은 한 번에 한 문자씩 시스템 인터럽트를 발생시키며 느리게 하역하는 트럭과 같고, sys.stdin.readline은 컨베이어 벨트를 통해 물건을 한꺼번에 부어버리는 자동화 설비와 같습니다. 본 챕터에서는 공장의 입구 속도를 극대화하는 기법을 배우고, 세상에서 가장 독특한 연산 규칙을 가진 수열 조립 공정인 이상한 알고리즘을 분석합니다.
1. 파이썬 입출력 속도 극대화
파이썬에서 대량의 데이터를 입력받거나 출력할 때 표준 input()과 print() 함수는 상당한 시간 오버헤드를 발생시킵니다. 이를 해결하기 위해 sys 모듈의 고속 입출력 함수를 사용합니다.
import sys
# 1. 한 줄의 문자열 입력받기 (개행 문자 \n 제거 필수)
input_string = sys.stdin.readline().rstrip()
# 2. 공백으로 구분된 여러 개의 정수 입력받기
n, m = map(int, sys.stdin.readline().split())
# 3. 대량의 데이터 출력 최적화
sys.stdout.write("출력할 문자열\n")
sys.stdin.readline()은 문자열의 끝에 줄바꿈 기호(\n)가 기본적으로 포함되어 반환되므로, 문자열 매칭이나 처리를 진행할 때는 반드시 rstrip()을 결합해야 예상치 못한 논리 오류를 방지할 수 있습니다.
2. 파이썬 핵심 자료형의 Big-O 시간 복잡도
"Competitive Programming in Python" 교재의 1.5절에서 강조하듯, 파이썬 내부 컨테이너의 시간 복잡도를 명확히 파악하고 코드를 구현해야 합니다.
| 자료형 (Class) |
연산 (Operation) |
시간 복잡도 |
설명 |
| 리스트 (list) |
append(x) |
$O(1)$ |
배열 끝에 원소 추가 (분할상환) |
| pop() |
$O(1)$ |
배열 끝의 원소 삭제 및 반환 |
| insert(0, x) / pop(0) |
$O(N)$ |
앞쪽 삽입/삭제 시 나머지 원소 이동 필요 |
| x in list |
$O(N)$ |
처음부터 끝까지 순회하여 탐색 |
| 딕셔너리 (dict) |
d[key] / d[key]=v |
$O(1)$ |
해시 테이블 기반으로 평균 상수 시간 |
| key in d |
$O(1)$ |
특정 키의 존재 여부를 즉시 판단 |
| 집합 (set) |
add(x) / remove(x) |
$O(1)$ |
원소 추가 및 삭제가 상수 시간에 수행 |
| x in set |
$O(1)$ |
리스트보다 압도적으로 빠른 탐색 |
| s1 & s2 (교집합) |
$O(\min(N, M))$ |
두 집합 중 작은 쪽 크기에 비례 |
3. 첫 번째 과제 해결: 이상한 알고리즘 (Weird Algorithm)
수론의 콜라츠 추측(Collatz Conjecture)에 기반한 알고리즘 문제입니다. 주어진 정수 $N$에 대해 아래 규칙을 적용하여 $1$이 될 때까지의 수열을 출력해야 합니다.
- $N$이 짝수이면 $N = N / 2$
- $N$이 홀수이면 $N = 3N + 1$
파이썬의 나누기 연산자(/)는 항상 실수형(Float)을 반환하므로, 정수형 연산을 유지하기 위해 정수 나눗셈 연산자(//)를 사용해야 오차 및 실수 출력 오류를 방지할 수 있습니다.
import sys
def main():
# 고속 입력 적용
n = int(sys.stdin.readline())
result = []
while True:
result.append(str(n))
if n == 1:
break
if n % 2 == 0:
n //= 2
else:
n = n * 3 + 1
# 결과를 공백으로 구분하여 한 번에 출력
sys.stdout.write(" ".join(result) + "\n")
if __name__ == "__main__":
main()
자주 하는 실수 & 오류 예방
- 문자열 비교 시 개행 문자 미처리: sys.stdin.readline()으로 읽은 문자열은 줄바꿈 문자를 포함하고 있으므로, rstrip() 처리 없이 비교 연산을 수행하면 논리적으로 일치하더라도 항상 거짓(False)이 반환됩니다.
- 실수형 나눗셈 사용: / 연산자를 통해 $N$을 나누게 되면 소수점이 발생하며 큰 수 연산 시 정밀도 손실이 일어나 정상적인 수열 계산을 방해합니다. 항상 // 연산자를 사용하여 정수형 상태를 유지하십시오.
- 리스트 맨 앞 원소 처리 남발: list.insert(0, x) 또는 list.pop(0)을 대량 루프 내부에서 반복적으로 사용하면 매번 $O(N)$의 시간 복잡도가 누적되어 성능이 저하됩니다. 대신 collections.deque의 appendleft() 및 popleft()를 사용하여 $O(1)$로 제어해야 합니다.
핵심 정리
| 구분 |
대상 도구 |
시간 복잡도 |
주요 역할 |
| 입력 가속 |
sys.stdin.readline() |
$O(1)$ |
대규모 입력의 버퍼를 한 번에 처리하여 시간 초과 방지 |
| 개행 문자 제거 |
rstrip() |
$O(L)$ |
입력 문자열 끝의 \n을 잘라내어 문자열 일치 판정 보장 |
| 출력 가속 |
sys.stdout.write() |
$O(1)$ |
출력 스트림 버퍼 최적화 (단, 자동 개행 미지원) |
| 정수 나눗셈 |
// 연산자 |
$O(1)$ |
정수 결과만을 반환하여 실수 연산 오차 방지 |
실습 문제
이번 수업의 개념을 직접 적용해보는 연습 문제입니다. CSES 및 SPOJ에서 엄선한 핵심 7문제입니다.
힌트: 8005번은 입출력의 양이 매우 많기 때문에 일반적인 input() 대신 반드시 파이썬 고속 입출력(sys.stdin.readline)을 사용해 풀어야 통과합니다. 8006번은 각 문자의 출현 빈도수를 누적 기록하며 매핑 위치를 계산해야 합니다.