1. 입출력(I/O) 속도 최적화

입력 데이터가 10만 줄 이상 넘어가는 문제에서는 알고리즘보다 입출력 방식이 병목(Bottleneck)이 되는 경우가 많습니다.

• ❌ input() (가장 느림)
  • 내부적으로 프롬프트 메시지를 확인하고 개행 문자를 지우는 등 불필요한 처리가 많아 대량 입력 시 무조건 시간 초과가 발생합니다.
• ✅ sys.stdin.readline() (권장 / 표준)
  • 한 줄씩 버퍼를 통해 읽어와 속도가 매우 빠릅니다.
  • 메모리를 적절히 관리할 수 있어 코딩 테스트에서 가장 기본적으로 세팅해야 하는 방식입니다.
• 🚀 sys.stdin.read().split() (가장 빠름)
  • 파일 전체를 단 한 번의 시스템 콜(Syscall)로 메모리에 올린 뒤 쪼개는 방식입니다.
  • 입력 속도는 타의 추종을 불허하지만, 데이터 전체를 한 번에 메모리에 올리므로 메모리 제한이 빡빡한 문제에서는 주의해야 합니다.

💡 [Tip] 출력 최적화 정답이 10만 개일 때 print()를 10만 번 호출하면 멈춥니다. 결과를 sys.stdout.write(str(ans) + '\n')로 그때그때 출력하거나, 문자열 배열에 모아두고 "".join()으로 한 번에 출력하세요.

2. 자료구조의 올바른 선택

리스트의 양끝 요소 조작 (Queue 구현)

리스트(list)는 맨 뒤에 값을 추가/삭제할 때는 빠르지만, 맨 앞(index 0)을 건드리는 순간 재앙이 시작됩니다.

• ❌ list.pop(0), list.insert(0, x) (절대 금지)
  • 맨 앞의 원소를 빼거나 넣으면, 뒤에 있는 모든 원소의 인덱스를 한 칸씩 당기거나 밀어야 하므로 $O(N)$의 시간이 걸립니다. 수백만 번 반복되면 무조건 시간 초과가 납니다.
• ✅ collections.deque 활용
  • 양방향 연결 리스트 기반이므로 popleft()와 appendleft()를 $O(1)$의 속도로 즉시 처리합니다.
  • ⚠️ 주의: 파이썬 내장 모듈인 queue.Queue()는 멀티스레드 환경의 락(Lock) 기능이 포함되어 있어 알고리즘 문제에서는 불필요하게 무겁고 느립니다. 무조건 deque를 쓰세요.

탐색 연산 (in 연산자)

특정 값이 컨테이너 안에 존재하는지(if x in data) 찾을 때 자료구조에 따라 속도가 천차만별입니다.

• ❌ list, tuple ($O(N)$): 처음부터 끝까지 순차적으로 전부 뒤져서 찾습니다.
• ✅ set, dict ($O(1)$): 해시(Hash) 테이블 기반이므로, 데이터가 1억 개라도 단번에 찾아냅니다. 중복 검사나 방문 처리에 필수적입니다.

3. 문자열과 다차원 배열(List) 최적화

문자열 결합 (String Concatenation)

파이썬의 문자열은 불변(Immutable) 객체입니다.

• ❌ str += "a" 처럼 더하기 연산을 반복하면, 매번 새로운 문자열 메모리를 붕어빵 찍듯 새로 만들어내어 엄청난 시간/메모리 낭비가 발생합니다.
• ✅ 수정이 잦은 문자열은 list("문자열")로 변환하여 인덱스로 수정한 뒤, 맨 마지막에 "".join(list)로 합치는 것이 훨씬 효율적입니다.

다차원 배열(2차원 리스트) 초기화 함정

• ❌ [[0] * M] * N
  • 겉보기엔 멀쩡하지만 '얕은 복사'가 일어나 모든 행이 같은 메모리 주소를 공유합니다. arr[0][0]을 바꿨는데 모든 행의 첫 번째 값이 똑같이 바뀌는 대참사가 발생합니다.
• ✅ [[0] * M for _ in range(N)]
  • 리스트 컴프리헨션을 사용해야 각각 독립적인 메모리를 가진 완벽한 2차원 배열이 생성됩니다.

4. 파이썬 문법 특성을 살린 고급 최적화

① 변수 스코프 (전역 변수 vs 지역 변수)

• 파이썬 엔진 구조상, 함수 바깥의 전역 변수(Global)를 읽는 속도보다 함수 내부의 지역 변수(Local)를 읽는 속도가 훨씬 빠릅니다.
• 코드를 바깥에 들여쓰기 없이 나열하지 말고, def solve(): 형태의 메인 함수를 만들어 그 안에서 로직을 실행하세요.

