[algorithm] Ugly Numbers 알고리즘
문제 2, 3, 5로만 나누어지는 배열에서 N번 째 수를 구하라. 단 배열의 첫 번째 수는 1이다. [1, 2, 3, 4, 5, 6, 8, 9, 10, ...] Geeksforgeeks 홈페이지의 코드를 참고하여 풀었다. 구현코드 단순 방식 const uglyNumbers = function (n) { let i = 1; let count = 1; while (count { i = maxDivide(i, 2); i = maxDivide(i, 3); i = maxDivide(i, 5); return i === 1 ? 1 : 0; } const maxDivide = (a, b) =>..
2021. 12. 30.
[algorithm] 힙정렬 알고리즘, 최소힙 이용
문제 힙을 이용하여 주어진 배열을 오름차 정렬해야 한다. 예제: let output = heapSort([5, 4, 3, 2, 1]); console.log(output); // [1, 2, 3, 4, 5] 풀이 전략 배열을 힙으로 만든다. 최대힙으로 만들어도 되고, 최소힙으로 만들어도 된다. 나중에 정렬할 때 약간의 차이가 있다. 만든 힙을 정렬한다. 2-1. 최대힙인 경우 루트에 가장 큰 값이 오기 때문에 루트와 맨 뒤의 값을 바꾸면서 재정렬하면 오름차순 배열이 된다. 2-2. 최소힙인 경우 루트에 가장 작은 값이 오기 때문에 루트와 맨 뒤의 값을 바꾸면서 재정렬하면 내림차순 배열이 된다. 재정렬하는 하는 과정(최소힙 기준) 3-1. 루트와 맨 뒤의 값을 바꾼다. 결과 맨 뒤에는 가장 작은 값이 온다..
2021. 12. 23.
[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 d..
2021. 12. 20.
[algorithm] LSCS, 연속부분배열의 최대합 문제
문제 정수 배열이 입력으로 주어졌을 때, 연속된 부분 배열의 합 중에서 가장 큰 값을 구하라 문제분석 [2] => 2 [2, -3] => 2 [2, -3, 4] => 3 [2, -3, 2] => 2 [2, -3, 4, 1] => 4 [2, -3, 2, 1] => 3 구현코드 JavaScript const LSCS = function (arr) { let curr_max = arr[0]; let S = arr[0]; for (let i = 1; i < arr.length; i++) { curr_max = Math.max(curr_max + arr[i], arr[i]); S = Math.max(S, curr_max); } return S; };마무리 코드는 진짜 짧다. 너무 짧다. 이해하는 건 힘들다. DP..
2021. 12. 20.