[DAY-7] JS 주요 문법(7)

😉 헷갈렸던 & 몰랐던 부분들만 정리하는 나만의 TIL
😯 모든 강의 내용은 적지 않아요!

오늘의 소감은?
진짜 단어 조각 문제 풀다가 찔끔 울 뻔 했습니다.
저는 알고리즘 유형 중에 그리디와 DP가 가장 어렵단 말이에요!

백트래킹, BFS, DFS만 풀지 말고, 취약한 부분 위주로 연습해야겠습니다.

[1] 백트래킹

• 모든 경우의 수를 탐색하는 알고리즘입니다.
• DFS나 BFS를 이용할 수 있습니다.
• 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기(Pruning)이라 합니다.
• JS는 재귀 효율이 나빠 DFS를 구현할 경우, 스택을 이용하는 것이 좋습니다.
  코딩 테스트에서는 이를 고려하여 재귀로 작성해도 풀 수 있도록 문제를 제출하는 경우가 있습니다.
• 탐색에서 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편합니다.

[+] 실습 코드 - N-Queen

😂오타 하나 때문에 2시간 날린 N-Queen..
디버깅만 한시간 한 것 같은데 i를 1로 잘못 썼었네요 하하
>
풀이 방법은 체스판 전체를 탐색하는 것이 아니라, row로만 탐색합니다.
> row의 인덱스는 행, row의 값은 열로 두고 풀이를 진행합니다.
>
check함수에서 인덱스가 같은 경우에 return false
행, 열에 대한 차가 같은 경우에 (대각선에 위치) return false로 백트래킹해줍니다.

function check(index, row) {
  for (let i = 0; i < index; i += 1) {
    if (row[index] === row[i]) {
      return false;
    }

    if (Math.abs(row[index] - row[i]) === index - i) {
      return false;
    }
  }
  return true;
}

function solution(n) {
  let count = 0;
  let row = new Array(n).fill(0);

  function dfs(index) {
    if (index === n) {
      count += 1;
      return;
    }

    for (let i = 0; i < n; i += 1) {
      row[index] = i;
      if (index === 0 || (index > 0 && check(index, row))) {
        dfs(index + 1);
      }
    }
  }

  dfs(0);
  return count;
}

[2] 동적 계획법(Dynamic Programming)

• 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식입니다.
• 그리디나 백트래킹처럼 특정 알고리즘이 아닌 문제 해결 방식을 의미합니다.
• 메모리를 많이 사용하는 대신 빠른 성능을 자랑합니다.
• 두 가지 방법론이 있습니다.
  

1. 메모이제이션 (Menoization)
   
2. 타뷸레이션 (Tabulation)

[2-1] 메모이제이션

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

[2-2] 타뷸레이션

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

메모이제이션은 필요할 때 계산한다면 (Lazy evalution)
타뷸레이션은 미리 계산해둡니다. (Eager evaluation)
>
보통의 코딩 테스트에서는 메모이제이션을 쓰는 경우가 대부분입니다.

[2-3] 접근법

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

위 두 가지가 가능하다면 동적 계획법 문제입니다.

간혹 메모리를 너무 사용하여 통과 못하는 경우도 생기지만, 이런 경우엔 백트래킹을 이용할 수 있습니다.

[+] 실습 코드 - 단어 조각

😥 풀다가 울뻔했습니다.
>
모든 알고리즘 문제 유형 중 그리디와 dp를 제일 어려워하는 저에게 단어 조각 문제는 정말 힘들었습니다.
>
> 원리)

1. 단어를 문자열에서 잘라서 단어 조각에 있는지 비교합니다.
2. 있으면 해당 단어의 개수로 dp[단어 끝자리 idx + 1]를 갱신합니다.
3. 그 다음 단어부터는 단어 조각에 있을 시, dp[단어 첫자리]+1과 dp[단어 끝자리 idx + 1]를 비교해
   최소 값을 dp[단어 끝자리 idx + 1]에 저장합니다.
