[Algorithm] 백트래킹 | DP | 230612

Chaeyeon Lee·2023년 6월 12일

DP TIL 국비지원교육 동적계획법 백트래킹 코딩부트캠프 프로그래머스 데브코스 프론트엔드 데브코스

데브코스 TIL

목록 보기

9/16

📌 백트래킹 Backtracking

모든 경우의 수를 탐색하는 알고리즘으로, DFS/BSF를 이용할 수 있다.
가지치기 : 탐색하지 않아도 되는 곳을 미리 쳐내는 것
DFS/BSF는 많은 경우에 사용이 되므로 외워두는 것이 좋다.

모든 경우의 수를 찾을 수 있도록 코딩하고, 문제에서 특정한 조건을 만족하는 것만 탐색하고 해가 될 수 없는 상황은 조건문으로 탐색 중지하도록 작성한다.

백트래킹의 대표적인 문제: N-Queen

프로그래머스 lv2. N-Queen
방법
1. 퀸을 둔 행과 열은 가지치기한다.
2. 퀸을 둔 대각선 왼쪽/오른쪽은 가지치기 한다.
3. 가지치기를 위해 루프를 통해 검색하는 것은 비효율적이므로, 1차원 배열로 체스판을 구성한다.

배열의 index는 행의 위치, 해당 index의 value는 열의 위치
queen[row] = col;

3-1. 한 idex에 여러 value를 둘 수 없기에 행은 자연스럽게 가지치기 된다.
3-2. index가 같다면 둘 수 없기에 열은 자연스럽게 가지치기 된다.
3-3. 행, 열에 대한 차가 같다면 대각선에 있다는 뜻이므로 가지치기한다.

 Math.abs(queen[i] - queen[row]) === row - i

📌 동적계획법 Dynamic Programming

해결한 작은 문제로 큰 문제를 해결하는 문제풀이 방식으로, 그리디나 백트래킹처럼 특정 알고리즘이 아닌 문제해결방식을 의미한다. 메모리를 많이 사용하는 대신 빠른 성능을 가진다.
동적계획법에는 두 가지 방법론이 있다. =>메모이제이션/타뷸레이션

메모이제이션 Memoization
: 하향식 접근법. 해결한 작은 문제를 메모리 공간에 메모해두었다가 필요할 때 활용하는 것. 캐싱(Caching)이라고도 부른다.
타뷸레이션 Tarbulation
: 상향식 접근법. 필요한 값들을 미리 계산해두고 필요할 때 사용한다. 코딩테스트에서는 메모이제이션을 주로 사용한다.

동적계획법의 대표적인 문제: 피보나치 수열

function fibo(idx) {
  if(idx==1 || idx===2) return 1;
  return fibo(idx-1) + fibo(idx-2);

피보나치 수열은 재귀함수로 간단하게 표현할 수 있지만, 값을 구하는 과정에서 중복으로 계산이 이루어져 비효율적이라는 단점이 있다.

//동적계획법을 써서 표현한 피보나치 수열
const dp=[];
function fibo(idx, dp) {
  if(idx===1 || idx===2) {
    dp[idx]=1;
    return 1;
  }
  if(dp[idx]!==undefined) {
    return dp[idx];
  }
  dp[idx] = fibo(idx-1, dp) + fibo(idx-2, dp);
  return dp[idx];
}