231002 [Day10] JavaScript 주요 문법 (7)

자료구조&알고리즘 - 백트래킹

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

 

백트래킹의 핵심은 가지치기(백트래킹 작성 방법)

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

 

자료구조&알고리즘 -  동적 계획법

동적계획법이란?

• 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식
• 그리디나 백트래킹처럼 특정 알고리즘이 아닌 문제 해결 방식을 의미
• Dynamic Programming(DP)이라고도 부른다.
  • 동적 계획법이 어렵게 느껴지는 원인 중 하나
  • Dynamic 하지 않고 Programming과도 관련이 없다.
• 메모리를 많이 사용하는 대신 빠른 성능
• 메모이제이션(Memoization), 타뷸레이션(Tabulation)이라는 2가지 방법론이 있다.

 

메모이제이션

• 하향식 접근법
• 동적 계획법에서 작은 문제들의 결과는 항상 같다.
• 따라서 이 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 메모이제이션이다.

 

타뷸레이션

• 상향식 접근법
• 필요한 값들을 미리 계산해두는 것
• 메모이제이션은 필요할 때 계산한다면 타뷸레이션은 미리 계산해둔다.
• 보통 코딩 테스트에선 메모이제이션을 쓰는 경우가 대부분이다.

 

동적 계획법 문제 접근법

• 동적 계획법 유형은 키워드만으로 동적 계획법 문제임을 알기 어렵다.
• 그렇기 때문에 문제 유형을 알 수 없다면 다음을 확인해보자.
  • 가장 작은 문제를 정의할 수 있는지?
  • 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙인 있는지?
  • 위 두 가지가 가능하다면 동적 계획법 문제이다.
  • 간혹 메모리를 너무 사용하여 통과 못하는 경우도 있다.