코딩 인터뷰를 위한 알고리즘 치트시트

기본 아이디어

• 데이터 구조의 기본 저장 방법은 배열(순차 저장)과 연결리스트(체인 저장) 두 가지다.
• 문제를 분석할 때는 반드시 재귀, 하향식, 추상적인 방식으로.

DP

• 최대값 구하기 문제가 나오면, 먼저 가능한 모든 결과를 탐색하는 무차별 탐색을 반사적으로 떠올릴 수 있도록 하자. 그런 후, 복잡도가 기하급수적으로 증가하는 것을 발견하면 DP 로 전환하라.
• "정의, 상태, 선택"
• dp 배열의 정의를 잘 잡아야 한다 : dp[i]는 "nums[0..i]의 maximum subarray" 인가, 아니면 "숫자가 nums[i] 로 끝나는 maximum subarray"인가?
• 순회하는 방향에 대해서 :
  1. 순회 과정에서 필요한 상태는 이미 계산되어 있어야 한다
  2. 순회의 끝은 구하고자 하는 최종 결과가 저장되는 위치여야 한다.

for i in range(1, n):
    for j in range(0, i):
        dp[i] = max(dp[i], dp[j] + ...)

recursive (e.g., tree)

• 재귀 문제를 푸는 세 가지 키 : (DP의 "정의, 상태, 선택" 과 본질적으로 동일함)
  • 함수는 무슨 일을 해야할까?
  • 함수의 매개변수는 무엇이어야 할까?
  • 함수의 재귀 결과로 무엇을 해야 할까?

Binary search

• lower_bound 가 반환하는 1은, nums 배열에 주어진 수보다 작은 숫자가 1개 있다는 의미이다.
• 해당 값 찾기 : right = nums.length - 1 -> [left, right] 구간 탐색 -> while (left <= right) -> right = mid - 1 -> 반환하는 값은 mid
• 왼쪽 가장자리 찾기 : right = nums.length -> [left, right) 구간 탐색 -> while (left < right) -> right = mid -> 반환하는 값은 left (미리 범위 체크 필요)
• 오른쪽 가장자리 찾기 : 위와 동일하지만 left = mid + 1 이라서 반환하는 값은 right - 1 (미리 범위 체크 필요)

Sliding window

while (right < s.length()) {
    // 윈도우 확대
    updateStatus()
    right++
    
    while (shouldShrink()) {
        updateStatus()
		left++    
    }
}

복잡도

• 시간 복잡도를 줄이는 기본적인 방법은 공간을 시간과 교환하는 것이다 (e.g., hashmap)
• 많은 2차 dp 는 1차 dp 로 압축이 가능하다.

Greedy

• 무차별 대입을 사용하면 지수 수준의 시간이 소요됨 -> DP 를 적용하여 하위 중복 문제를 제거할 수 있다면 다항식 수준의 시간이 소요됨 -> 그리디 속성을 만족한다면 선형 수준의 시간이 소요됨

Union-Find

• 경로 압축을 하더라도 추가적으로 각 union 별 size 정보를 들고 있는게 나음 - 트리를 극한으로 평평하게 만들 수 있기 때문