시간 초과 / 메모리 초과 판단법

🕒 시간 초과 판단법

1. 입력 크기로 시간복잡도 예측

입력 크기 N	안전한 시간 복잡도	설명
N ≤ 10	O(N!), 완전탐색도 OK	모두 가능( 브루트포스, 백트래킹)
N ≤ 100	O(N³)까지 OK	삼중 for 문까지 가능, 그래프 연결 확인 문제
N ≤ 1,000	O(N²) 가능 (2중 for문 가능)	이중 for 문 가능, 단순 비교/조합 문제 가능
N ≤ 100,000	O(N log N) 이하 필요	이중 for문 ❌, 정렬/슬라이딩 윈도우/해시처럼 빨라야 함
N ≥ 1,000,000	O(N), O(log N), O(1)만 가능	한 번 훑는 수준만 가능(선형 탐색, 누적 합)

→ 판단 포인트:
☑️ 이중 for문 돌려도 되나?
☑️ 정렬만으로 풀 수 있나?
☑️ 슬라이딩 윈도우 / 해시 / 이분탐색 필요한가?

 

---

☑️ 이중 for문 돌려도 되나?

이중 for문은 시간복잡도 O(N²)이기 때문에,
입력 크기가 커지면(1,000 이상) 바로 시간초과 위험이 생김.

 

✔️ 언제 가능?

N ≤ 1,000 → 이중 for문 OK

N ≥ 10,000 → ❗❗❗ 시간초과 거의 확정

 

💡 실전 예시

# N = 1000일 때
for i in range(N):
    for j in range(N):
        pass  # 이건 O(N^2) → 약 100만 번, OK

# N = 100,000일 때
for i in range(N):
    for j in range(N):
        pass  # 이건 O(N^2) → 100억 번 → 시간초과 🔥

 

 

☑️ 정렬만으로 풀 수 있나?

정렬은 O(N log N) 알고리즘 중에서도 가장 강력하고 빠른 축에 속함
→ 문제에 “최댓값 찾기”, “작은 순서대로 선택하기” 같은 선택 기준이 있으면,
정렬 후 한 번 훑으면 해결되는 문제가 많음.

✔️ 정렬이 유리한 경우

그리디 (예: 가장 짧은 걸 먼저, 가장 작은 걸 먼저 등)

조건 기반으로 정렬 후 반복

순서만 바꾸면 되는 문제

 

💡 실전 예시

ATM 문제 (11399)
사람들의 인출 시간을 오름차순 정렬 → 누적합 → 최소 대기 시간

times = sorted(map(int, input().split()))
total = 0
for i in range(len(times)):
    total += sum(times[:i+1])

 

 

☑️ 슬라이딩 윈도우 / 해시 / 이분탐색 필요한가?

N이 100,000 이상일 때는 O(N log N) 이하 알고리즘이 필수
→ 슬라이딩 윈도우, 해시, 이분탐색은 실전에서 가장 많이 쓰이는 기법

 

💡 슬라이딩 윈도우

지속적으로 “구간합”이나 “최대값” 같은 걸 구해야 할 때

전체 탐색하면 O(N²)인데 → 윈도우로 돌리면 O(N)

 

예시: 누적합이 K 이상인 연속된 구간 길이 구하기

left = 0
sum = 0
for right in range(N):
    sum += arr[right]
    while sum >= K:
        result = min(result, right - left + 1)
        sum -= arr[left]
        left += 1

 

 

💡 해시 (딕셔너리, set)

중복 검사, 빈도 세기, 빠른 포함 여부 검사

리스트로 하면 O(N)인데, 해시는 O(1)

 

예시: 문자 개수 세기

from collections import Counter
c = Counter("ABBAA")
print(c['A'])  # 빠르게 'A' 몇 개인지 출력

 

 

💡 이분탐색

정렬된 배열 안에서 특정 값 탐색할 때

리스트에서 in으로 찾으면 O(N)
→ 이분탐색 쓰면 O(log N)

 

예시: 원하는 값이 배열에 있는지 확인

import bisect
arr = sorted([1, 3, 5, 7, 9])
x = 5
idx = bisect.bisect_left(arr, x)
if idx < len(arr) and arr[idx] == x:
    print("있음")

 

 

🎯 요약

 

---

💾 메모리 초과 판단법

2. 자료구조 크기 감각 익히기

→ 판단 포인트:
☑️ 리스트/딕셔너리 크기가 1,000,000 이상?
☑️ 불필요하게 중복 데이터 저장 중인가?
☑️ 방문 여부 등은 set이나 bool 배열로 최소화 가능?

---

 

☑️ 리스트/딕셔너리 크기가 1,000,000 이상? (백만)

🔍 왜 확인해야 할까?

대부분 코딩 테스트는 메모리 제한이 256MB ~ 512MB

정수형 리스트 하나에 원소 1,000,000개만 넣어도 약 4MB

그런데 리스트 10개, 딕셔너리 2개, set까지 다 쓰면 금방 커짐!

💡 실전 예시

arr = [0] * 1_000_000  # 약 4MB → OK

arr = [0] * 100_000_000  # 약 400MB → 메모리 초과 가능성 높음

 

✔️ 판단 기준

리스트/딕셔너리 크기가 백만 단위를 넘기면 → “혹시 덜 쓸 수는 없을까?” 꼭 고민하기

특히 딕셔너리의 키가 수십만 개 이상일 땐 더 주의

 

 

☑️ 불필요하게 중복 데이터 저장 중인가?

🔍 왜 중요해?

한 정보를 여러 번 저장하거나,

계산에 필요 없는 값까지 저장하면 메모리 낭비가 생김

💡 실전 예시

# 나쁜 예: 굳이 모든 숫자 리스트로 저장
arr = []
for i in range(1_000_000):
    arr.append(i)  # 사실 sum만 구할 거면 불필요

# 좋은 예
total = 0
for i in range(1_000_000):
    total += i  # sum만 필요하니 저장 X

✔️ 실전에서는

“이 값을 저장해서 나중에 꼭 다시 쓸까?”
→ 아니면 계산만 하고 버려도 됨!

 

☑️ 방문 여부 등은 set이나 bool 배열로 최소화 가능?

🔍 방문 체크는 실전에서 자주 나와

DFS/BFS/탐색 문제에서 중복 방문 방지용

이때 visited 배열을 만드는데,
bool 배열 or set으로 줄이면 훨씬 메모리 효율적

💡 예시 비교

# 나쁜 예: 방문한 값들을 리스트로 저장
visited = []
if x not in visited:
    visited.append(x)  # O(N), 메모리도 점점 커짐

# 좋은 예 1: set 사용 (빠르고 메모리 덜 씀)
visited = set()
if x not in visited:
    visited.add(x)

# 좋은 예 2: bool 배열 (값의 범위가 정해져 있을 때)
visited = [False] * 1001
if not visited[x]:
    visited[x] = True

 

 

 

 

🛠 실전에서 체크할 것

• ⏱️ 반복문 안에서 정렬, 슬라이싱, .append() 등 무심코 쓰지 말기
• 🔄 무한루프 위험 없는지 조건 잘 확인하기
• 📦 자료구조 최대 몇 개 쌓이는지 rough 계산해보기

---

 

 

 

🎯 한 줄 요약

 

“입력 크기 보면 시간복잡도가 보여야 하고,  자료 크기 보면 메모리 한계가 보여야 한다.”