Skip to content

Latest commit

 

History

History
93 lines (69 loc) · 4.94 KB

43.md

File metadata and controls

93 lines (69 loc) · 4.94 KB

피로도

완전탐색 보다는 DFS 유형!

Try1

function solution(k, dungeons) {
  const dg = dungeons.sort((a, b) => {
    if (k > a[0] && k > b[0]) return a[1] - b[1];
    else return b[0] - a[0];
  });

  let count = 0;
  let total = k;
  for (let i = 0; i < dg.length; i++) {
    const [required, expended] = dg[i];
    if (required > total) continue;
    else {
      total -= expended;
      count++;
    }
  }

  return count;
}

완전탐색의 기본은 정렬이다. 감각적인(?) 정렬을 통해서 최대 혹은 최소에 맞는 조건을 추가하여 구할 수 있었다. 그래서 이 문제 역시 정렬부터 시작하였다. 최소 필요 피로도 기준 내림차순 + 최소 필요 피로도보다 작은 경우 소모 피로도 기준 오름차순으로 정렬하였다. 그렇게 문제가 끝나는줄 알았다. 제출 후 60점... 음...어떤 반례가 있는지 알지 못해 약간의 힌트를 참고해보았다. 두둥!!

INPUT 40, [[40, 20], [10, 10], [10, 10], [10, 10], [10, 10]]
OUTPUT 4

위 조건이라면 나의 구현으로는 3이 나온다. 하지만 최대치는 4가 나와야한다. 이런 경우, 최소 필요 피로도 순으로 정렬한 의미가 없어진다. 단순히 이렇게 정렬해서 푸는것이 아니라 다른 접근이 필요했다.

Try2

기본적으로 완전탐색 타입의 문제는 정렬을 토대로 for/if를 통해서 적절하게 모든 경우의 수를 탐색하는 방법을 말한다.(적어도 나는 이렇게 알고 있다.) 그런데 이 문제는 단순히 완전탐색이 아니였다. 여기에 좀 더 전략적인 기법이 들어갔다. 백트랙킹, DFS(BFS)가 그것이다.

  • 백트랙킹 말 그대로 뒤로 가는 방법이다. 탐색 중에 이게 아닌것 같다면, 다시 뒤로 돌아가서 다시 탐색하는 전략을 말한다.,

  • DFS(BFS)

    DFS(BFS)는 백트랙킹을 바탕으로서 하는 재귀 알고리즘이다.

    DFS (와 BFS)는 모든 노드를 탐색하는 것을 목표로 하는 완전탐색을 베이스로 한 그래프 탐색 기법이다. 그 중 DFS는 깊이를 우선해 탐색하는 것.
문제 풀이에 적용할 때는, 가능한 모든 경우의 수를 DFS방식으로 탐색하는 중 조건을 걸어서 올바른 해가 나오지 않을 듯한 경우에 backtracking을 이용해 직전의 수를 물리고 다른 수를 두는 식으로 두 탐색 기법을 혼용하여 사용한다.

거두절미하고, 이 문제는 DFS기법을 통해서 접근해야하는 문제였다!

function solution(k, dungeons) {
  const checked = [];
  const result = [];

  const dfs = (k, checked, count) => {
    for (let i = 0; i < dungeons.length; i++) {
      const [required, used] = dungeons[i];
      if (!checked[i] && k >= required) {
        checked[i] = 1;
        dfs(k - used, checked, count + 1);
        checked[i] = 0;
      }
      if (i === dungeons.length - 1) result.push(count);
    }
  };
  dfs(k, checked, 0);

  return Math.max(...result);
}

사실 이 구현을 할 때, 여러가지 코드를 참고하면서 구현을 해서 결과적으로 내가 이 코드를 구현했다고 보기는 어렵다. 단지, DFS에 대해서 알아가는 과정으로서의 문제라고 기록하고 싶다.

내가 가장 헷갈렸던 부분은 왜 dfs(k - used, checked, count + 1) 이런 식으로 인자로서 변경된 값을 넣어줘야하는가 였다.

k -= used;
count++;
dfs(k, checked, count);

요런식으로 전달하면 안되는거지?!에 대한 부분이였다. 이건 여러가지 의미를 이해하는데, 우선 이 코드는 재귀이고, 모든 경우의 수를 탐색하기 위한 것이라는 것에 있다. 처음 dfs함수를 호출한다는 것의 의미, 첫번째 for문을 순회한다는 것은 시작할 던전을 고르는 것을 의미한다. 즉 던전을 시작하는 것이기 때문에 모든 조건이 동일해야한다, k(주어진 피로도), checked(방문여부), count(현재까지 가능한 던전의 수). 그래서 재귀를 부를 때 인자로 넣어줌으로서 기존 함수에서의 값을 변경시키지 않는 것이다. 이와 같은 맥락에서 checked[i] = 0를 써주는 것이기도 하다.

결론

뭔가 문제를 풀었다기보다 오픈북으로 DFS에 대해서 공부를 한 느낌이다. 알고리즘 문제를 푼지 보름 조금 넘어간다. 약 50문제(리스트에 적지않는 문제 포함하여)정도 푼것 같다. 레벨도 조금씩 올라가면서 같은 유형이더라도 조금씩 더 생각이 필요하고, 추가적인 전략(알고리즘)이 필요하다는 생각이 든다. 그래서 하나의 문제를 단순히 푸는 것을 넘어서 내가 익숙하지 않은 자료구조, 알고리즘에 대해서도 정리하는 시간이 필요해보인다. 그렇게 하나씩 하나씩 익숙해지는 것이 코테 나아가 자료구조/알고리즘을 정복??!! 하는 길이 아닐까 싶다! 급하지말고 천천천~천히 하자!! 🚀