입력이 커질 때, 알고리즘이 얼마나 오래 걸리는지와 메모리를 얼마나 쓰는지를 나타내는 기준
1. 시간복잡도
①의미
Ⅰ) 시간복잡도란?
-입력 크기가 커질 때 알고리즘의 실행 시간이 얼마나 증가하는지를 나타냄
-입력 크기는 보통 'n'으로 표현
-예시: 배열에 숫자가 'n'개 있으면, 배열 크기를 'n'으로 봄
②쉬운 예시
Ⅰ) 배열을 한 번 훑는 경우
def find(arr, target):
for x in arr:
if x == target:
return True
return False
-배열에서 원하는 값을 찾는 코드
-최악의 경우 배열 끝까지 전부 확인해야 함
-배열 길이가 'n' 이면 최대 'n'번 확인
-시간복잡도는 'O(n)'
Ⅱ) 첫 번째 값만 확인하는 경우
def get_first(arr):
return arr[0]
-배열이 몇 개든 첫 번째 값만 확인
-입력 크기와 상관없이 한 번만 실행
-시간복잡도는 'O(1)'
2. 공간복잡도
①의미
Ⅰ) 공간복잡도란?
-입력 크기가 커질 때 알고리즘이 메모리를 얼마나 더 사용하는지를 나타냄
-계산하는 동안 추가로 필요한 저장 공간이 얼마나 되는가?
②쉬운 예시
Ⅰ) 추가 배열을 만드는 경우
def copy_array(arr):
new_arr = []
for x in arr:
new_arr.append(x)
return new_arr
-입력 배열 'arr'의 크기가 'n'이면 새 배열 'new_arr'도 크기가 'n'
-추가로 'n'짜리 저장 곤간이 필요함
-공간복잡도는 'O(n)'
Ⅱ) 변수 하나만 쓰는 경우
def sum_array(arr):
total = 0
for x in arr:
total += x
return total
-배열 크기가 커져도 추가로 쓰는 변수는 'total' 하나
-입력 크기와 상관없이 추가 메모리가 거의 일정
-공간복잡도는 'O(1)'
3. Big-O표기법
①의미
Ⅰ) Big-O란?
-알고리즘의 정확한 실행 시간을 초 단위로 재는 것이 아님!
-입력이 커질 때 일의 양이 얼마나 빠르게 증가하는지를 표현하는 방식
-코딩 테스트에서는 보통 최악의 경우를 기준으로 Big-O를 많이 생각함
② 대표적인 Big-O
Ⅰ) O(1)
-입력 크기와 상관없이 거의 일정
-예시: 배열의 첫 번째 값 가져오기
Ⅱ) O(log n)
-입력이 커져도 아주 천천히 증가
-예: 이진 탐색
-매번 탐색 범위를 절반씩 줄이는 경우
Ⅲ) O(n)
-입력 크기만큼 시간이 늘어남
-예시: 배열 전체를 한 번 확인하기
Ⅳ) O(n log n)
-효율적인 정렬에서 자주 나옴
-예시: 병합 정렬, 힙 정렬, 파이썬 기본 정렬
Ⅴ)O(n^2)
-입력이 커질수록 시간이 빠르게 늘어남
-예시: 이중 반복문으로 모든 쌍 비교하기
Ⅵ) (2^n)
-매우 빠르게 폭발적으로 증가
-예시: 모든 부분집합 확인하기
→복잡도 증가 느낌
O(1) → O(log n) → O(n) → O(n log n) → O(n^2) → O(2^n)
4. 자주 나오는 코드별 복잡도
①O(1)
Ⅰ) 한 번만 처리하는 경우
arr[0]
-배열의 크기와 상관없이 특정 위치에 바로 접근
② O(n)
Ⅰ) 반복문 하나로 전체를 확인하는 경우
for x in arr:
print(x)
-원소의 개수만큼 실행
③ O(n^2)
Ⅰ) 이중 반복문으로 모든 조합을 확인하는 경우
for i in range(n):
for j in range(n):
print(i, j)
-바깥 반복문이 'n'번, 안쪽 반복문도 'n'번 돎
-전체는 'n x n' 번
④ O(log n)
Ⅰ) 탐색 범위를 절반씩 줄이는 경우
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return True
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return False
-매번 탐색 범위를 절반으로 줄임
-단, 배열이 정렬되어 있어야 함
5. 시간복잡도와 공간복잡도의 관계
① 시간을 줄이기 위해 공간을 더 쓰는 경우
Ⅰ) 중복 확인 예시
def has_duplicate(arr):
seen = set()
for x in arr:
if x in seen:
return True
seen.add(x)
return False
-'set'을 사용해서 이미 본 값을 빠르게 확인
-시간복잡도는 평균 'O(n)' , 공간복잡도는 'O(n)'
-메모리를 더 쓰는 대신 속도가 빨라짐
② 공간을 아끼지만 시간이 오래 걸리는 경우
Ⅰ) 이중 반복문으로 중복 확인
def has_duplicate(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] == arr[j]:
return True
return False
-추가 저장 공간은 거의 쓰지 않음
-공간복잡도는 'O(1)', 모든 쌍을 비교하므로 시간복잡도는 'O(n^2)'
6. 코디에스트에서 자주 쓰는 판단법
①입력 크기 확인하기
Ⅰ) n이 작을 때
- `n <= 10` 정도면 완전탐색, 순열, 조합도 가능할 수 있음
- 모든 경우를 다 확인해도 시간이 버틸 가능성이 있음
Ⅱ) n이 중간 정도일 때
- `n <= 1,000` 또는 `n <= 2,000` 정도면 `O(n^2)` 풀이가 가능할 때도 있음
- 하지만 제한 시간이 짧으면 조심해야 함
Ⅲ) n이 클 때
- `n <= 100,000`이면 보통 `O(n)` 또는 `O(n log n)`이 필요
- `O(n^2)`은 대부분 시간초과
②제한 조건으로 풀이 예상하기
- `n <= 10` → 완전탐색, 백트래킹 가능
- `n <= 20` → `2^n` 부분집합 탐색 가능할 수도 있음
- `n <= 500` → `O(n^3)` 가능할 수도 있음
- `n <= 2,000` → `O(n^2)` 가능할 수도 있음
- `n <= 100,000` → `O(n log n)` 또는 `O(n)` 필요
- `n <= 1,000,000` → 거의 `O(n)` 수준 필요
7. 코딩 테스트에서 자주 쓰는 자료구조
①리스트
Ⅰ) 인텍스 접근
arr[i]
-시간 복잡도 'O(1)'
Ⅱ) 맨 뒤에 추가
arr.append(x)
-평균 시간복잡도 'O(1)'
Ⅲ) 맨 앞에서 삭제
arr.pop(0)
-앞 원소를 삭제하면 뒤 원소가 앞으로 밀려와야 함
-시간복잡도는 'O(n)'
-큐 문제에서 자주 시간초과를 만드는 실수
② deque
Ⅰ) 큐를 구현할 때 사용
from collections import deque
q = deque()
q.append(1)
q.popleft()
-오른쪽 추가는 'O(1)', 왼쪽 삭제도 'O(1)', BFS 문제에서 자주 사용
③ set
Ⅰ) 중복 확인
seen = set()
-값이 있는지 확인하는 연산이 평균 'O(1)'
-중복제거, 방문 체크에 많이 사용함
④ dict
Ⅰ) 개수 세기
count = {}
for x in arr:
count[x] = count.get(x, 0) + 1
-key로 값을 빠르게 찾을 수 있음
-평균 조회, 삽입은 'O(1)'
-빈도 계산, 매칭, 해시 문제에 많이 사용
⑤ heap
Ⅰ) 우선순위가 필요한 경우
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappop(heap)
- 삽입은 `O(log n)`, 삭제도 `O(log n)`, 최솟값 확인은 `O(1)`
- 가장 작은 값, 가장 큰 값, Top-K 문제에 자주 나옴
8. 코딩테스트에서 자주 쓰는 알고리즘 패턴
①완전탐색
Ⅰ) 모든 경우를 확인하는 방법
-가능한 경우를 전부 확인
-입력이 작을 때 사용
-시간복잡도는 문제에 따라 `O(n)`, `O(n^2)`, `O(2^n)`, `O(n!)` 등이 될 수 있음
②정렬
Ⅰ) 순서를 정리한 뒤 문제를 쉽게 푸는 방법
- 보통 시간복잡도는 'O(n log n)'
- 정렬 후 이진 탐색, 투 포인터, 그리디로 이어지는 경우가 많음
③ 이진 탐색
Ⅰ) 정렬된 데이터에서 빠르게 찾는 방법
-시간 복잡도는 'O(log n)'
-단, 데이터가 정렬되어 있어야 함
Ⅱ) 답의 범위를 탐색하는 경우
-'최소값을 구하라', '최대값을 구하라' 문제에서도 사용
-어떤 값 'x'가 가능한지 검사하고, 가능하면 범위를 줄이는 방식
-이러한 유형을 파라메트릭 서치라고 함
④투 포인터
Ⅰ)두 개의 위치를 움직이며 푸는 방법
-정렬된 배열이나 연속 구간 문제에서 사용
-두 포인터가 한 방향으로만 움직이면 시간복잡도는 'O(n)'
⑤ 슬라이딩 윈도우
Ⅰ) 연속된 구간을 유지하며 푸는 방법
-구간 합, 구간 길이, 연속 부분 배열 문제에 자주 나옴
-시간복잡도 'O(n)'
-단, 구간을 늘리고 줄이는 기준이 명확해야 함
⑥ BFS / DFS
Ⅰ) 그래프나 미로를 탐색하는 방법
- BFS는 가까운 곳부터 넓게 탐색
- DFS는 한 방향으로 깊게 들어갔다가 돌아옴
- 인접 리스트 기준 시간복잡도는 `O(V + E)` //`V`는 정점 개수, `E`는 간선 개수
⑦ DP
Ⅰ) 작은 문제의 답을 저장해서 큰 문제를 푸는 방법
-같은 계산을 반복하지 않기 위해 저장
-경우의 수, 최대값, 최소값 문제에서 자주 나옴
-시간복잡도는 보통 '상태 수 x 각 상태에서의 선택 수'로 계산
⑧ 그리디
Ⅰ) 매 순간 가장 좋아 보이는 선택을 하는 방법
-정렬과 함께 자주 사용
-보통 'O(n)' 또는 'O(n log n)' 이 많이 나옴
-단, 지금의 선택이 전체적으로도 최적인지 확인해야 함
중복 확인 → set, dict
최단 거리 → BFS
정렬된 배열 탐색 → 이진 탐색
연속 구간 → 슬라이딩 윈도우
모든 조합 → 완전탐색 / 백트래킹
최대·최소·경우의 수 → DP 가능성 확인
9. 실전에서 복잡도 계산하는 방법
| 구분 |
확인할 것 |
판단 기준 |
자주 나오는 복잡도 |
예시 |
| 1 |
반복문 개수 |
반복문이 몇 겹인지 본다 |
O(n), O(n^2), O(n^3) |
for i in range(n) → O(n) |
| 2 |
중첩 반복문 |
바깥 반복문과 안쪽 반복문이 모두 n번 도는지 본다 |
O(n^2) |
for i in range(n): for j in range(n): |
| 3 |
반복 횟수 감소 |
반복할 때마다 범위가 절반씩 줄어드는지 본다 |
O(log n) |
이진 탐색 |
| 4 |
배열 전체 순회 |
배열이나 리스트를 처음부터 끝까지 한 번 보는지 본다 |
O(n) |
최댓값 찾기, 합 구하기 |
| 5 |
정렬 사용 |
정렬을 먼저 하는지 확인한다 |
O(n log n) |
arr.sort() |
| 6 |
해시 사용 |
set, dict로 빠르게 찾는지 본다 |
평균 O(1) |
중복 확인, 빈도 계산 |
| 7 |
재귀 사용 |
함수가 자기 자신을 몇 번 호출하는지 본다 |
상황에 따라 다름 |
팩토리얼, DFS |
| 8 |
추가 배열 사용 |
입력 외에 새 리스트나 배열을 만드는지 본다 |
공간복잡도 O(n) 가능 |
복사 배열 만들기 |
| 9 |
변수만 사용 |
배열 없이 변수 몇 개만 쓰는지 본다 |
공간복잡도 O(1) |
합계, 최대값 저장 |
| 10 |
큐/스택 사용 |
deque, stack 등을 쓰는지 본다 |
보통 O(n) 또는 연산당 O(1) |
BFS, 괄호 검사 |
| 11 |
그래프 탐색 |
정점과 간선을 모두 방문하는지 본다 |
O(V + E) |
BFS, DFS |
| 12 |
모든 경우 탐색 |
가능한 경우를 전부 확인하는지 본다 |
O(2^n), O(n!) 등 |
부분집합, 순열 |
- 시간복잡도는 입력이 커질 때 얼마나 빨리 느려지는가를 보는 개념
- 공간복잡도는 보통 입력 자체보다 추가로 쓰는 메모리를 중심으로 보는 경우가 많음
- 정렬은 O(n log n) 비용이 들지만, 정렬한 뒤에 문제를 휠씬 쉽게 풀 수 있는 경우가 많음
- 해시는 메모리를 더 쓰는 대신 탐색을 빠르게 만들어줌
- 재귀는 코드가 깔끔해질 수 있지만, 깊이가 너무 커지면 스택 문제나 재귀 제한 문제가 생길 수 있음
!Big-O에서 상수는 보통 무시
!리스트의 pop(0)을 큐처럼 쓰면 위험
!큐가 필요하면 deque를 쓰는 게 좋음
!이진 탐색은 아무 배열에나 쓰는 게 아님⇒ 정렬되어 있거나, 답의 가능 여부가 일정한 방향으로 나뉘는 구조가 있어야 함
!슬라이팅 윈도우는 연속 구간 문제에 자주 쓰이지만, 음수가 섞이면 단순하게 적용되지 않을 수 있음
!set, dict 평균적으로 빠르지만, 공간을 추가로 사용함
!재귀 함수는 호출 스택도 공간복잡도에 포함해야 함