분명 맞는 답이라고 생각했는데, 왜 내 코드는 백준에서 시간 초과가 뜰까?
그건 너가 아직 시간을 지배하는 자가 되지 못했기 때문이지...후훗

시간 복잡도

• 프로그램을 실행하는 데 필요한 시간으로, 알고리즘의 성능을 평가하는 기준
• 입력 크기에 따른 코드의 연산 횟수로 측정
  • 입력 크기를 $N$으로 일반화하여 연산 횟수를 나타냄
• 최악의 경우, 즉 제일 오래 걸린 경우에 대한 시간 복잡도를 가정

빅오 표기법

• 입력 크기가 $N$일 때의 연산 횟수가 $f(N)$일 때
• $f(N)$의 최고차항을 남기고 계수를 지워 $O(...)$로 표기
  • $3N^2+5N+6$ -> $O(N^2)$
  • $2^N+10N^5+5N^2$ -> $O(2^N)$
• 오 엔 제곱, 오 이의 엔제곱과 같이 읽으면 됨
• 2가지 이상 계산으로 구성된 알고리즘의 복잡도는, 차원이 높은 쪽의 복잡도를 우선으로 함
• $O(1)$ < $O(log N)$ < $O(N)$ < $O(N log N)$ < $O(N^2)$ < $O(N^3)$ < $O(N^k)$ < $O(2^N) < O(N!)$ 순으로 높음

시간 복잡도 계산하기

별 찍기 문제

• 숫자 $N$을 입력받으면, $N$번째 줄까지 별을 1개에서 $N$개까지 찍기

def stars(n):
    for i in range(1, n + 1):
        print("*" * i)

• 별 하나를 찍을 때마다 연산 1회 수행
• 즉 총 연산 수는 $(1 + 2 + ... + N) = \frac{N(N+1)}{2} = \frac{N^2+N}{2}$
• 빅오 표기법으로 $O(N^2)$

박테리아 수명 문제

• 초기 박테리아 세포 수가 $N$개이고 해마다 세포 개수가 작년의 반으로 줄어듦
  • 단, 홀수인 경우 버림
• 언제 모든 박테리아가 죽을지 계산하기

def bacteria(n):
    count = 0
    while n >= 1:
        n /= 2
        count += 1
    else:
        return count

• A년 후의 박테리아 수는 $(\frac{1}{2})^AN$
• $(\frac{1}{2})^AN < 1$인 $A$ 찾기 (단, $A$는 자연수)
  • $N$으로 나누면 $(\frac{1}{2})^A$ < $\frac{1}{N}$
  • 역수를 취하면 $2^A > N$
  • 양변에 로그를 취하면 $A > \log_2(N)$
• 즉 박테리아의 소멸 시기는 $\lfloor\log_2(N)\rfloor + 1$
  • $\lfloor x \rfloor$: $x$를 내림해서 정수로 만듦
• 빅오 표기법으로 $O(\log N)$

시간제한 안에 문제 풀기

• 일반적으로 백준의 시간 제한은 1초
• $N$의 크기에 따라, 허용 가능한 최대 시간 복잡도가 달라짐
• 컴퓨터는 1초에 대략 1-2억번 연산이 가능
  • 하지만 입출력, 메모리 접근, 언어 성능 차이 등 여러 요인 때문에 실제로는 O(N) 기준 약 1천만 정도를 안정적인 한계로 봄

N 크기	가능한 최대 시간 복잡도	예시
약 $10$	$O(N!)$	조합, 순열 등
약 $20$	$O(2^N)$	완전 탐색 등
약 $500$	$O(N^3)$	삼중 반복문
약 $5,000$	$O(N^2)$	이중 반복문
약 $1,000,000$~$2,000,000$	$O(N \log N)$	정렬
약 $10,000,000$~$20,000,000$	$O(N)$	단일 반복문, 선형 탐색
사실상 무한	$O(\log N)$	이진 탐색
무한	$O(1)$	수식을 이용한 신박한 풀이

• Python은 C, C++에 비해 느려 이 기준에 만족해도 오답이 뜰 수 있음
  • 이럴 땐 PyPy로 바꿔 보기
  • (추가 시간 없음)으로 명시되지 않았을 시, Python에 추가 시간을 주는 문제들도 많음
• $O(1)$인 연산: set.add() / .remove(), x in set, dict[key], x in dict, list[idx], list.append(), list.pop(-1), deque.popleft(), 등
• $O(N)$인 연산: list.pop(0), list.index, list.insert, list.count, x in list, list[:-1] 등

공간 복잡도

• 프로그램 실행에 메모리와 파일 공간이 얼마나 필요한지를 평가하는 기준
• 입력 크기에 따른 사용되는 메모리 크기로 측정
  • 입력 크기를 $N$으로 일반화하여, 몇 개의 메모리 단위를 사용하는지 나타냄
  • 보통 변수 하나, 배열 한 칸에 저장되는 데이터 양을 1개의 메모리 단위로 봄

예시

• $O(1)$: 고정된 변수 몇 개만 써서, 입력과 상관없이 메모리가 많이 필요하지 않음

N = int(input())
total = 0
for _ in range(N):
	total += int(input())	

• $O(N)$: 입력을 일차원 배열에 저장

N = int(input())
array = []
for _ in range(N):
  array.append(input())

• $O(N^2)$: 입력을 이차원 배열에 저장

N = int(input())
table = [[0] * N for _ in range(N)]
for i in range(N):
  for j in range(N):
    table[i][j] = int(input())

함수의 공간 복잡도

• 함수의 공간 복잡도를 계산할 땐, 함수에 매개변수로 전달된 외부 데이터(e.g., 배열)의 크기는 고려하지 않음
• 함수 내에서 새로 할당된 메모리만 공간 복잡도에 포함함

e.g., 버블 정렬

def bubble_sort(a):
    N = len(a)
    
    for i in range(N - 1):
        for j in range(N - 1, i, -1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]

• 함수가 길이 $N$의 배열 a을 매개변수로 받더라도, 함수 내에서는 N, i, j변수에 대한 공간만 새로 할당되므로 공간 복잡도는 $O(1)$