[CS] 코딩테스트 접근 방법

1. 시간제한 : 보통 1초 이내

- 코딩테스트에서 보통 1초에 약 1억번(10^8) 연산이 가능하다

- N을 보고 O(N^2)을 써도 되는지, O(N)까지 제한되는지 감을 잡아야 한다!!

입력크기 N	시간제한	알고리즘
N<= 20	O(N^2)	브루트포스, 백트래킹
N<= 1000	O(N^2)	이중 반복문, DP
N<= 10^5	O(N log N)	정렬, 이진탐색, 해시, 슬라이딩 윈도우
N<= 10^6 이상	O(N)	누적합, 투포인터, 해시, deque, 그리디

 

1) 입력크기 N <= 20일때=> O(N^2) 가능=> 완전탐색 가능! => 브루트포스, 백트래킹

- O(2^n) 의 경우 2^20 = 1,048,576으로 약 백만이 되므로, 가능!

- n=20일때, 20!는 2.4*10^18로 너무 커서 안됨

 

2) 입력 N<= 1,000 일때 => 이중 반복문, DP

- 시간복잡도: O(N^2)이면 N*N = 1000*1000 = 1,000,000, 연산량이 약 100만번 => 1초안에 처리 가능

* 파이썬은 느린 인터프리터 언어라 1억번이 이론적으로 1초에 가능하지만, 파이썬은 시간초과

** 루프 내부에 단순 계산이 아닌 조건문, 리스트 접근, 비교 등 부가 연산이 포함되기 때문에 추가 시간이 필요

=> 10000이 아니라 1000을 기준으로 하는 이유

 

3) 입력이 최대 100,000개(10^5) => O(N log N) 또는 O(N) 도 가능=> 정렬, 해시, 슬라이딩 윈도우로 풀어야함

- 100,000 log 100,000 = 약 100만번 => 1초 안에 처리 가능

 

4) 입력이 최대 1,000,000개(백만개, 10^6) => O(N log N)도 가능 

- 1000,000 log 100,000 = 대략 10^7이니까 10^8 이내에 처리 가능

import math

n=10**6
print(n*math.log2(n)) 

# math.log는 밑이 자연상수(e=2.718....)인 자연로그 ln이다
# 시간복잡도는 log의 밑을 2로쓰지만 2나 e나 10이나 상수배 밖에 차이안남

 

5) 입력이 1,000,000보다 클때 => O(n) 이하만 안정적

 

6) 시간복잡도 계산하기

- 백준: https://www.acmicpc.net/problem/24267

- 코드 1은 몇 번 수행될까? => 1부터 n까지 숫자 중에서 서로 다른 3개를 골라서, 항상 오름차순 i<j<k으로 뽑는 경우(조합)

=> n(n-1)(n-2)/3! , 순서있게 3개 고르는 경우/3개 순서를 무시해서 중복 제거

for i in range(1, n - 1):
    for j in range(i + 1, n):
        for k in range(j + 1, n + 1):
            # 코드1

반복문구조	의미	수학적으로
1중 for문	n번 반복	n
2중 for문 (i<j)	서로 다른 2개 고르기	n(n-1)/2 = nC2
3중 for문 (i<j<k)	서로 다른 3개 고르기	n(n-1)(n-2)/6 = nC3
4중 for문 (i<j<k<l)	서로 다른 4개 고르기	nC4

 

2. 메모리 제한 : 보통 128MB 이내

- 메모리 제한이 낮으면 불필요한 배열 할당이나 DP 테이블에 주의해야 한다.

- 컴퓨터는 1MB = 2^20 =1,048,576B, 즉 1MB = 약 10^6B(바이트)

단위	크기	이유
1KB	2^10(=1,024bytes)	2진수 중 1000이랑 가장 가까움
1MB	2^20(=1,048,576bytes)	1024*1024
1GB	2^30(1,073,741,824 bytes)	1024*1024*1024

- 128MB = 128*1,024*1,024 bytes = 134,217,728 bytes

- 예1: int 100만개 저장 =>  arr = [0]*10^6 => 4바이트*10^6 => 4MB
- 예2: 2차원 배열 arr = [[0]*1000 for _ in range(1000)] => 1000^2=10^6 =>4BM

자료형	크기	코딩테스트에서 많이 쓰는 메모리제한 128MB 기준
int	계산 편의상 4바이트(32비트) * python은 가변길이	128*1024*1024 / 4 = 33,554,432 => 가변길이 감안 32,000,000개 => [0]*32*10^6 까지 사용 가능 * 64MB제한이면 /2 해서 16*10^6개
float	8바이트
bool	1바이트	약 128*10^6개
char	1바이트
list	int 리스트	1차원: 128*1024*1024 / 4 = 33,554,432 => 가변길이 감안 32,000,000개 => [0]*32*10^6 까지 사용 가능 * 64MB제한이면 /2 해서 16,000,000개 2차원: 5600*5600 = 31,360,000개
dict, set	내부요소*각요소크기+오버헤드	int리스트보다 적게, set(range(10,000,000) dict, set은 키/값 크기에 따라 달라 보수적으로 잡아야 함 * set은 키 값만 저장하지만, 내부 구조가 복잡해 메모리를 더 많이 사용 (대략 int 리스트보다 30~50% 더 많이 사용)

* 파이썬은 int가 가변 크기라서 실제론 4바이트보다 더 많은 메모리를 사용 => 최대치보다 약 70~80% 까지만 사용하는게 안전함

** 메모리 초과 방지 팁

1) 아주 큰 배열 필요 : 필요할 때만 만들기(lazy allocation)

2) dict/set 크기 커짐 : 값 누적 전에 조건 필터링

3) 문자열 계속 더하기: ''.join()사용 (불변 특성 때문)

 

3. 문제 유형과 알고리즘 매칭

문제 유형	추천 알고리즘
최댓값/ 최솟값 찾기	정렬, heap, 그리디
모든 경우 탐색	브루트포스, 백트래킹
최단 경로	BFS(무가중치), 다익스트라
최소 횟수 이동	BFS(큐 기반)
구간 합, 빈도	누적합, 해시
연결성 검사	DFS, BFS, 유니온파인드
경우의 수, 최댓값 계산	DP
문자열 처리	투포인터, 슬라이딩 윈도우

 

4.