LeetCode의 55번째 문제인 Jump Game를 함께 풀어보도록 하겠습니다.
문제
정수 배열 nums가 주어집니다.
처음에는 배열의 첫 번째 인덱스에 위치하고 있으며, 배열의 각 요소는 해당 위치에서의 최대로 점프(jump)할 수 있는 길이를 나타냅니다.
마지막 인덱스에 도달할 수 있다면 참을 반환하고, 그렇지 않으면 거짓을 반환하시오.
예제
입력: nums = [2,3,1,1,4]
출력: true
입력: nums = [3,2,1,0,4]
출력: false
풀이 1: DFS
우선 알고리즘의 성능은 배제하고 무식하지만 단순한 방법으로 이 문제를 풀어볼까요? 배열의 첫 번째 인덱스부터 점프를 해서 마지막 인덱스까지 도달할 수 있는 모든 경우의 수를 따져보는 거예요.
첫 번째 예제를 기준으로 생각을 해보면 다음과 같은 총 4가지 경우의 수를 구할 수 있습니다.
[2, 3, 1, 1, 4]
^
[2, 3, 1, 1, 4]
^ ^
[2, 3, 1, 1, 4]
^ ^ ^
[2, 3, 1, 1, 4]
^ ^ ^ ^
[2, 3, 1, 1, 4] ✅
^ ^ ^ ^ ^
[2, 3, 1, 1, 4]
^ ^ ^
[2, 3, 1, 1, 4] ✅
^ ^ ^ ^
[2, 3, 1, 1, 4] ✅
^ ^ ^
[2, 3, 1, 1, 4]
^ ^
[2, 3, 1, 1, 4]
^ ^ ^
[2, 3, 1, 1, 4] ✅
^ ^ ^ ^
반면에 두 번째 예제에서는 마지막 인덱스에 도달할 수 있는 경우가 하나도 없습니다.
[3, 2, 1, 0, 4]
^
[3, 2, 1, 0, 4]
^ ^
[3, 2, 1, 0, 4]
^ ^ ^
[3, 2, 1, 0, 4] ❌
^ ^ ^ ^
[3, 2, 1, 0, 4] ❌
^ ^ ^
[3, 2, 1, 0, 4]
^ ^
[3, 2, 1, 0, 4] ❌
^ ^ ^
[3, 2, 1, 0, 4] ❌
^ ^
이와 같은 사고 과정을 통해서 우리는 재귀 알고리즘을 통해서 이 문제를 해결할 수 있다는 것을 깨닫게 됩니다. 하지만 문제에서 요구하는 것은 경우의 개수가 아니기 때문에 마지막 인덱스에 도달할 수 있는 경우가 하나라도 발견되면 바로 참을 반환할 수 있을 것입니다. 모든 경우의 수를 따져봤는데도 마지막 인덱스에 도달할 수 있는 경우가 나오지 않는다면 거짓을 반환하면 됩니다.
그럼 이 알고리즘을 코드로 구현해볼까요? 재귀 함수는 현재 인덱스에 있는 값만큼의 재귀 호출을 하게 됩니다. 그러다가 마지막 인덱스에 도달하면 재귀 함수를 탈출할 수 있습니다.
class Solution:
def canJump(self, nums: List[int]) -> bool:
def dfs(start):
if start == len(nums) - 1:
return True
for jump in range(1, nums[start] + 1):
if dfs(start + jump):
return True
return False
return dfs(0)class Solution {
public boolean canJump(int[] nums) {
return dfs(nums, 0);
}
private boolean dfs(int[] nums, int start) {
if (start == nums.length - 1) return true;
for (int jump = 1; jump <= nums[start]; jump++) {
if (dfs(nums, start + jump)) return true;
}
return false;
}
}function canJump(nums: number[]): boolean {
function dfs(start: number): boolean {
if (start === nums.length - 1) return true;
for (let jump = 1; jump <= nums[start]; jump++) {
if (dfs(start + jump)) return true;
}
return false;
}
return dfs(0);
}func canJump(nums []int) bool {
var dfs func(start int) bool
dfs = func(start int) bool {
if start == len(nums)-1 {
return true
}
for jump := 1; jump <= nums[start]; jump++ {
if dfs(start + jump) {
return true
}
}
return false
}
return dfs(0)
}impl Solution {
pub fn can_jump(nums: Vec<i32>) -> bool {
Self::dfs(0, &nums)
}
fn dfs(start: usize, nums: &Vec<i32>) -> bool {
if start == nums.len() - 1 {
return true;
}
for jump in 1..=nums[start] as usize {
if Self::dfs(start + jump, nums) {
return true;
}
}
false
}
}입력 배열의 길이를 n이라고 했을 때, 재귀 함수 내에서 재귀 호출이 최대 n번 일어날 수 있고, 호출 스택의 깊이는 n이 됩니다.
따라서 이 풀이의 시간 복잡도는 O(n^n)이고, 공간 복잡도는 O(n)이 됩니다.
성능이 너무 안 좋은 알고리즘이기 때문에 LeetCode에 제출하면 Time Limit Exceeded 오류가 날 것입니다.
풀이 2: Memoization
위 재귀 트리를 유심히 관찰해보시면 중복 연산이 상당히 많이 발생하고 있다는 것을 알 수 있는데요.
예를 들어, 세 번째 인덱스로부터 마지막 인덱스에 도달하는 부분은 총 2번 반복되고 있고요.
[2, 3, 1, 1, 4]
^ ^ ^
[2, 3, 1, 1, 4]
^ ^ ^ ^
[2, 3, 1, 1, 4] ✅
^ ^ ^ ^ ^
[2, 3, 1, 1, 4]
^ ^
[2, 3, 1, 1, 4]
^ ^ ^
[2, 3, 1, 1, 4] ✅
^ ^ ^ ^
네 번째 인덱스로부터 마지막 인덱스로 점프하는 부분도 총 3번이나 반복되고 있습니다.
[2, 3, 1, 1, 4]
^ ^ ^ ^
[2, 3, 1, 1, 4] ✅
^ ^ ^ ^ ^
[2, 3, 1, 1, 4]
^ ^ ^
[2, 3, 1, 1, 4] ✅
^ ^ ^ ^
[2, 3, 1, 1, 4]
^ ^ ^
[2, 3, 1, 1, 4] ✅
^ ^ ^ ^
재귀 알고리즘에서 이렇게 불필요하게 중복되는 연산은 메모이제이션(memoization) 기법을 사용해서 제거해줄 수 있는데요. 일차원 배열에 각 인덱스로부터 마지막 인덱스까지 도달할 수 있는지 여부를 저장해두면 됩니다.
class Solution:
def canJump(self, nums: List[int]) -> bool:
memo = {}
def dfs(start):
if start >= len(nums) - 1:
return True
if start in memo:
return memo[start]
memo[start] = False
for jump in range(1, nums[start] + 1):
if dfs(start + jump):
memo[start] = True
break
return memo[start]
return dfs(0)class Solution {
public boolean canJump(int[] nums) {
return dfs(nums, 0, new HashMap<>());
}
private boolean dfs(int[] nums, int start, Map<Integer, Boolean> memo) {
if (start >= nums.length - 1) return true;
if (memo.containsKey(start)) return memo.get(start);
memo.put(start, false);
for (int jump = 1; jump <= nums[start]; jump++) {
if (dfs(nums, start + jump, memo)) {
memo.put(start, true);
break;
}
}
return memo.get(start);
}
}function canJump(nums: number[]): boolean {
const memo = new Map<number, boolean>();
function dfs(start: number): boolean {
if (start >= nums.length - 1) return true;
if (memo.has(start)) return memo.get(start)!;
memo.set(start, false);
for (let jump = 1; jump <= nums[start]; jump++) {
if (dfs(start + jump)) {
memo.set(start, true);
break;
}
}
return memo.get(start)!;
}
return dfs(0);
}func canJump(nums []int) bool {
memo := map[int]bool{}
var dfs func(start int) bool
dfs = func(start int) bool {
if start >= len(nums)-1 {
return true
}
if _, ok := memo[start]; ok {
return memo[start]
}
memo[start] = false
for jump := 1; jump <= nums[start]; jump++ {
if dfs(start + jump) {
memo[start] = true
break
}
}
return memo[start]
}
return dfs(0)
}use std::collections::HashMap;
impl Solution {
pub fn can_jump(nums: Vec<i32>) -> bool {
let mut memo = HashMap::new();
Self::dfs(0, &nums, &mut memo)
}
fn dfs(start: usize, nums: &Vec<i32>, memo: &mut HashMap<usize, bool>) -> bool {
if start >= nums.len() - 1 {
return true;
}
if memo.contains_key(&start) {
return memo[&start];
}
memo.insert(start, false);
for jump in 1..=nums[start] as usize {
if Self::dfs(start + jump, nums, memo) {
memo.insert(start, true);
break;
}
}
memo[&start]
}
}참고로 파이썬에서는 @cache 데코레이터를 쓰면 동일한 효과를 얻을 수 있습니다.
from functools import cache
class Solution:
def canJump(self, nums: List[int]) -> bool:
@cache
def dfs(start):
if start == len(nums) - 1:
return True
for step in range(1, nums[start] + 1):
if dfs(start + step):
return True
return False
return dfs(0)이 풀이의 시간 복잡도는 중복 연산이 모두 제거되어 O(n^2)로 대폭 향상됩니다.
풀이 3: DP
여태까지는 각 인덱스로부터 마지막 인덱스까지 도달할 수 있는지 여부를 구했는데요. 즉, 더 작은 인덱스에 대한 결과를 구하기 위해서 더 큰 인덱스에 대한 결과가 필요했었고 그래서 재귀 알고리즘을 사용해야 했습니다.
이번에는 반대로 어떤 인덱스까지 도달할 수 있는지 여부를 구해보면 어떨까요? 그러면 동적 계획법(Dynamic Programming)을 통해서 이차원 배열을 사용하여 반복 알고리즘으로 해결을 할 수 있을 것입니다.
첫 번째 예제로 주어진 입력 배열을 가지고 같이 생각을 해보겠습니다.
첫 번째 인덱스에는 무조건 도달할 수 있습니다.
T
[2, 3, 1, 1, 4]
_
첫 번째 인덱스의 값이 2이기 때문에 두 번째 인덱스와 세 번째 인덱스에 도달할 수 있습니다.
T T T
[2, 3, 1, 1, 4]
^
두 번째 인덱스의 값이 4이기 때문에 네 번째 인덱스와 마지막 인덱스에 도달할 수 있습니다.
T T T T T
[2, 3, 1, 1, 4]
^
나머지 인덱스는 굳이 따져보지 않더라도 이미 마지막 인덱스에 도달이 가능하다는 것을 알 수 있습니다.
그럼 이 반복 알고리즘을 코드로 구현해보겠습니다.
class Solution:
def canJump(self, nums: List[int]) -> bool:
dp = [False] * len(nums)
dp[0] = True
for start in range(len(nums)):
if not dp[start]:
continue
for step in range(1, nums[start] + 1):
if start + step < len(nums):
dp[start + step] = True
return dp[-1]class Solution {
public boolean canJump(int[] nums) {
boolean[] dp = new boolean[nums.length];
dp[0] = true;
for (int start = 0; start < nums.length; start++) {
if (!dp[start]) continue;
for (int step = 1; step <= nums[start]; step++) {
if (start + step < nums.length) dp[start + step] = true;
}
}
return dp[dp.length - 1];
}
}function canJump(nums: number[]): boolean {
const dp: boolean[] = new Array(nums.length).fill(false);
dp[0] = true;
for (let start = 0; start < nums.length; start++) {
if (!dp[start]) continue;
for (let step = 1; step <= nums[start]; step++) {
if (start + step < nums.length) dp[start + step] = true;
}
}
return dp[dp.length - 1];
}func canJump(nums []int) bool {
dp := make([]bool, len(nums))
dp[0] = true
for start := 0; start < len(nums); start++ {
if !dp[start] {
continue
}
for step := 1; step <= nums[start]; step++ {
if start+step < len(nums) {
dp[start+step] = true
}
}
}
return dp[len(dp)-1]
}impl Solution {
pub fn can_jump(nums: Vec<i32>) -> bool {
let mut dp = vec![false; nums.len()];
dp[0] = true;
for start in 0..nums.len() {
if !dp[start] {
continue;
}
for step in 1..=nums[start] as usize {
if start + step < nums.len() {
dp[start + step] = true;
}
}
}
dp[dp.len() - 1]
}
}이 풀이는 이중 루프를 돌기 때문에 메모이제이션을 적용한 재귀 알고리즘 풀이와 동일한 복잡도를 갖습니다.
풀이 4: Greedy
마지막 풀이 방법은 상당한 직관(intuition)을 요하는데요. 사실 잘 생각을 해보시면 위와 같이 열심히 이중 루프를 돌지 않더라도, 각 인덱스로부터 가장 멀리 갈 수 있는 인덱스만 추적해서 이 문제를 해결할 수 있습니다.
예를 들어, 첫 번째 인덱스에서는 최대 세 번째 인덱스까지 점프할 수 있습니다.
_______
[2, 3, 1, 1, 4]
^
두 번째 인덱스에서는 최대 마지막 인덱스까지 점프할 수 있습니다.
_____________
[2, 3, 1, 1, 4]
^
이 알고리즘을 코드로 구현해볼까요?
class Solution:
def canJump(self, nums: List[int]) -> bool:
reach = 0
for idx in range(len(nums)):
if idx <= reach:
reach = max(reach, idx + nums[idx])
return len(nums) - 1 <= reachclass Solution {
public boolean canJump(int[] nums) {
int reach = 0;
for (int idx = 0; idx < nums.length; idx++) {
if (idx <= reach) reach = Math.max(reach, idx + nums[idx]);
}
return nums.length - 1 <= reach;
}
}function canJump(nums: number[]): boolean {
let reach = 0;
for (let idx = 0; idx < nums.length; idx++) {
if (idx <= reach) reach = Math.max(reach, idx + nums[idx]);
}
return nums.length - 1 <= reach;
}func canJump(nums []int) bool {
reach := 0
for idx := 0; idx < len(nums); idx++ {
if idx <= reach {
reach = max(reach, idx+nums[idx])
}
}
return len(nums)-1 <= reach
}impl Solution {
pub fn can_jump(nums: Vec<i32>) -> bool {
let mut reach = 0;
for idx in 0..nums.len() {
if idx <= reach {
reach = reach.max(idx + nums[idx] as usize);
}
}
nums.len() - 1 <= reach
}
}이 풀이는 단일 루프만 사용하므로 시간 복잡도가 O(n)으로 향상이 됩니다.
뿐만 아니라 고정된 개수의 변수 외에는 추가 메모리를 사용하지 않으므로 공간 복잡도도 O(1)로 향상됩니다.