② 메서드 지역 변수 할당 (Look-up 최적화)

• 반복문 안에서 arr.append(x)를 수백만 번 호출하면, 매번 arr 객체에서 append라는 메서드 이름을 찾는(Look-up) 오버헤드가 발생합니다.
• 반복문 시작 전에 my_append = arr.append처럼 미리 지역 변수에 빼두고, 내부에서는 my_append(x)만 호출하면 탐색 시간을 획기적으로 줄일 수 있습니다.

③ 내장 함수 활용

• 파이썬의 sum(), max(), min() 등은 C언어로 고도로 최적화되어 있습니다.
• 본인이 직접 for문을 돌리면서 더하거나 최댓값을 찾는 것보다 내장 함수를 호출하는 것이 압도적으로 빠릅니다.

④ 파이썬의 꽃: 컴프리헨션(Comprehension) 완벽 활용

파이썬에서 append()를 반복하는 것은 하수입니다. C언어 수준에서 최적화되어 동작하는 컴프리헨션과 제너레이터를 사용하면 속도와 메모리를 동시에 잡을 수 있습니다.

① 리스트 컴프리헨션 (List Comprehension)

단 한 줄로 배열을 생성하고 필터링하는 파이썬의 핵심 문법입니다. append() 메서드를 찾는(Look-up) 시간을 생략하여 일반 for문보다 훨씬 빠릅니다.

• [✅ 예시] 짝수만 골라서 제곱한 리스트 만들기
  • [i * i for i in range(100) if i % 2 == 0]

② 딕셔너리 & 집합 컴프리헨션

리스트([]) 대신 중괄호({})를 사용하여 빠른 탐색을 위한 구조를 단번에 만듭니다.

• [✅ 딕셔너리] words = {word: len(word) for word in lst} (빈도수나 매핑 테이블 생성 시 압도적으로 빠름)
• [✅ 집합(Set)] uniques = {x for x in lst} (생성과 동시에 자동으로 중복을 제거)

③ ⭐️ 제너레이터 표현식 (메모리 초절약)

가장 중요한 팁입니다! 데이터가 수백만 개일 때 대괄호 []를 쓰면 메모리가 터지지만, 소괄호 ()를 쓰면 "필요할 때마다 하나씩 꺼내주는 기계"만 생성되어 메모리 사용량이 0에 수렴합니다.

• ❌ sum([i**2 for i in range(10000000)]) (1,000만 개 배열 생성 👉 메모리 폭발)
• ✅ sum(i**2 for i in range(10000000)) (제너레이터 사용 👉 메모리 초절약)

5. 메모리와 시뮬레이션 문제 팁

① 배열 깊은 복사 최적화 (BFS/DFS)

삼성 역량 테스트 같은 시뮬레이션 문제에서 2차원 배열(지도)을 백업할 일이 많습니다.

• ❌ copy.deepcopy(arr): 완벽하게 복사되지만 너무 느려서 무조건 시간 초과가 납니다.
• ✅ [row[:] for row in arr]: 슬라이싱을 이용한 복사 방식이 deepcopy보다 7~10배 이상 빠릅니다.

② 가비지 컬렉터(GC) 멈춤 현상 방지

파이썬은 사용하지 않는 메모리를 자동 청소하는 GC가 주기적으로 돕니다. 반복문 내부에서 무의미하게 배열 객체를 계속 새로 생성하면 GC가 발동해 프로그램이 뚝뚝 끊깁니다. 배열은 반복문 밖에서 한 번만 선언하고 내부 값만 덮어씌우는 것이 좋습니다.

③ 극악의 메모리 제한 (계수 정렬)

메모리가 8MB밖에 안 되는데 1,000만 개의 숫자가 입력되는 문제(예: 백준 10989번)에서는 리스트에 .append()를 하는 순간 즉시 메모리 초과(MLE)가 뜹니다.

• 이럴 땐 데이터 범위만큼 미리 빈 배열(arr = [0] * 10001)을 만들어두고, 숫자가 입력될 때마다 해당 인덱스의 값에 +1만 더해주는 카운팅(계수 정렬) 방식을 사용해야만 통과할 수 있습니다.

💡 최종 결론: 그래도 안 된다면?

로직은 완벽하고 위의 모든 최적화를 다 적용했는데도 시간 초과가 발생한다면, 제출 언어를 PyPy3로 변경해 보세요. 내부적으로 JIT(Just-In-Time) 컴파일러를 사용하기 때문에 잦은 반복문 연산에서 Python3보다 수십 배 빠릅니다. (단, PyPy3는 메모리를 더 많이 먹으므로 상황에 맞게 선택해야 합니다.)