[algorithm] 배열 나선 순회 Spiral Traverse
문제 2차원 M x N 배열을 나선형(spiral)으로 순회해야 한다. 입출력 예시 let matrix = [ ['A', 'B', 'C'], ['D', 'E', 'F'], ['G', 'H', 'I'], ]; let output = spiralTraversal(matrix); console.log(output); // --> 'ABCFIHGDE' matrix = [ ['T', 'y', 'r', 'i'], ['i', 's', 't', 'o'], ['..
2022. 1. 12.
[algorithm] Decompression
문제 한 변의 길이가 2의 제곱수인 정사각형의 흑백 이미지가 2차원 배열로 주어진다. 각 좌표에는 0(백) 또는 1(흑)이 저장되어 있다. 이미지에 포함된 데이터가 모두 1이면 '1', 모두 0이면 '0' 한 글자로 압축할 수 있다. 그렇지 않은 경우, 이를 대문자 X로 표시하고 전체를 4등분하여 재귀적으로 압축한다. 4등분한 영역의 순서는 좌측 상단, 우측 상단, 좌측 하단, 우측 하단이다. 입출력 예시 let image = [ [1, 0, 1, 1], [0, 1, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0], ]; let result = decompression(image); console.log(result); // --> 'XX100110X110..
2022. 1. 12.
[algorithm] LIS
문제 정수를 요소로 갖는 문자열을 입력받아 다음의 조건을 만족하는 LIS의 길이를 리턴해야 한다. LIS: 배열의 연속되지 않는 부분 배열 중 모든 요소가 엄격하게 오름차순으로 정렬된 가장 긴 부분 배열(Longest Increasing Subsequence) 배열 [1, 2, 3]의 subseqeunce는 [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3] 이다. 엄격한 오름차순: 배열이 동일한 값을 가진 요소없이 오름차순으로 정렬되어 있는 경우를 말한다. 코드(JavaScript) const LIS = function (arr) { arr.unshift(Number.MIN_SAFE_INTEGER); const len = arr.length; let cache = A..
2022. 1. 12.
[algorithm] 로봇
문제 세로와 가로의 길이가 각각 M, N인 방의 지도가 2차원 배열로 주어졌을 때, 1은 장애물을 의미하고 0 이동이 가능한 통로를 의미합니다. 로봇은 한 번에 임의의 k칸 직진과 90도 회전 중 1가지 동작을 할 수 있다. 로봇의 현재 위치와 방향, 목표 지점과 방향이 함께 주어집니다. 이 때, 방향은 위쪽이 1, 오른쪽이 2, 아래쪽이 3, 왼쪽이 4로 주어집니다. 로봇이 목표 지점까지 도달해 목표 방향으로 회전하는 데 필요한 동작의 수를 리턴해야 합니다. 입출력 예시 let room = [ [0, 0, 0, 0], [0, 1, 1, 0], [0, 1, 0, 0], [0, 0, 1, 1], ]; let src = [3, 0]; let sDir = 3; let dst = [2, 2]; let dDir ..
2022. 1. 12.
[algorithm] 미로탐색 BFS
문제 세로와 가로의 길이가 각각 M, N인 방의 지도가 2차원 배열로 주어졌을 때, 1은 장애물을 의미하고 0 이동이 가능한 통로를 의미한다. 로봇은 지도 위를 일분에 한 칸씩 상하좌우로 이동할 수 있다. 로봇의 위치와 목표 지점이 함께 주어질 경우, 로봇이 목표 지점까지 도달하는 데 걸리는 최소 시간을 리턴해야 한다. 입출력 예시 let room = [ [0, 0, 0, 0, 0, 0], [0, 1, 1, 0, 1, 0], [0, 1, 0, 0, 0, 0], [0, 0, 1, 1, 1, 0], [1, 0, 0, 0, 0, 0], ]; let src = [4, 2]; let dst = [2, 2]; let output = robotPath(room, src, dst); console.log(output)..
2022. 1. 12.
[algorithm] Sweeping algorithm, 백준 화성지도
문제 좌표평면 위에 존재하는 수많은 직사각형에 대한 정보가 2차원 배열로 주어진다. 이 직사각형들은 서로 겹쳐 있을(overlapping) 수 있다. 이 직사각형들이 이루는 면적을 리턴해야 한다. 백준 3392번에서 확인할 수 있다. 입출력 예시 let result = shadowOfPapers([[0, 1, 4, 4]]); console.log(result); // --> 16 /* 4 | x x x x 3 | x x x x 2 | x x x x 1 | x x x x 0 | -------------- 0 1 2 3 4 */ result = shadowOfPapers([ [0, 0, 4, 4], [2, 1, 2, 6], [1, 5, 5, 3], [2, 2, 3, 3], ]); console.log(res..
2022. 1. 12.
[algorithm] 보드게임(JavaScript)
문제 첫 번째 입력으로 [N, M] 크기의 보드판이 주어진다. 보드 칸에는 숫자가 적혀있다. 두 번째 입력으로 움직임을 나타내는 문자열이 주어진다. U는 위로, D는 아래로, L는 왼쪽, R는 오른쪽으로 움직이라는 뜻이다. 말이 어떠한 위치로 움직였을 때 그 자리에 해당한 점수를 획득한다. 말이 보드판을 벗어나는 경우 그 움직임은 무시된다. 즉 원래 자리를 유지한다. 또한 한 곳에서는 한 번만 점수를 획득할 수 있다. 즉 이미 방문한 곳에 다시 들리면 추가로 획득하는 점수가 없다. [0, 0] 위치부터 시작해 두 번째 입력으로 주어진 모든 움직임을 수행했을 때 획득한 점수를 구하라. 입출력 예시 const board1 = [ [72, 0, 80, 1], [1, 9, 11, 10], [1, 1, 792, ..
2022. 1. 11.