자바스크립트로 코딩 테스트 준비하기
코딩 테스트 준비하기
이번 글은 나중에 코딩 테스트를 비롯한 문제 해결이 필요할 때 참고하려고 간단하게 작성했습니다. 개인적으로 정리한 글이지만, 프론트엔드 개발자에 지원하는 분들께 도움이 되었으면 좋겠습니다. 코드 설명이 필요한 분들은 댓글 달아주시면 최대한 빨리 답변드릴게요. 피드백도 환영합니다.
본문에 포함된 예제는 모두 자바스크립트 ES6 기준으로 작성했습니다.
탐욕 알고리즘
탐욕 알고리즘(Greedy)은 현재 상황에서 문제 해결을 위한 가장 좋아 보이는 것을 고르는 방법입니다. 이렇게 매순간 최적의 해라 생각되는 방법을 토대로 반복하여, 결과적으로 최적의 해에 도달하는 것입니다. 탐욕 알고리즘은 알고리즘에 대한 사전 지식을 많이 요구하지 않는 대신, 문제 해결에 대한 창의적인 접근이 필요합니다.
대표 예제로 거스름돈 문제를 가져왔습니다.
// [문제] 손님에게 돈을 받았을 때, 거스름돈으로 줘야 하는 동전을 최소화하기
const coins = [500, 100, 50, 10];
let money = 2370;
let result = 0;
// 단위가 큰 동전부터 처리하기
coins.forEach((coin) => {
result = result + Math.floor(money / coin);
money = money % coin;
});
// 10 (500: 4, 100: 3, 50: 1, 10: 2)
log(result);
문제 유형을 바로 파악하기 어렵다면 탐욕 알고리즘으로 해결 가능한지 먼저 시도해 보고, 탐욕 알고리즘으로 해결이 불가능한 것 같으면 그때는 동적 프로그래밍을 포함한 다른 알고리즘으로 해결을 시도해야 합니다.
완전 탐색
완전 탐색(Brute Force)은 모든 경우의 수를 계산하는 방법입니다. 모든 경우의 수를 계산하여 문제를 해결하기 때문에, 반복문과 조건문에 대해 알고 있으면 좋습니다. 바로 이어서 소개할 시뮬레이션과 함께 구현 유형으로 묶이며, 구현 유형의 문제는 문법을 어느 정도는 알고 있어야 편하게 접근할 수 있습니다.
완전 탐색의 대표 예제로 숫자 야구 게임을 가져왔습니다.
// [문제] 친구가 생각하고 있을 가능성이 높은 숫자의 개수 맞추기
// 친구가 123을 생각하고 있다면, 147은 1스트라이크 0볼이다. (자릿수까지 일치해야 스트라이크)
// 친구가 123을 생각하고 있다면, 213은 1스트라이크 2볼이다. (자릿수는 일치하지 않지만, 포함된 숫자라면 볼)
// [내가 예측한 숫자, 스트라이크 개수, 볼 개수]
const input = [
[123, 1, 1],
[356, 1, 0],
[327, 2, 0],
[489, 0, 1],
];
const answer = [];
// 불필요한 경우의 수 제거
for (let i = 123; i <= 987; i++) {
const temp = String(i);
// 숫자는 중복될 수 없으며, 0 또한 존재할 수 없음 (ex. 131, 190, 200 등)
if (temp.includes('0') || temp[0] === temp[1] || temp[1] === [2] || temp[2] === temp[0]) continue;
answer.push(temp);
}
// 경우의 수 모두 확인
input.forEach((data) => {
// 내가 예측한 숫자
const temp = String(data[0]);
for (let i = answer.length - 1; i >= 0; i--) {
let [strike, ball] = [0, 0];
for (let j = 0; j < 3; j++) {
// 숫자와 자릿수가 모두 일치하면 스트라이크
if (answer[i][j] === temp[j]) strike++;
// 숫자는 포함되어 있지만, 자릿수가 다르다면 볼
if (answer[i][(j + 1) % 3] === temp[j] || answer[i][(j + 2) % 3] === temp[j]) ball++;
}
// 스트라이크와 볼의 개수가 맞지 않는 경우 모두 제거
if (strike !== data[1] || ball !== data[2]) answer.splice(i, 1);
}
});
// 2 (324, 328)
log(answer.length);
시뮬레이션
시뮬레이션(Simulation)은 알고리즘 해결을 위한 방법이 아닌 문제 유형의 한 종류입니다. 시뮬레이션은 출제자가 요구하는 사항에 따라 한 단계씩 단계별로 문제를 해결해 나가면 되는데, 완전 탐색과 마찬가지로 사용하는 언어에 대한 문법을 많이 알고 있는 것이 좋습니다. 예를 들어 문자열에 포함된 문자 중 홀수번째의 문자만 대문자로 변환해야 하는 경우, 문자를 대문자로 변환해주는 메소드를 알고 있으면 빠르게 해결할 수 있는 것처럼 말이지요.
시뮬레이션의 대표 예제로 게임 개발을 가져왔습니다.
// [문제] 캐릭터는 다음 순서에 따라 맵을 이동한다.
// 1. 현재 바라보는 방향에서 반시계 방향으로 90도 회전한다.
// 2. 앞으로 갈 수 있다면 이동하고, 갈 수 없다면 다시 반시계 방향으로 90도 회전한다. (네 방향 반복)
// 3. 네 방향을 모두 가봤다면 뒤로 돌아가는데, 뒤쪽 방향이 갈 수 있다면 돌아가고, 갈 수 없는 벽이라면 종료한다.
// 캐릭터가 방문한 위치는 총 몇 군데인지 확인하자.
// 캐릭터의 위치, 바라보는 방향 (0: 북쪽, 1: 동쪽, 2: 남쪽, 3: 서쪽)
let [position, direction] = [[1, 1], 0];
// 움직임 값 (Move X, Y)
mx = [-1, 0, 1, 0];
my = [0, 1, 0, -1];
// 맵(0: 땅, 1: 벽), 방문 체크(0: 미방문, 1: 방문)
const map = [
[1, 1, 1, 1],
[1, 0, 0, 1],
[1, 1, 0, 1],
[1, 1, 1, 1],
];
const visit = [
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
];
// 시작 지점 방문 처리
visit[position[0]][position[1]] = 1;
let count = 1;
// 반시계 방향으로 회전하는 함수
function turn() {
direction = direction - 1;
if (direction < 0) direction = 3;
}
// 회전 횟수
let turnCount = 0;
while (true) {
// 반시계 방향 회전
turn();
turnCount++;
// 회전 후 이동 계산 (Next X, Y)
[nx, ny] = [position[0] + mx[direction], position[1] + my[direction]];
// 이동할 방향이 벽이 아니면서, 방문하지 않은 경우
if (map[nx][ny] === 0 && visit[nx][ny] === 0) {
position = [nx, ny];
visit[nx][ny] = 1;
count++;
turnCount = 0;
}
// 네 방향 모두 확인한 경우
if (turnCount === 4) {
// 돌아갈 위치 계산 (Next X, Y)
[nx, ny] = [position[0] - mx[direction], position[1] - my[direction]];
// 돌아갈 곳이 벽인 경우
if (map[nx][ny] === 1) break;
else {
position = [nx, ny];
turnCount = 0;
}
}
}
log(count);
대부분의 코딩 테스트는 검색을 허용해 주기에 크게 부담되는 부분은 아니지만, 사전에 이러한 문법을 많이 알고 있다면 문제 해결에 필요한 시간을 절약할 수 있습니다.
정렬 알고리즘
자바스크립트에서 객체 또는 배열을 정렬할 때는 sort 메소드를 사용합니다. 호출만 하면 되기 때문에 사용이 간단하지만, 기본적으로 값을 비교할 때 숫자가 아닌 문자 순서를 토대로 비교하기 때문에 이 점을 유의해야 합니다. 그리고 이 메소드는 배열만 사용 가능한 메소드이므로, 객체를 대상으로 정렬 시 배열로 변환 후 사용해야 합니다.
// 문자 순서로 정렬되므로 [ 1, 14, 2, 22, 3]이 됨
const array = [2, 3, 1, 14, 22];
array.sort();
// 오름 또는 내림차순으로 정렬하고 싶다면, 인자를 사용해야 함
array.sort((a, b) => a - b); // 오름차순
array.sort((a, b) => b - a); // 내림차순
// 객체 정렬 시 배열 형태로 변환하면서 호출해야 함
const obj = { x: 5, y: 2, z: 3 };
let temp = Object.entries(obj).sort(([, a], [, b]) => a - b);
log(Object.fromEntries(temp));
기본 정렬 메소드와 함께 퀵 정렬(Quick Sort)까지 소개하고 넘어가려 합니다. 퀵 정렬은 기준이 되는 요소를 정한 후 기준보다 작은 값이면 왼쪽으로, 기준보다 큰 값이면 오른쪽으로 모으는 식으로 정렬하는 알고리즘입니다. 분해한 후에는 분해된 각각의 리스트를 가지고, 분해를 더 이상 할 수 없을 때까지 동일한 작업을 수행합니다. 이렇게 분해된 요소들이 마지막에는 합쳐지면서 결국 정렬이 완료되는데, 이러한 방식을 분할 정복(Divide and Quanquer)이라 합니다.
function quickSort(arr) {
// 길이가 1 이하라면 정렬할 필요가 없음
if (arr.length <= 1) return arr;
// 첫 번째 원소를 기준으로 설정
const pivot = arr[0];
// 피봇 요소를 기준으로 작은 값, 큰 값을 가진 배열을 만듦
const left = arr.filter((item) => item < pivot);
const right = arr.filter((item) => item > pivot);
// 분할된 배열도 퀵 정렬을 재귀 호출하며 정렬해 나감
// concat은 배열을 병합해 하나로 만드는 메소드
return quickSort(left).concat([pivot], quickSort(right));
}
const array = [2, 5, 4, 3, 1, 7, 6];
quickSort(array);
퀵 정렬 외에도 수많은 정렬 알고리즘이 있는데, 각 정렬 알고리즘마다 안정성, 복잡도(성능)가 모두 다릅니다. 그리고 자바스크립트는 기본 정렬 알고리즘으로 팀 정렬(Tim Sort)을 채택하고 있습니다. 본문에 담기에는 내용이 너무 방대해지므로, 관심 있는 분들은 별도로 확인해 보시기 바랍니다.
이진 탐색
이진 탐색(Binary Search)은 앞에서부터 순차적으로 탐색하는 순차 탐색(Linear Search)의 성능적 단점을 보완하기 위해 등장한 알고리즘입니다. 이미 정렬이 완료된 데이터 집합을 대상으로만 사용할 수 있다는 단점이 있지만, 이름에 걸맞게 원하는 값을 찾을 때까지 탐색 대상을 절반씩 줄여나가며 빠르게 탐색합니다. 간단하지만 처음 구현할 때는 어려울 수 있어 기본 구현 코드를 먼저 보여드리면서, 예제 문제도 함께 소개하겠습니다.
function binarySearch(arr, target, start, end) {
if (start > end) return null;
const mid = Math.floor((start + end) / 2);
// 가운데 값을 비교 후 분기에 따라 처리
if (arr[mid] === target) return mid;
else if (arr[mid] < target) return binarySearch(arr, target, mid + 1, end);
else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
}
const array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
log(binarySearch(array, 2, 0, array.length - 1));
이어서 이진 탐색을 활용해 해결해야 하는 예제 문제입니다.
// [문제] 떡볶이 떡 만들기
// 손님이 떡볶이를 만들기 위해 떡을 사러 왔다.
// 떡은 너무 길기 때문에 절단기를 통해 손님이 원하는 만큼 잘라줘야 한다.
// 절단기로 떡을 자를 때는 모든 떡이 일괄로 잘리게 된다.
// 떡이 17cm, 19cm, 14cm 세 개가 있고, 절단기의 높이가 15cm라면 잘랐을 때 총 6cm가 나온다.
// 손님이 원하는 길이로 잘라주려면 절단기의 높이를 몇으로 해야 하는가?
// 손님이 원하는 길이와 떡들의 길이
const need = 6;
const dduks = [19, 15, 10, 17];
// end 값으로 가장 길이가 긴 떡을 사용해 이진 탐색을 돌리면 된다.
function binarySearch(arr, target, start, end) {
if (start > end) return null;
// 중앙값으로 떡들을 자른 후 길이를 더함
const cut = Math.floor((start + end) / 2);
const sum = arr.reduce((pre, cur) => {
let temp = cur - cut;
return temp <= 0 ? pre : pre + temp;
}, 0);
if (sum === target) return cut;
else if (sum < target) return binarySearch(arr, target, start, cut - 1);
else if (sum > target) return binarySearch(arr, target, cut + 1, end);
}
// 15cm로 잘라줘야 손님이 원하는 6cm를 얻어갈 수 있음
log(binarySearch(dduks, need, 0, Math.max(...dduks)));
간단한 이진 탐색 문제는 재귀적으로 구현하는 것보다 반복문으로 처리하는 것이 좋을 수 있습니다.
동적 프로그래밍
동적 프로그래밍(Dynamic Programming)은 알고리즘의 성능을 최적화하는 방법 중 메모리를 좀 더 사용하면서 연산 속도를 높이는 방법입니다. 주로 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제에서 해결한 답이 큰 문제에서도 사용될 때 활용할 수 있습니다. 동적 프로그래밍이 필요한 상황에 대한 예제로 피보나치 수열이 있습니다.
// 성능이 너무나 느린 피보나치 수열 함수
// f(3)으로 시작하면, f(2)와 f(1)을 호출하게 되고, f(2)는 또 f(1)을 호출한다.
function fibo(n) {
if (n === 1 || n === 2) return 1;
return fibo(n - 1) + fibo(n - 2);
}
// 프로그램 멈춤
log(fibo(100));
// 성능을 개선한 피보나치 수열 함수 (메모이제이션)
// 위의 함수와 다르게 중복된 부분 호출 시 메모리에 저장된 값만 반환하며 끝낸다.
const memo = Array.from({ length: 1000 });
function fibo2(n) {
if (n === 1 || n === 2) return 1;
if (memo[n]) return memo[n];
else {
memo[n] = fibo2(n - 1) + fibo2(n - 2);
return memo[n];
}
}
// 아주 쌩쌩함
log(fibo2(100));
재귀 호출만 가지고 구현을 하게 되면 불필요하게 반복되는 작업이 많아 조금만 수열 값이 커지더라도 프로그램이 금방 죽게 됩니다. 따라서 이미 계산한 값은 이후 계산할 필요 없도록 미리 준비한 데이터 집합(배열, 객체)에 저장하게 되는데, 이렇게 계산한 결과를 저장해 두고 필요할 때 사용하는 기법을 메모이제이션(Memoization) 또는 캐싱이라 합니다. 메모이제이션은 다이나믹 프로그래밍을 구사할 때 많이 사용하는 기법입니다.
다음은 동적 프로그래밍으로 풀어본 예제 문제입니다.
// [문제] 효율적으로 화폐 구성하기
// N 종류의 화폐가 있을 때, 화폐들을 최소한으로 사용하여 M원을 만들어 보자.
const [n, m] = [2, 15];
const coins = [2, 3];
// 모든 요소를 정수 최댓값으로 초기화 (아직 구성이 불가함)
const memo = Array.from({ length: m + 1 }, () => Number.MAX_VALUE);
// 0원은 화폐를 쓰지 않고도 구성 가능하니 0으로 초기화
memo[0] = 0;
// 상향식(Bottom-Up)으로 문제 해결
for (let i = 0; i < n; i++) {
for (let j = coins[i]; j <= m; j++) {
// 화폐 단위에 따른 처리
// 2원(j = 2)으로는 "2원: 1개, 4원: 2개, 6원: 3개, ..."가 필요함
// 3원(j = 3)으로는 "3원: 1개, 6원: 2개, ..."가 필요한데,
// 6원을 만들 때 3원으로 만들면 더 적은 개수로 만들 수 있으므로 갱신
memo[j] = Math.min(memo[j], memo[j - coins[i]] + 1);
}
}
// 5
log(memo[m]);
동적 프로그래밍 문제를 해결할 때는 점화식(인접한 항들의 관계식)을 세워보고 코드로 구현해 보는 것이 좋습니다. 그리고 재귀적으로 호출하는 방식을 하향식 기법(Top-Down)이라 부르며, 반복문을 이용한 방식을 상향식 기법(Bottom-Up)이라 부릅니다. 재귀적으로 큰 문제에서 작은 문제들을 호출해 나가며 문제를 해결하는 것도 좋지만 이런 경우 스택 사용에 제한이 있을 수 있으니, 작은 문제부터 차근차근 해결해 나가는 상향식 기법을 먼저 사용하는 것을 추천합니다.
위에서 소개한 퀵 정렬 역시 큰 부분을 잘게 쪼개서 문제를 해결하는 분할 정복 방식의 알고리즘이라 했습니다. 그런데 분할 정복과 동적 프로그래밍의 차이는 그렇게 해결한 문제들이 서로 영향을 미치는지의 여부입니다. 퀵 정렬은 한 번 정렬이 끝난 작은 문제들은 더 이상 건드리지 않지만, 동적 프로그래밍에서 해결한 작은 문제들은 이후 큰 문제를 해결할 때 사용될 수 있습니다.
꼬리 재귀
꼬리 재귀(Tail Recursion)는 재귀 함수를 호출하고, 종료가 되는 마지막 함수에 도달했을 때 최종 값만 반환하는 형태를 말합니다. 이렇게 하면 중간에는 더 이상 연산을 수행할 필요가 없으므로, 굳이 돌아갈 스택을 기억하고 있지 않아도 됩니다. 말로만 보면 이해가 어려울 수 있으니 함께 팩토리얼 예제를 보면서 이해를 돕겠습니다.
// 일반적으로 구현한 팩토리얼
// 마지막 함수가 반환한 값을 중간중간 호출되었던 함수들이 사용한다.
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
log(factorial(5));
// 꼬리 재귀로 구현한 팩토리얼
// 마지막 함수가 반환하는 값이 최종 결과이므로, 중간 함수들은 필요 없다.
function factorial2(n, total = 1) {
if (n === 1) {
return total;
}
return factorial2(n - 1, total * n);
}
log(factorial2(5));
일반적인 팩토리얼 함수는 값을 반환 받은 이후에도 곱하기 연산을 하기 때문에 호출당한 함수는 돌아가야 할 함수의 주소를 기억해야 합니다. 이런 이유에서 꼬리 재귀 방식으로 구현하게 되면 굳이 돌아가지 않더라도 마지막 함수가 반환하는 값이 곧 최종 결과이기 때문에 스택 메모리를 절약할 수 있습니다.
컴파일러가 꼬리 재귀 최적화를 지원하고 있다면 성능이 개선되지만, 지원하고 있지 않다면 일반 재귀 함수로 구현했을 때와 차이가 없습니다.
BFS & DFS
그래프에서 각 지점을 순회하는 방법을 알고 있는 것은 중요하며, 대표적으로 두 가지 알고리즘이 있습니다.
첫 번째는 너비 우선 탐색(Breadth First Search)이고, 두 번째는 깊이 우선 탐색(Depth First Search)입니다. 너비 우선 탐색은 인접한 노드들을 차례대로 방문하는 순회 알고리즘이며, 깊이 우선 탐색은 갈 수 있는 마지막까지 방문한 이후 돌아오는 길에 다른 곳도 끝까지 방문하는 식의 순회 알고리즘입니다. 글로는 이해가 어려울 수 있어 그림을 첨부했는데, 모습은 트리 형태긴 하지만 그래프로 봐도 무방합니다.
BFS는 큐를 사용해서, DFS는 스택 또는 재귀 함수를 사용해 구현할 수 있습니다.
// 그래프 (1번 노드는 2, 3번 노드와 연결되어 있음)
const graph = [[], [2, 3], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6]];
// 방문 여부 체크를 위한 테이블
let visited = Array.from({ length: graph.length }, () => false);
function bfs(graph, start, visited) {
const queue = [];
queue.push(start);
visited[start] = true;
while (queue.length !== 0) {
const now = queue.shift();
process.stdout.write(`${now} `);
// 현재 노드와 인접한 노드 확인 (Adjacency)
for (const adj of graph[now]) {
// 아직 방문하지 않은 노드라면 큐에 추가하고 방문 처리
if (!visited[adj]) {
queue.push(adj);
visited[adj] = true;
}
}
}
}
function dfs(graph, start, visited) {
const stack = [];
stack.push(start);
while (stack.length !== 0) {
const now = stack.pop();
// 이미 방문한 노드가 나왔다면 다시 반복
if (visited[now]) continue;
else visited[now] = true;
process.stdout.write(`${now} `);
// 현재 노드와 인접한 노드를 역순으로 확인 (스택은 선입후출이므로)
for (let i = graph[now].length - 1; i >= 0; i--) {
const adj = graph[now][i];
if (!visited[adj]) {
stack.push(adj);
}
}
}
}
// 1 2 3 7 4 5 6
bfs(graph, 1, visited);
// 방문 테이블 초기화
visited = visited.map(() => false);
// 1 2 7 6 8 3 4
dfs(graph, 1, visited);
다익스트라 알고리즘
다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 노드와 노드사이의 최단 경로를 구할 때 사용하는 알고리즘입니다. 이 알고리즘은 기본적으로 최단 경로를 구할 때 사용되지만, 코딩 테스트 레벨에서는 최단 거리까지만 요구하는 문제가 많이 출제됩니다. 그래서 본문에서는 최단 거리를 구하는 알고리즘 정도만 소개하려 합니다.
다익스트라 알고리즘의 원리는 다음과 같습니다.
- 출발 노드를 선택하고, 방문 처리를 합니다.
- 최단 거리 테이블을 초기화합니다.
- 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택하고, 방문 처리를 합니다.
- 목적지를 다이렉트로 가는 것과 다른 노드를 거쳐가는 것 사이의 비용을 비교하여 최단 거리 테이블을 갱신합니다.
const graph = {
// 노드: { 연결된 노드: 거리 }
1: { 2: 2, 3: 5, 4: 1 },
2: { 3: 3, 4: 2 },
3: { 3: 3, 6: 5 },
4: { 3: 3, 5: 1 },
5: { 3: 1, 6: 2 },
6: {},
};
// 방문 여부 테이블 (처음에는 false로 초기화)
const visited = Array.from({ length: 7 }, () => false);
// 최단 거리 테이블 (가장 큰 정수값으로 초기화)
const distances = Array.from({ length: 7 }, () => Number.MAX_VALUE);
function findShortestNode(distances, visited) {
let min = Number.MAX_VALUE;
let index = -1;
for (let i = 1; i < distances.length; i++) {
// 아직 방문하지 않았으면서, 거리가 가장 짧은 노드를 탐색
if (distances[i] < min && !visited[i]) {
min = distances[i];
index = i;
}
}
return index;
}
function dijkstra(start) {
// 시작 노드를 기준으로 테이블 갱신
distances[start] = 0;
visited[start] = true;
// 시작 노드는 2, 3, 4번 노드로의 최단 거리를 갖고 있음
Object.keys(graph[start]).forEach((v) => (distances[v] = graph[start][v]));
// 나머지 노드에 대해 과정 처리 (2 ~ 6번 노드)
for (let i = 2; i <= 6; i++) {
const now = findShortestNode(distances, visited);
visited[now] = true;
// 인접한 노드로 가는 비용을 비교하여 최단 거리 테이블 갱신
Object.keys(graph[now]).forEach((v) => {
const cost = distances[now] + graph[now][v];
if (distances[v] > cost) {
distances[v] = cost;
}
});
}
}
dijkstra(1);
// [ 0, 2, 3, 1, 2, 4 ]
log(distances);
다익스트라 알고리즘은 최소 힙(Min-Heap)을 사용하면 더욱 짧은 코드로 작성할 수 있습니다. 이는 파이썬에는 내장 라이브러리로 구현이 되어 있지만 자바스크립트에는 없기 때문에 별도 구현이 필요합니다 😅
플로이드 워셜 알고리즘
플로이드 워셜(Floyd Warshall)은 다익스트라와 달리 모든 노드 사이의 최단 경로를 구할 때 사용하는 알고리즘입니다. 플로이드 워셜은 다이나믹 프로그래밍으로 분류하며, 점화식 Dab = min(Dab, Dak + Dkb)에 따라 3중 반복문으로 구현할 수 있습니다. 점화식을 풀어 설명하자면, A에서 B로 갈 때 필요한 비용과 A에서 K를 거쳐 B로 가는 비용 중 더 작은 값을 최단 거리로 결정한다는 것을 의미합니다.
// 4x4 그래프지만 인덱스를 편하게 계산하기 위해 한 칸 더 크게 만듦
// 도달할 수 없는 곳으로의 거리는 1e9 값으로 초기화 (10^9)
// 자기 자신으로의 거리는 0이므로 [1, 1], [2, 2], [3, 3], [4, 4]는 0으로 초기화
const graph = [
[1e9, 1e9, 1e9, 1e9, 1e9],
[1e9, 0, 4, 1e9, 6],
[1e9, 3, 0, 7, 1e9],
[1e9, 5, 1e9, 0, 4],
[1e9, 1e9, 1e9, 2, 0],
];
// 플로이드 워셜 수행
for (let k = 1; k <= 4; k++) {
for (let a = 1; a <= 4; a++) {
for (let b = 1; b <= 4; b++) {
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
// 모든 노드 사이의 최단 거리 확인
log(graph);
다음은 플로이드 워셜을 활용해 해결할 수 있는 예제 문제입니다.
// [문제] 방문 판매원
// 방문 판매원 A는 X회사에 방문해 물건을 판매하려 합니다.
// 그런데 중간에 여자친구를 보고 가기 위해 K회사를 들르기로 했습니다.
// A가 K회사를 들러 X회사에 도착하기까지 걸리는 최소 이동 거리를 계산하세요. (모든 거리는 1)
const [x, k] = [4, 5];
const graph = [
[1e9, 1e9, 1e9, 1e9, 1e9, 1e9],
[1e9, 0, 1, 1, 1, 1e9],
[1e9, 1, 0, 1e9, 1, 1e9],
[1e9, 1, 1e9, 0, 1, 1],
[1e9, 1, 1, 1, 0, 1],
[1e9, 1e9, 1e9, 1, 1, 0],
];
for (let k = 1; k <= 5; k++) {
for (let a = 1; a <= 5; a++) {
for (let b = 1; b <= 5; b++) {
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
// 1번 회사에서 출발하여, K회사를 거쳐 X회사까지 최소 이동 거리 (3)
log(graph[1][k] + graph[k][x]);
크루스칼 알고리즘
크루스칼 알고리즘(Kruskal's Algorithm)은 최소 신장 트리(MST: Minimun Spanning Tree)를 구축할 때 사용하는 알고리즘입니다. 최소 신장 트리란 그래프의 노드들끼리 사이클을 이루지 않으면서 모든 노드가 최소 비용으로 이어진 트리를 말합니다. 컴퓨터 공학에서 트리는 부모-자식 관계를 가지는 자료구조이지만, 부모에서 자식 또는 자식에서 부모를 가리키고 있는 그래프로 볼 수도 있습니다.
최소 신장 트리는 다음 그림과 같이 생겼습니다.
임의의 노드에서 출발한 후 자기 자신의 위치로 다시 돌아올 수 있는 경우 사이클(Cycle)이 발생했다 말합니다. 위 그림에서는 사이클을 제거하면서 인접한 노드들을 모두 최단 거리로 연결했기에 최소 신장 트리라 합니다.
이제 최소 신장 트리가 무엇인지 알았으니 크루스칼 알고리즘을 이용해 만드는 방법을 알아보겠습니다. 크루스칼 알고리즘은 최소 신장 트리를 만들 때 분리 집합(Disjoint Set) 구조를 사용하여 손쉽게 구현합니다. 분리 집합은 두 집합 간 공통된 부분이 없는 집합을 의미하는데, 그래프에서라면 임의의 두 노드가 소속된 집합이 달라 서로가 서로에게 도달할 수 없음을 의미합니다. 분리 집합 구조에서는 주로 합집합 연산 정도만 사용하는데, 두 집합의 부모만 서로 연결하면 끝일 정도로 간단합니다.
function findParent(parent, x) {
// x의 부모가 x가 아니라면, 부모 노드가 있는 것이므로
// 재귀적으로 호출하며 집합의 최상위 부모를 구함
if (parent[x] !== x) {
parent[x] = findParent(parent, parent[x]);
}
return parent[x];
}
function union(parent, a, b) {
// a 노드와 b 노드의 최상위 부모를 구함
a = findParent(parent, a);
b = findParent(parent, b);
// 더 작은 값을 가진 노드를 부모로 설정
if (a < b) parent[b] = a;
else parent[a] = b;
}
// 노드 개수, 부모 테이블 (초기값은 자기 자신으로 설정)
const n = 6;
const parent = Array.from({ length: n + 1 }, (_, i) => i);
// 간선 연결 [노드, 노드, 거리(가중치)]
const edges = [
[1, 2, 29],
[1, 5, 75],
[2, 3, 35],
[2, 6, 34],
[3, 4, 7],
[4, 6, 23],
[5, 6, 53],
];
// 가중치가 가장 짧은 노드부터 연결하도록 정렬
edges.sort((a, b) => a[2] - b[2]);
// 간선 정보를 바탕으로 최소 신장 트리 구축
// 총 거리를 result 변수에 저장
let result = 0;
edges.forEach((edge) => {
const [a, b, cost] = edge;
// 포함된 집합이 같은 경우 두 노드 사이 사이클 발생
// 사이클이 발생하지 않은 경우 합집합 수행과 거리를 누적함
if (findParent(parent, a) !== findParent(parent, b)) {
union(parent, a, b);
result += cost;
}
});
// 총 거리: 146
log(result);
위상 정렬
위상 정렬(Topology Sort)는 사이클이 발생하지 않는 방향성 그래프에서, 진입 방향에 따라 노드를 정렬하는 알고리즘입니다. 위상 정렬에 대해 본격적으로 알아보기 전에 위상 정렬을 하기 전과 후의 그래프를 먼저 확인해 보겠습니다.
방향을 가진 그래프는 각 노드마다 진입 차수(Indegree)라는 것을 갖습니다. 왼쪽 그림을 보면 1번 노드는 0번 노드로부터 이어지기 때문에 진입 차수가 1이며, 5번 노드는 1번과 6번 노드로부터 이어지기 때문에 진입 차수가 2입니다. 위상 정렬은 진입 차수가 0인 노드부터 방문하여 출력하고, 출력을 마친 이후에는 해당 노드에서 다음 노드로 가는 진입 간선을 제거합니다. 진입 차수가 0인 노드들부터 출력 후 제거하고, 남은 노드 중 진입 차수가 0이 된 노드를 출력하는 식입니다.
위상 정렬은 큐(Queue)를 사용하면 간단하게 구현할 수 있습니다.
// 노드 개수, 간선 개수
const [n, e] = [7, 8];
// 연결 정보 [노드, 노드]
const edges = [
[1, 2],
[1, 5],
[2, 3],
[2, 6],
[3, 4],
[4, 7],
[5, 6],
[6, 4],
];
// 진입 차수 초기화
const indegree = Array.from({ length: n + 1 }, () => 0);
edges.forEach((edge) => {
const [_, v] = edge;
indegree[v]++;
});
// 0번 노드는 없는 노드이므로, 제외하고 위상 정렬 수행
const queue = [];
for (let v = 1; v <= n; v++) {
if (indegree[v] === 0) queue.push(v);
}
// 최종 출력 결과는 1 2 5 3 6 4 7
while (queue.length !== 0) {
// 큐의 맨 앞 노드를 제거한 후 출력
const now = queue.shift();
process.stdout.write(`${now} `);
// 연결된 노드와의 진입 간선 제거
for (const edge of edges) {
if (edge[0] === now) {
indegree[edge[1]]--;
// 진입 차수가 0이 되었다면 큐에 삽입
if (indegree[edge[1]] === 0) queue.push(edge[1]);
}
}
}
아직 정렬이 끝나지 않았는데 중간에 큐가 비게 된다면 사이클이 발생한 상황입니다.
예제 문제로는 위상 정렬이 활용되는 대표 문제 중 하나인 커리큘럼 문제를 가져왔습니다.
// [문제] 커리큘럼
// 온라인 강의를 들으려 하는데, 특정 강의는 선수 강의가 있다.
// A강의는 10시간, B강의는 20시간, C강의는 10시간 동안 수강한다.
// C강의는 선수 강의로 A와 B를 들어야 하며, 이 경우 C까지 모두 듣는데 소요되는 시간은 총 30시간이다.
// ㄴ A와 B는 선수 강의가 없으며 동시에 들을 수 있으므로, 20시간이면 둘 다 들을 수 있다.
// 듣고자 하는 N개의 강의 정보가 주어질 때, N개의 강의를 각각 듣는데 필요한 최소 시간을 구하자.
// 강의 수
const n = 5;
// 강의 정보 [수강시간, 선수강의,-1] <- 정보의 끝을 -1로 표기
const infos = [[], [10, -1], [10, 1, -1], [4, 1, -1], [4, 3, 1, -1], [3, 3, -1]];
// 그래프, 진입 차수, 수강 시간 초기화
const graph = Array.from({ length: n + 1 }, () => []);
const indegree = Array.from({ length: n + 1 }, () => 0);
const time = Array.from({ length: n + 1 }, () => 0);
infos.forEach((info, index) => {
// info의 1번 인덱스부터 마지막 인덱스를 제외한 부분이 선수 강의
// [4, 3, 1, -1]을 아래 인자로 슬라이스하면 [3, 1]만 잘려나옴
// 그렇기 때문에 4번 노드의 진입 차수는 [3, 1]의 길이인 2를 할당하면 됨
const sliced = info.slice(1, -1);
indegree[index] = sliced.length;
// 슬라이스 된 배열을 토대로 그래프도 만듦
sliced.forEach((v) => graph[v].push(index));
// 수강 시간은 info의 맨 앞 값을 사용하면 됨
time[index] = info[0];
});
// 위상 정렬을 수행하며 수강 시간 계산
const queue = [];
for (let v = 1; v <= n; v++) {
if (indegree[v] === 0) queue.push(v);
}
// 시간 테이블을 복사하여 사용
const temp = [...time];
while (queue.length !== 0) {
const now = queue.shift();
// 현재 노드와 연결된 노드로의 진입 간선 제거
for (const v of graph[now]) {
// 해당 강의를 듣기 위해 필요한 최소 시간 갱신
time[v] = Math.max(time[v], temp[now] + time[v]);
indegree[v]--;
if (indegree[v] === 0) queue.push(v);
}
}
// 강의별 소요 시간 [ 10, 20, 14, 18, 7 ]
log(time);
행렬 회전 알고리즘
행렬 회전(Transpose)은 행과 열을 맞바꿔 전치 행렬을 만드는 알고리즘입니다. 위상 정렬을 마지막으로 끝내려 했는데, 행렬 회전도 종종 써먹을 필요가 있을 것 같아 본문의 마지막 알고리즘으로 준비했습니다.
const array = [
[1, 1, 1, 1, 1],
[2, 2, 2, 2, 2],
[3, 3, 3, 3, 3],
[4, 4, 4, 4, 4],
[5, 5, 5, 5, 5],
];
// 시계 방향 회전
function transpose(matrix) {
return matrix.reduce((result, col) => {
return col.map((_, i) => {
return [col[i], ...(result[i] || [])];
});
}, []);
}
// 반시계 방향 회전
function transposeReverse(matrix) {
return matrix.reduce((result, col) => {
return col.map((_, i) => {
return [...(result[i] || []), col[i]];
});
}, []);
}
log(transpose(array));
log(transposeReverse(array));
자주 사용되지만 매번 구현하기에는 번거로운 알고리즘이 있습니다. 이런 경우 미리미리 깃허브 저장소나 노트에 정리해 두면, 필요할 때마다 빠르게 참조할 수 있어 편리합니다.
저도 여러분도 함께 힘내요 🎉
탐욕 알고리즘부터 시작하여 행렬 회전 알고리즘까지 코딩 테스트에서 자주 보이는 알고리즘과 유형들을 준비해 봤습니다. 어떤 알고리즘은 기본 코드만 소개했고, 또 어떤 알고리즘은 응용해서 풀 수 있는 예제 문제까지 함께 소개했습니다. 예제 문제를 보면 알 수 있듯 모든 문제는 기본 알고리즘을 활용해 해결할 수 있습니다. 다만 문제 해결을 위해서 어떻게 접근해야 하는 지를 찾는 것이 문제지요. 저도 기본 알고리즘을 이제는 어느 정도 이해했지만, 막상 문제를 풀 때는 어떻게 활용할 수 있는지 여전히 감이 잘 안 잡힙니다. 그런데 어쩌겠어요. 많이 풀어봐야죠 ㅠ
여튼 여러분도 기본이 되는 알고리즘부터 가볍게 익혀보시고, 시간이 날 때마다 문제를 조금이라도 풀어보시는 것을 추천드립니다. 물론 너무 알고리즘에만 시간을 할애하지는 마시구요. 알고리즘을 이해하면서 컴퓨팅적으로 사고하는 능력을 기르는 것은 중요하지만, 실질적으로 우리는 기술(React, Next, Electron 등)을 바탕으로 서비스를 만들어나갈 거잖아요. 그러니 기술과 알고리즘을 서로 병행하면서 공부해 나가시길 바랍니다.
마지막으로 저는 나동빈님께서 내신 책인 이것이 취업을 위한 코딩 테스트 with. Python과 GeeksforGeeks라는 사이트(영문)의 글을 읽으면서 알고리즘과 자료구조를 공부했습니다. 한글이면서 자바스크립트를 메인 언어로 한 참고 자료를 찾기가 힘든 편인데, 만약 파이썬 언어의 문법을 조금이라도 알고 계시다면 위 책을 보면서 자바스크립트 코드로 옮겨 보시는 것을 추천드리고, 영어가 부담 없다 하시는 분들은 GeeksforGeeks를 들러 보시기 바랍니다.
열심히 해서 주니어 프론트엔드 개발자로 함께 성장해 봐요! (아 프론트엔드 개발자 되고 싶다)
참고 자료
'💻 컴퓨터공학 > 알고리즘' 카테고리의 다른 글
다익스트라 알고리즘으로 경로 나타내기 (0) | 2022.02.20 |
---|---|
자바스크립트스럽게 퀵 정렬 구현하기 (0) | 2022.02.10 |
스택을 이용한 계산기 만들기 (0) | 2022.02.01 |
이진 탐색 (Binary Search) (0) | 2021.10.28 |
정렬 알고리즘 (Sorting Algorithms) (0) | 2021.10.27 |
댓글
이 글 공유하기
다른 글
-
다익스트라 알고리즘으로 경로 나타내기
다익스트라 알고리즘으로 경로 나타내기
2022.02.20 -
자바스크립트스럽게 퀵 정렬 구현하기
자바스크립트스럽게 퀵 정렬 구현하기
2022.02.10 -
스택을 이용한 계산기 만들기
스택을 이용한 계산기 만들기
2022.02.01 -
이진 탐색 (Binary Search)
이진 탐색 (Binary Search)
2021.10.28