[카테고리:] 자바스크립트 코딩테스트 강좌

문제 정의

다음과 같은 조건을 충족하는 함수를 작성하세요:

주어진 정수 배열이 주어졌을 때, 이 배열에서 두 수를 더하여 특정 목표값을 만드는 두 수의 인덱스를 반환하는 함수를 작성하시오. 배열에는 항상 해답이 존재한다고 가정하며, 같은 요소를 두 번 사용하는 것은 허용되지 않습니다.

function twoSum(nums, target) {
    // 여기에 코드를 작성하세요.
}

입력 예시

입력:

twoSum([2, 7, 11, 15], 9)

출력 예시

출력:

0, 1

문제 풀이 과정

이 문제를 해결하기 위해, 우리는 두 가지 접근 방식을 사용할 수 있습니다. 첫 번째는 이중 루프를 사용하는 방법이고, 두 번째는 해시맵을 활용하는 방법입니다. 효율성을 고려하여 해시맵을 사용하는 방법을 선택하겠습니다.

1. 문제 분석

우리가 해야 할 일은 배열의 각 요소를 살펴보면서, 목표값에서 해당 요소를 뺀 값을 찾는 것입니다. 이 값을 발견하면, 그 요소의 인덱스를 반환하면 됩니다.

2. 해시맵 사용

첫 번째 단계로, 빈 해시맵(객체)을 생성합니다. 배열을 순회하면서 각 요소를 해시맵에 추가하고, 그 요소의 인덱스도 함께 저장합니다. 그 후, 매 순회할 때마다 목표값에서 현재 요소를 뺀 값이 해시맵에 존재하는지 확인합니다. 존재하면 그 인덱스를 반환합니다.

function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
}

3. 디버깅 사례

코드를 작성한 후, 오류가 발생할 수 있는 부분을 확인하는 것이 중요합니다. 디버깅을 통해 ‘목표값에서 현재 요소를 뺀 값을 찾는 로직’에서 의도한 대로 작동하는지 체크할 수 있습니다. 콘솔 로그를 활용하여 각 단계에서 변수의 상태를 확인할 수도 있습니다.

function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        console.log(`Current Number: ${nums[i]}, Complement: ${complement}`);
        if (map.has(complement)) {
            console.log(`Found complement: ${complement} at index ${map.get(complement)}`);
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
}

결론

위와 같은 방법으로 문제를 해결하면, 자바스크립트의 특성을 활용할 수 있고, 디버깅 또한 수월하게 진행할 수 있습니다. 코드를 작성한 후에는 항상 디버깅 툴(브라우저의 개발자 도구 등)을 활용해 다양한 케이스를 테스트해보고, 각 변수의 상태를 확인하며 문제를 보다 깊이 이해하는데 초점을 맞추는 것이 좋습니다.

이번 강좌에서는 자바스크립트에서의 알고리즘 문제 풀이와 함께 디버깅의 중요성을 알아보았습니다. 이러한 접근법을 통해 여러분의 코딩 테스트 준비에 도움이 되기를 바랍니다.

문제 설명

다음은 게임 캐릭터의 이동 경로를 추적하는 알고리즘 문제입니다.

문제: 주어진 게임 맵에서 캐릭터가 (0, 0)에서 시작하여 (n, m) 위치로 이동합니다. 캐릭터는 상, 하, 좌, 우로 한 번에 한 칸씩 이동할 수 있으며, 장애물은 이동할 수 없는 칸으로 설정되어 있습니다. 장애물을 포함한 맵이 주어질 때, 캐릭터가 목표 위치에 도달하기 위한 모든 가능한 경로의 수를 구하시오.

입력:

• 첫 번째 줄: 정수 n, m (1 ≤ n, m ≤ 10)
• 이후 n개의 줄: m개의 정수 (0은 빈 칸, 1은 장애물)

출력: 목표 위치까지의 경로 수

문제 해결 접근법

문제를 해결하기 위해 깊이 우선 탐색(DFS) 방법을 사용할 것입니다. DFS는 모든 가능한 경로를 탐색하여 적합한 경로 수를 카운트하는 데 효과적입니다. 다음과 같은 단계를 진행하겠습니다:

1. 맵을 2D 배열로 초기화합니다.
2. (0, 0)에서 시작하여 (n, m)으로 가는 경로를 탐색하기 위해 재귀함수를 구현합니다.
3. 장애물 또는 경계를 만났을 때 탐색을 멈추고, 경로의 수를 카운트합니다.
4. 모든 경로를 탐색한 후 경로 수를 반환합니다.

코드 구현

이제 위의 접근법을 바탕으로 자바스크립트를 사용한 코드 구현을 진행하겠습니다.

function countPaths(map, x, y, n, m) {
    // 목표 위치에 도달한 경우
    if (x === n - 1 && y === m - 1) {
        return 1;
    }
    
    // 경계 또는 장애물을 만난 경우
    if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] === 1) {
        return 0;
    }
    
    // 현재 위치를 방문한 것으로 표시
    const temp = map[x][y];
    map[x][y] = 1; // 장애물로 설정하여 방문 표시
    
    // 상, 하, 좌, 우로 이동
    const paths = countPaths(map, x + 1, y, n, m) +
                  countPaths(map, x - 1, y, n, m) +
                  countPaths(map, x, y + 1, n, m) +
                  countPaths(map, x, y - 1, n, m);
    
    // 방문한 위치를 원상복구
    map[x][y] = temp;
    
    return paths;
}

function findAllPaths(map) {
    const n = map.length;
    const m = map[0].length;
    return countPaths(map, 0, 0, n, m);
}

// 테스트 케이스
const gameMap = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
];

console.log(findAllPaths(gameMap)); // 경로 수 출력

            

위 코드는 게임 맵에서 (0, 0)에서 (n-1, m-1)로 이동할 수 있는 경로의 수를 계산합니다. 장애물과 경계를 처리하는 방법을 잘 보여줍니다.

최적화

위의 구현은 간단하고 이해하기 쉬운 코드입니다. 그러나, 이 방법은 중복 탐색이 발생할 수 있어 비효율적일 수 있습니다. 이를 해결하기 위해 메모이제이션 기법을 사용할 수 있습니다. 메모이제이션을 통해 이미 계산한 경로 수를 저장하고, 동일한 위치에서 계산할 때는 저장된 결과를 재사용하여 성능을 개선할 수 있습니다.

const memo = {};

function countPathsOptimized(map, x, y, n, m) {
    const key = x + ',' + y;
    // 메모이제이션을 체크
    if (key in memo) {
        return memo[key];
    }
    
    // 목표 위치에 도달한 경우
    if (x === n - 1 && y === m - 1) {
        return 1;
    }
    
    // 경계 또는 장애물을 만난 경우
    if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] === 1) {
        return 0;
    }
    
    // 현재 위치를 방문한 것으로 표시
    const temp = map[x][y];
    map[x][y] = 1;
    
    // 경로 계산
    const paths = countPathsOptimized(map, x + 1, y, n, m) +
                  countPathsOptimized(map, x - 1, y, n, m) +
                  countPathsOptimized(map, x, y + 1, n, m) +
                  countPathsOptimized(map, x, y - 1, n, m);
    
    // 방문한 위치를 원상복구
    map[x][y] = temp;
    
    // 메모이제이션에 저장
    memo[key] = paths;
    
    return paths;
}

function findAllPathsOptimized(map) {
    memo = {};
    const n = map.length;
    const m = map[0].length;
    return countPathsOptimized(map, 0, 0, n, m);
}
            
            

위의 최적화된 코드는 이전 코드와 거의 유사하지만, 이번에는 메모이제이션을 통해 반복 계산을 방지합니다. 이렇게 하면 성능이 크게 향상됩니다.

결론

이번 강좌를 통해 자바스크립트를 활용하여 게임 개발과 관련된 문제를 해결하는 방법을 알아봤습니다. DFS와 메모이제이션 기법을 통해 문제를 해결하는 데 필요한 기본 접근법을 학습하였습니다. 알고리즘 문제풀이 연습을 통해 더 많은 문제를 접하고 해결하는 힘을 길러보세요.

게임 개발은 창의적이고 논리적인 사고를 요구합니다. 다양한 알고리즘 문제를 풀면서 코딩 능력을 향상시키고, 실제 프로젝트에 활용하시길 바랍니다. 앞으로도 더 많은 알고리즘과 게임 개발 관련 강좌를 준비하겠습니다. 감사합니다!