TIL8 - 2023.10.02

백트래킹

• 모든 경우의 수를 탐색하는 알고리즘
• DFS나 BFS를 이용할 수 있다
• 가지치기(Pruning) : 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것
• 자바스크립트는 재귀 효율이 나쁘게 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다
• 탐색에서 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다
• 핵심은 가지치기 !!!

백트래킹 로직을 어떻게 작성할 것인가?

• 우선 모든 경우의 수를 찾을 수 있도록 코딩
• 이후 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머지는 탐색하지 않도록 조건문을 작성
• 즉, 절대로 답이 될 수 없는 문제는 탐색을 종료한다

동적계획법

• 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식
• 그리디(Greedy)나 백트래킹처럼 특정 알고리즘이 아닌 문제 해결 방식을 의미
• Dynamic Programming(DP)이라고도 부른다
• 메모리를 많이 사용하는 대신 빠른 성능을 자랑한다
• 두 가지 방법론 : 메모이제이션(Memoization), 타뷸레이션(Tabulation)

메모이제이션

• 하향식 접근법
• 작은 문제들의 결과를 저장해 두었다가 필요할 때 꺼내 쓰는 것
• 필요할 때 계산(Lazy evaluation)
• ex) 피보나치 수열

타뷸레이션

• 상향식 접근법
• 필요한 값들을 미리 계산해두는 것(Eager evaluation)

동적 계획법 문제 어떻게 접근할까?

• 가장 작은 문제를 정의할 수 있는지?
• 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙이 있는지?