수업 목표 및 동기부여

- 파이썬의 표준 입출력과 고속 입출력의 구조적 성능 차이를 학습합니다. - 대용량 데이터 처리 시 입출력 병목으로 인한 TLE를 예방합니다. - 주요 파이썬 컨테이너 연산들의 시간 복잡도를 명확히 파악합니다. - CSES 8000번~8004번 문제를 설계하고 파이썬으로 구현합니다.

고속 입출력 기법

sys 모듈을 활용하여 대규모 입력을 버퍼를 통해 한 번에 읽어들입니다.

import sys

# 1. 한 줄 읽고 줄바꿈 제거
line = sys.stdin.readline().rstrip()

# 2. 공백으로 구분된 다수의 정수 읽기
a, b, c = map(int, sys.stdin.readline().split())

# 3. 고속 출력 처리
sys.stdout.write(str(a) + "\n")

파이썬 자료형별 시간 복잡도 요약

- 리스트: append/pop은 $O(1)$, insert(0,x)/pop(0)은 $O(N)$ - 딕셔너리: 키 탐색 및 삽입은 평균 $O(1)$ - 집합: 원소 추가 add(x), 탐색 모두 $O(1)$ - 탐색이 잦은 알고리즘에는 반드시 set/dict를 사용해야 합니다.

이상한 알고리즘 (CSES 1068, 8000번)

주어진 자연수 $N$에 대해 아래 과정을 반복하여 출력합니다. - $N$이 짝수이면 $N = N // 2$ - $N$이 홀수이면 $N = 3N + 1$ - $N = 1$이 될 때까지 수열을 공백으로 출력

이상한 알고리즘 구현 코드

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()

자주 하는 실수 요약

- rstrip() 누락: 문자열 비교 시 항상 거짓이 반환되는 원인 - 나누기 연산자(/) 오용: 소수점 발생으로 오답 처리 - 리스트 pop(0) 남발: $O(N)$ 누적으로 성능 저하 → deque 활용