알고리즘 문제 풀어보기

피로도

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

k는 1 이상 5,000 이하인 자연수입니다.
dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
dungeons의 가로(열) 길이는 2 입니다.
dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
"최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

풀이 코드

function solution(k, dungeons) {
    const visited = Array(dungeons.length).fill(false); // 방문 배열 초기화
    var max = 0;
  
    // 완전탐색을 위한 DFS(남은피로도, 현재 카운트)
    function dfs(k, cnt) {
      // 던전의 수만큼 반복
      for (var i = 0; i < dungeons.length; i++) {
        // 방문하지 않았고, 현재 피로도가 최소 피로도보다 크거나 같은 경우 (방문 가능)
        if (!visited[i] && k >= dungeons[i][0]) {
          visited[i] = true; // 방문 여부 true
          dfs(k - dungeons[i][1], cnt + 1); // 피로도 감소, 카운트 1증가 dfs 재귀
          visited[i] = false; // dfs가 종료되어 돌아오면, 방문 여부 false로 (visited 초기화)
        }
      }
      if (max < cnt) max = cnt;
    }
  
    dfs(k, 0);
    return max;
  }

풀이 과정

DFS알고리즘을 이용해 풀었다.

DFS(Depth-First-Search)

• 깊이 우선 탐색, 그래프에서 깊은 부분을 우선으로 탐색하는 알고리즘.
• 트리구조를 생각하면 이해하기 쉽다.
  => 트리를 탐색할 때 시작 노드에서 한 방향으로 계속 탐색하다가 더 이상 갈 수 없을 때 다시 가장 가까운 노드로 되돌아와 다시 탐색을 진행하는 방법과 유사하다.

구현방법

재귀를 이용

• 동작 방식
  1. 방문 여부를 기록하기 위해 배열 visited를 사용하며, 배열 visited의 값을 false로 초기화한다.
  2. 노드를 방문할 때마다 해당 노드의 visited 배열 값을 true로 변경한다.
  3. 해당 노드(v)와 연결된 노드 중에 방문하지 않은 노드(node)이 있다면 방문하지 않은 노드(node)를 시작점으로 하여 DFS를 다시 시작한다.

• 코드 구현

function dfs(graph, v, visited) {
  // 현재 노드를 방문 처리
  visited[v] = true;
  console.log(v);
  // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for (let node of graph[v]) {
    if (!visited[node]) {
      dfs(graph, node, visited);
    }
  }
}
const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);

dfs(graph, 0, visited);
// 0 1 5 2 4 3

스택(반복문)을 이용

• 동작 방식
  1. 스택에 시작 노드를 push 한다.
  2. 스택에서 노드를 pop하고 해당 노드(v)가 방문하지 않은 노드라면 방문처리 한다.
  3. 노드(v)와 연결된 노드 중에서 방문하지 않은 노드(node)이 있다면 stack에 push 한다.
  4. 스택의 길이가 0이 될 때까지 2, 3번 과정을 반복한다.

• 코드 구현

function dfs(graph, start, visited) {
  const stack = [];
  stack.push(start);

  while (stack.length) {
    let v = stack.pop();
    if (!visited[v]) {
      console.log(v);
      visited[v] = true;

      for (let node of graph[v]) {
        if (!visited[node]) {
          stack.push(node);
        }
      }
    }
  }
}
const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);

dfs(graph, 0, visited);
// 0 4 3 2 5 1

팀프로젝트(타워 디펜스 리마스터)

피드백

우리 조 피드백 담당으로 강창민 튜터님과 문승현 튜터님이 맡게 되셨는데
강창민 튜터님 께서는
상태동기화에 대한 설명 좋았고 트러블슈팅에서 소통이 정말 중요하다고 말씀하셧는데 딱 최종프로젝트 전에 이 부분을 잘 알게 되신거같아 다행이라고 말씀하셨다.
그리고 시연영상에서 소리가 안난 부분이 조금 아쉽다고 말씀하셧다.

문승현 튜터님 께서는
ppt자료 보면 같은 코드를 여러번 부르는 부분이 있는데 그렇다면 특정값 하나만 다르고 다른 부분은 같다는 것이므로 이 같은 코드들을 하나로 합치면 좋을 것 같다고 하시고 주석으로 이긴놈, 진놈이라는 표현을 사용했는데 이렇게 굳이 이긴놈 진놈 안하고 변수명으로 이쁘게 해놔도 좋을 것 같다고 말씀하셨다.

ppt 만든다고 캡쳐할때 재미를 조금 얹고싶다는 생각에 해당 부분을 안지우고 살려둿었는데 지울걸 그랬나..? 조금 후회됫다.

전반적으로 발표 자체는 딱히 안좋은 말 없이 잘 마무리 된 것 같아 다행이었다.

advanced 특강

Redis, Bull Queue, 로드 밸런싱 등 여러 기술 스택에 대한 특강이 있었다.