문제를 푸는 기준

dp[i]가 무엇인지 한 문장으로 정의하고 마지막 선택을 기준으로 이전 상태와의 관계를 세운 뒤 초기값과 계산 순서를 정합니다.

핵심 개념

대표 문제

인접하지 않은 값의 최대 합

0 이상의 정수 배열 numbers에서 서로 인접한 두 원소를 함께 선택하지 않을 때 최대 합을 반환하세요.

함수 시그니처: solution(numbers)

제한사항

• numbers의 길이는 0 이상 200,000 이하입니다.
• 모든 값은 0 이상입니다.

입출력 예

풀이 설계

1. 현재 값을 선택하지 않으면 직전 최댓값을 유지합니다.
2. 선택하면 두 칸 전 최댓값에 현재 값을 더합니다.
3. 두 경우의 큰 값을 현재 상태로 둡니다.

JavaScript 풀이

function solution(numbers) {
  let twoBack = 0;
  let oneBack = 0;
  for (const value of numbers) {
    const current = Math.max(oneBack, twoBack + value);
    twoBack = oneBack;
    oneBack = current;
  }
  return oneBack;
}

복잡도

• 시간복잡도: O(n)
• 공간복잡도: O(1)
• 핵심 패턴: 현재 값을 선택하는 경우와 건너뛰는 경우 비교
• 경계 사례: 빈 배열은 합 0 반환

연습 문제

1. 계단 방법 수

1칸 또는 2칸씩 n칸에 도달하는 방법 수를 구하세요.

2. 최소 동전 수

금액을 만드는 최소 동전 수를 반환하세요.

3. 격자 경로 수

오른쪽과 아래 이동 경로 수를 구하세요.

자주 하는 실수

• 상태 의미 없이 점화식부터 쓰는 실수
• 초기값을 빠뜨리는 실수
• 현재 갱신 전에 이전 값을 덮어쓰는 실수
• 중복 부분 문제가 없는 데 DP를 쓰는 실수

핵심 정리

• 함수 시그니처와 반환 자료형을 먼저 확정합니다.
• 제한사항으로 가능한 시간복잡도를 판단합니다.
• 예시와 경계 사례를 손으로 추적한 뒤 구현합니다.
• 완성한 solution 함수가 입력을 불필요하게 바꾸지 않는지도 확인합니다.

확인 문제

참고 자료

• MIT OpenCourseWare 6.006 Introduction to Algorithms 
• 프로그래머스 코딩테스트 고득점 Kit 
• MDN Array