[프로그래머스] 코딩 테스트 공부

문제 상황

https://school.programmers.co.kr/learn/courses/30/lessons/118668

• 알고력 공부: 1시간에 알고력 +1
• 코딩력 공부: 1시간에 코딩력 +1
• 문제 풀기: 문제마다 다른 시간과 보상

목표는 모든 문제를 풀 수 있는 능력을 얻는 최단시간을 구하는 것이었습니다.

첫 번째 시도: BFS로 접근

처음에는 BFS(너비 우선 탐색)로 접근해봤다. 상태를 (알고력, 코딩력)으로 표현하고, 각 상태에서 가능한 행동들을 큐에 넣어가며 탐색했다.

// BFS 방식 (첫 번째 시도)
const queue = [];
const visited = Array.from({ length: 151 }, () => Array(151).fill(false));

하지만 이 방식에는 문제가 있었다. BFS는 가중치가 없는 그래프에서 최단 경로를 보장하지만, 이 문제는 각 행동마다 다른 시간이 걸리기 때문에 최적해를 보장하지 않더라고 했다.

두 번째 시도: 다익스트라 알고리즘

그래서 다익스트라 알고리즘으로 바꿔봤다. 우선순위 큐를 사용해서 가장 시간이 적게 걸리는 경로부터 탐색하는 방식이었다.

// 다익스트라 방식 (두 번째 시도)
const pq = [];
pq.push([0, alp, cop]); // [시간, 알고력, 코딩력]

이 방식은 올바른 결과를 내놓았지만, JavaScript에서 우선순위 큐를 직접 구현하기 어려워서 매번 배열을 정렬해야 했다. 이게 성능상 비효율적이었다.

최종 해결책: DP (동적 프로그래밍)

결국 DP 방식으로 해결했다. 2차원 DP 테이블을 만들어서 각 능력치 조합에 도달하는 최단 시간을 저장하는 방식이었다.

function solution(alp, cop, problems) {
  // 목표 능력치 계산
  let targetAlp = alp;
  let targetCop = cop;

  for (let i = 0; i < problems.length; i++) {
    if (problems[i][0] > targetAlp) targetAlp = problems[i][0];
    if (problems[i][1] > targetCop) targetCop = problems[i][1];
  }

  // DP 테이블 초기화
  const time = [];
  for (let i = 0; i <= 150; i++) {
    time[i] = [];
    for (let j = 0; j <= 150; j++) {
      time[i][j] = Infinity;
    }
  }
  time[alp][cop] = 0;

  // DP로 최단 시간 계산
  for (let currentAlp = alp; currentAlp <= targetAlp; currentAlp++) {
    for (let currentCop = cop; currentCop <= targetCop; currentCop++) {
      if (time[currentAlp][currentCop] === Infinity) continue;

      // 알고력 공부
      if (currentAlp + 1 <= targetAlp) {
        const newTime = time[currentAlp][currentCop] + 1;
        if (time[currentAlp + 1][currentCop] > newTime) {
          time[currentAlp + 1][currentCop] = newTime;
        }
      }

      // 코딩력 공부
      if (currentCop + 1 <= targetCop) {
        const newTime = time[currentAlp][currentCop] + 1;
        if (time[currentAlp][currentCop + 1] > newTime) {
          time[currentAlp][currentCop + 1] = newTime;
        }
      }

      // 문제 풀기
      for (let i = 0; i < problems.length; i++) {
        const [alpReq, copReq, alpRwd, copRwd, cost] = problems[i];

        if (currentAlp >= alpReq && currentCop >= copReq) {
          let newAlp = currentAlp + alpRwd;
          let newCop = currentCop + copRwd;

          // 목표 초과시 제한
          if (newAlp > targetAlp) newAlp = targetAlp;
          if (newCop > targetCop) newCop = targetCop;

          const newTime = time[currentAlp][currentCop] + cost;

          if (time[newAlp][newCop] > newTime) {
            time[newAlp][newCop] = newTime;
          }
        }
      }
    }
  }

  return time[targetAlp][targetCop];
}

핵심 아이디어

1. 목표 설정: 모든 문제를 풀 수 있는 최소 능력치 = 각 문제 요구사항의 최대값
2. 상태 정의: time[i][j] = 알고력 i, 코딩력 j에 도달하는 최단 시간
3. 상태 전이: 각 상태에서 공부하거나 문제를 풀어서 다음 상태로 이동
4. 최적화: 목표를 초과하는 능력치는 목표로 제한

성능 분석

• 시간복잡도: O((targetAlp - alp) × (targetCop - cop) × problems.length)
• 공간복잡도: O(151 × 151)

최악의 경우에도 약 2백만 번의 연산으로 해결 가능해서 효율성 테스트도 통과할 수 있었다.

테스트 결과

제공된 테스트 케이스들이 모두 통과했다:

• solution(10, 10, [[10,15,2,1,2],[20,20,3,3,4]]) → 15
• solution(0, 0, [[0,0,2,1,2],[4,5,3,1,2],[4,11,4,0,2],[10,4,0,4,2]]) → 13

느낀 점

처음에는 그래프 탐색 문제인 줄 알았는데, 실제로는 DP 문제였다. 가중치가 있는 그래프에서 최단 경로를 구하는 문제라서 다익스트라도 가능하지만, DP가 더 직관적이고 구현하기 쉬웠다.

특히 JavaScript에서 우선순위 큐를 직접 구현하기 어려운 점도 DP를 선택한 이유 중 하나였다. 언어의 특성을 고려한 알고리즘 선택이 중요하다는 걸 다시 한번 느꼈다.