멀리 뛰기 | 알고달레

프로그래머스의 멀리 뛰기 문제를 함께 풀어보도록 하겠습니다.

문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는

(1칸, 1칸, 1칸, 1칸)

(1칸, 2칸, 1칸)

(1칸, 1칸, 2칸)

(2칸, 1칸, 1칸)

(2칸, 2칸)

의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

예제

입력: n = 4
출력: 5

입력: n = 3
출력: 3

풀이 1

우선 멀리 뛰기에 사용될 칸의 수가 1일 때는 효진이가 끝에 도달하는 방법은 1가지라는 것을 알 수 있습니다.

(1칸)

칸의 수가 2일 때는 어떨까요? 1칸씩 2번을 뛸 수 있고 2칸을 한 번에 뛸 수도 있을 것입니다.

(1칸) + (1칸)
(2칸)

칸의 수가 3일 때는 어떨까요?

바로 전 칸에서 올 수 있는 방법이 2가지 있고요.

(1칸, 1칸) + (1칸)
(2칸) + (1칸)

바로 전전 칸에서 올 수 있는 방법이 1가지가 있습니다.

(1칸) + (2칸)

그러므로 총 3가지 방법이 있겠네요.

(1칸, 1칸, 1칸)
(2칸, 1칸)
(1칸, 2칸)

4칸을 멀리 띄기할 때는 어떨까요?

바로 전 칸에서 올 수 있는 방법이 2가지 있고요.

(1칸, 1칸, 1칸) + (1칸)
(2칸, 1칸) + (1칸)
(1칸, 2칸) + (1칸)

바로 전전 칸에서 올 수 있는 방법이 3가지가 있네요.

(1칸, 1칸) + (2칸)
(2칸) + (2칸)

따라서 총 5가지 방법을 얻게 됩니다.

(1칸, 1칸, 1칸, 1칸)
(2칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 2칸)

이렇게 건너 띄기에 사용될 칸을 수를 1씩 증기시키면서 생각을 해보면, 현재 칸에서 결과는 이전 칸과 이전 이전 칸의 결과를 통해서 도출할 수 있다는 것을 알 수 있습니다.

이런 상황에서 사용하면 안성 맞춤인 풀이 기법이 있는데요. 바로 동적 계획법(Dynamic Programming)입니다.

건너 띄기에 사용될 칸의 수가 n일 때, 끝에 도달하는 방법은 칸의 수가 n - 1일 때의 방법과 칸의 수가 n - 2일 때 방법의 수를 더하면 구할 수 있습니다. 이 것을 일반화해보면 다음과 같은 점화식을 얻을 수 있습니다.

dp[n] = dp[n - 1] + dp[n - 2]

위 수식은 n이 2보다 적을 때는 n - 2 부분이 음수가 되므로 적용할 수 없습니다. 그런데 아까 위에서 칸의 개수가 1일 때는 방법이 하나 밖에 없었고, 칸의 개수가 0일 때는 안 띄면 되므로 역시 방법이 하나라고 볼 수 있겠습니다.

dp[1] = 1
dp[0] = 1

그럼 이 알고리즘을 배열을 이용해서 파이썬으로 구현해보겠습니다.

def solution(n):
    dp = [1] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n] % 1234567

dp 배열에 0부터 n까지 칸에 대한 결과를 저장해놓고, 더 작은 칸의 결과를 활용하여 더 큰 칸의 값의 결과를 구하고 있습니다.

같은 코드를 자바스크립트로도 구현해보았습니다.

function solution(n) {
  let dp = new Array(n + 1).fill(1);
  for (let i = 2; i <= n; i++) {
    dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
  }
  return dp[n] % 1234567;
}

n을 칸의 개수라고 했을 때, 이 풀이의 시간 복잡도는 반복 횟수가 n에 비례하기 때문에 O(n)입니다. dp 배열의 크기도 n에 비례해서 커지기 때문에 공간 복잡도도 O(n)이 되겠습니다.

풀이 2

위 풀이에서는 0부터 n까지 칸에 대한 모든 결과를 저장하고 있는데요. 사실 바로 전 칸과 전전 칸에 대한 결과만 알면 되는데, 굳이 이렇게 모든 결과를 저장할 필요가 없겠죠?

그럼 배열 대신에 2개의 변수만 사용해서 이전 풀이를 다시 구현해보겠습니다.

def solution(n):
    p2, p1 = 1, 1
    for _ in range(2, n + 1):
        p2, p1 = p1, p2 + p1
    return p1 % 1234567

p2에는 전전 결과, p1에는 전 결과를 저장하고 있습니다. 그리고 이전 풀이와 동일한 횟수의 반복을 하면서, p2와 p1의 값을 갱신해주고 있습니다.

같은 코드를 자바스크립도 구현하면 다음과 같습니다.

function solution(n) {
  let p2 = 1,
    p1 = 1;
  for (let i = 2; i <= n; i++) {
    let tmp = p1;
    p1 = (p2 + p1) % 1234567;
    p2 = tmp;
  }
  return p1 % 1234567;
}

이렇게 메모리 사용량을 최적화해주면 공간 복잡도가 O(n)에서 O(1)로 향상이 됩니다. 이 풀이는 고정된 개수의 변수 외에는 추가 메모리가 필요하지 않기 때문입니다.