Leetcode 2638. Count the number of k-free subsets (ft.개인적인 알고리즘 회고)

질문 

- 정수 배열 nums와 정수 k가 주어졌을 때, 두 요소 간의 차이가 k인 쌍이 없는 부분집합을 k-프리 부분집합이라고 한다
- nums의 모든 k-프리 부분집합의 개수를 구하라

 

 

 

알고리즘 풀이 방법 정리

백트래킹(Backtracking)과 동적 계획법(Dynamic Programming, DP)은 둘 다 재귀를 사용하는데, 사실 차이를 잘 몰랐기에 이번 기회를 통해 정리해보려 한다.

백트래킹 (Backtracking)
가능한 모든 해를 탐색하며 조건에 맞지 않는 불필요한 경로는 가지치기(pruning)한다. 모든 가능성을 탐색해야 하는 경우에 사용하며, 그렇기에 항상 효율적인 답을 보징하지 않는다.

 

동적 계획법 (Dynamic Programming)
주로 최적의 해를 구하기 위해 사용한다. 문제를 작은 부분 문제들로 나누고, 큰 문제를 해결하기 위해 이미 해결한 작은 문제의 결과를 메모이제이션하여 중복 계산을 줄인다.

 

내가 작성한 시간초과 코드(백트래킹):

함수명을 dp라고 썼지만 dp의 정의에 맞게 메모이제이션을 하는 코드는 아니기 때문에 정말 코드를 씹고뜯고맛보고즐기는 사람이본다면 내가 알고리즘 유형에 대해 잘 모른다고 생각할 수도 있겠다.(맞음)
아무튼 나는 백트래킹 방식으로 풀었고 시간초과가 나서 메모이제이션을 할 수밖에 없는 상황이다.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countTheNumOfKFreeSubsets = function (nums, k) {
    let ans = 0;

    function dp(currentSubset, idx) {
        if (idx >= nums.length) {
            ans++;
            return;
        }

        dp([...currentSubset], idx + 1);
        if (idx < 1) {
            dp([...currentSubset, nums[idx]], idx + 1);
        }
        else {
            for (let i = 0; i < currentSubset.length; i++) {
                if (Math.abs(currentSubset[i] - nums[idx]) === k) return;
            }
            dp([...currentSubset, nums[idx]], idx + 1);
        }
    }

    dp([], 0);

    return ans;
};

 

 

 

 

DP 풀이법

처음에 채대리에게 물어봤었는데 막상 돌려보니 모든 테스트케이스를 만족하지는 못했다.. 역시 더블체크는 인간이 해야 한다.

그래서 자바스크립트 코너에 올라온 풀이를 확인했다. dp풀이법의 주요 내용은 이렇다.

- Sorting: nums를 정렬하여 내용을 간소화
- Memoization: Map에 저장하여, dp[i] = dp[i-2]+dp[i-1]와 같이 사용

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countTheNumOfKFreeSubsets = function(nums, k) {
  const map = new Map()
  let maxChain = 0

  nums.sort((a, b) => a - b)

  // make groups where each element has difference of k
  for (let i = 0; i < nums.length; i++) {
    let num = nums[i]
    let prev = num - k
    let value = 1

    if (map.has(prev)) {
      value += map.get(prev)
      map.delete(prev)
    }
    map.set(num, value)
    maxChain = Math.max(maxChain, value)
  }

  // compute subset for each group by group length
  const dp = Array(maxChain + 1)
  dp[0] = 1 // []
  dp[1] = 2 // [], x

  for (let i = 2; i <= maxChain; i++) {
    dp[i] = dp[i - 2] + dp[i - 1]
  }

  let value = 1
  for (let size of map.values()) {
    value *= dp[size]
  }

  return value
};

 

 

 

 

 

갑자기 개인적인 알고리즘 회고

조금 늘었다..

알고리즘을 제대로 열심히 공부해본 적이 없어서 자신감이 없다는 말은 질리도록 해왔지만 내가 지금 있는 캐나다에서의 영어로 하는 코딩 인터뷰를 위해 별수없이 하고 있었다.

2024년 4월부터 (물론 중간에 안나간 때도 있었지만) 리트코드 밋업을 주기적으로 나갔고, 중간 두달 정도는 밴쿠버 KDD에서 진행하는 코딩인터뷰스터디에 참석하기도 했다.

그런데 웬일인가.. 2024년 11월인 지금, 느리긴 했지만 문제를 푸는 속도나 난이도가 올라갔다!

집에서 개인적으로 시간을 내어서 공부한 적은 손에 꼽는데 말이다.

정말 엄청난 알고바보에서 알고린이 정도로 레벨업한 입장에서 어떻게 이 사실을 인지했냐면,

- Blind75같이 기출유형만 반복해서 풀다보니 유형이 파악되었다..!

- 코딩인터뷰스터디할때는 사실 이해못하면 그냥 외웠었는데, 그 기억이 남아있다..

- 리트코드 밋업에서 내가 주어진 문제를 푸는 양이 많아졌다. medium도 가끔 푼다.

 

공부하는 방법?

최근에 친구와 리트코드를 풀며 풀이방법을 설명하는 식으로 공부를 잠깐 했었는데, 그 친구가 내게 해준 말이 인상적이었다. 지금까지 내가 들은 알고리즘 공부법과 너무 달랐기 때문에..

채대리 설명을 보고 이해했으면 굳이 다시 풀어서 submission accept하려 하지 마라, 시간낭비하지 마라..

물론 이 말이 정답이 아니고 진리의 사바사 이기때문에 새겨들을 필요가 없다고 생각.. 처음엔 했다. 내가 안풀어보는게 오히려 시간을 아끼는 일이라니?

내가 기존에 알고있던 공부방법(안보고 풀 수 있을때까지 풀기) 도 결국 풀이 제출을 하느냐 마냐의 차이이지 이해를 하라는 말과는 일맥상통하는 것 같다. 하지만 나는 아무래도 쓸 줄 알아야 이해가 되는 사람인 것 같기도 하다.. 하하