[Day 10] JavaScript 주요 문법 (7)

Today I Learn📖

• 백트래킹 (강의)
• 동적계획법 (강의)

백트래킹

: 모든 경우의 수를 탐색하는 알고리즘

• DFS / BFS 이용
• 자바스크립트는 재귀 효율이 나쁘기 때문에, DFS로 구현할 경우에는 스택 사용 추천 (코테에선 재귀로도 풀 수 있게 내는 경우 있음)
• 탐색에서 순환이 발생할 수 있다면 BFS를 이용하기
• 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기(Pruning)라고 함

가지치기 방법

1. 모든 경우의 수를 찾을 수 있도록 코딩
2. 문제의 특정 조건을 만족하는 것만 탐색하고 나머지는 탐색하지 않도록 조건문 작성
   => 절대로 답이 될 수 없는 것은 탐색 안 함(탐색 종료)

---

동적계획법 (= DP, Dynamic Programming)

: 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식 (특정 알고리즘이 아님)
-> 메모리를 많이 사용, 대신 빠른 성능
-> 메모이제이션(Memoization) / 타뷸레이션(Tabulation) 방법 사용 가능

메모이제이션 (Memoization)

• 하향식 접근법
• 이미 해결한 작은 문제들의 결과들을 메모리에 저장해, 필요할 때마다 꺼내 쓰는 것 (DP에서 작은 문제들의 결과는 항상 같기 때문)
• 대부분 DP 유형 코테에서 사용되는 방식 !!
• 필요할 때 계산함 (Lazy evaluation)

타뷸레이션 (Tabulation)

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

동적 계획법(DP) 문제 접근법
1. 가장 작은 문제를 정의할 수 있는가?
2. 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙이 있는?
위 2가지가 가능하면 동적 계획법 문제임
(동적 계획법 유형은 키워드만으로 파악하기 어려움... 그러니까 문제 유형을 알 수 없다면 DP 의심하기 !)

• 가끔 메모리를 너무 사용해서 통과 못하는 경우 있음
  -> 이땐 백트래킹 이용하기

---

😊오늘의 느낀점😊

백트래킹이라는 알고리즘 유형에 대해 배웠다. 그래프 문제인데 거기서 조건을 빠르게 쳐내는 유형인듯 ?
DP는 알고리즘이 아니라 문제 풀이법 중 하나라는 걸 알게되었고, 문제 유형이 감이 안 오면 DP를 의심하라는 꿀팁도 배웠다 ㅎㅎ
같이 주신 해당 유형 알고리즘 문제 풀어보면서 직접 익히니까 더 이해가 잘 된당 (ᐢ 'ᵕ' ᐢ )