4. 매번 dp[단어 끝자리 idx + 1]는 20000(최대값)으로 초기화해주기 때문에,
   만약 반복문이 끝난 후 dp[주어진 문자열의 길이]의 값이 20000보다 같거나 크면 단어 조각들로 해당 문자열을 만들 수 없음을 뜻합니다.
   
   
   예시) banana / [ba, na, n, a]
   
   1. b부터 단어 조각에 있는지 검사합니다.
   → 없으니 dp[1]에는 20000이 그대로 저장 (dp[단어 끝자리 idx] + 1)
   
   2. a로 끝나는 단어인 ba, a를 단어 조각에 있는지 검사합니다.
   → a가 있으니 dp[2] 값은 dp[1] + 1 값 (20001)과 dp[2] (20000) 중 최소값 저장 = 20000
   → ba가 있으니 dp[2] 값은 dp[0] + 1값 (1)과 dp[2] (20000) 중 최소값 저장 = 1
   
   3. n으로 끝나는 단어인 n, an, ban을 단어 조각에 있는지 검사합니다.
   → n이 있으니 dp[3] 값은 dp[2] + 1 값 (2)과 dp[3] (20000) 중 최소값 저장 = 2
   → an과 ban은 없음
   
   4. a로 끝나는 단어인 a, na, ana, bana를 단어 조각에 있는지 검사합니다.
   → a가 있으니 dp[4] 값은 dp[3] + 1 값(3)과 dp[4] (20000) 중 최소값 저장 = 3
   → na가 있으니 dp[4] 값은 dp[2] + 1값 (2)과 dp[4] (3) 중 최소값 저장 = 2
   → ana, bana 없음
   
   …
   
   해당 과정을 반복하다보면 dp의 맨 마지막 부분에 최소 단어의 개수가 저장됩니다. 😊

// 메모이제이션
// 각 단어를 만들 수 있는 최소 갯수의 단어를 저장해놓는다.
// 다음 단어가 들어왔을 때, 저장한 단어 + 다음 최소 갯수 단어
// 만약 최소값이 갱신되면 메모해놓은 단어의 수도 갱신

function solution(strs, t) {
  let tLen = t.length;
  let dp = new Array(tLen + 1).fill(0);
  let answer = 0;

  // k의 범위도 1, 6으로 지정해서 i범위도 편하게 1, tLen + 1로 지정
  // i는 잘라서 단어 조각들과 비교할 '자른 단어'의 끝 글자
  for (let i = 1; i < tLen + 1; i += 1) {
    // 최솟값 비교를 위해 200000으로 초기화 해준다.
    // 만약 해당하는 단어가 단어 조각에 없어서 조건문에 들어가지 않으면
    // 200000이 유지되고 dp[-1]이 >= 200000이면 해당 단어조각들로 문자열을 만들지 못한다는 뜻.
    dp[i] = 200000;

    // 단어 조각의 길이는 1이상 5 이하
    for (let k = 1; k < 6; k += 1) {
      // s부터 i 사이의 문자열을 자를겁니다.
      let s = i - k;

      // 음수면 그냥 맨 첫번째부터 자르는거랑 다를 게 없다.
      if (s < 0) s = 0;

      // s부터 i 전까지 잘라줍니다.
      tSplit = t.substring(s, i);

      // 단어 조각 모음 배열에서 해당 tSplit을 가지고 있으면 dp 배열에서 최솟값을 비교합니다.
      // dp배열[단어 끝자리 idx] = 최소값(dp[단어 끝자리 idx], dp[해당 단어의 첫자리 idx] + 1)
      // 그러니까, 자른 단어가 단어 조각 모음에 있어서 새로 값이 갱신될 수 있는지
      // 아니면 전에 저장된 값 + 1 (단어의 개수 += 1)인지 최소를 구한다.
      if (strs.includes(tSplit)) {
        dp[i] = Math.min(dp[i], dp[s] + 1);
      }
    }
  }

  if (dp[tLen] >= 200000) answer = -1;
  else answer = dp[tLen];

  return answer;
}

---

출처

프로그래머스