[algorithm] Radix Sort, 기수정렬
문제 정수 배열을 입력받아 오름차순 정렬한다. 입력: 170, 45, 75, 90, 802, 24, 2, 66 출력: 2, 24, 45, 66, 75, 90, 170, 802기본로직 170, 90, 802, 2, 24, 45, 75, 661의 자리 숫자를 기준으로 정렬한다. 802, 2, 24, 45, 66, 75, 170, 90얻어진 배열을 10의 자리 숫자를 기준으로 정렬한다. 2, 24, 45, 66, 75, 90, 170, 802다시 100의 자리 숫자를 기준으로 정렬한다. 정렬 횟수는 입력값 중 가장 긴 수의 자릿수가 된다. 예제에서는 가장 긴 수인 170과 802의 길이가 3이고, 정렬 3번 만에 결과를 얻는다. 각각의 정렬은 Counting Sort로 구현한다. 계수 정렬을 사용하는 이유는 ..
2022. 1. 19.
[algorithm] 새로운 치킨 소스 레시피
문제 N 가지의 재료 중에 단 M 가지만을 사용하여 조합한 모든 경우의 수 중 하나이다. 재료는 0과 1로만 이루어진 숫자로 암호화가 되어 있고, 항상 1로 시작하며 복호화를 할 수 없다. 단, 0이 3개 이상인 재료는 상한 재료이기 때문에 제외한다. 재료의 순서에 따라 맛이 달라지기 때문에, 재료를 넣는 순서가 다르다면 다른 레시피이다. 이상의 설명을 참고하여 소스 레시피를 전부 구하시오. 입출력 예시 const output1 = newChickenRecipe([1, 10, 1100, 1111], 2); console.log(output1); /* [ [1, 10], [1, 1100], [1, 1111], [10, 1], [10, 1100], [10, 1111], [1100, 1], [1100, 10]..
2022. 1. 12.
[algorithm] 금고를 털어라. DP 알고리즘
문제 훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 target 을 훔칠 수 있는 방법의 수를 리턴하시오. 입출력 예시 let output = ocean(50, [10, 20, 50]); console.log(output); // 4 let output = ocean(100, [10, 20, 50]); console.log(output); // 10 let output = ocean(30, [5, 6, 7]); console.log(output); // 4 코드(JavaScript) function ocean(target, type) { type.unshift(0); let memo = Array.from(Array(type.length), () => Array(t..
2022. 1. 12.
[algorithm] 보드게임
문제 보드판이 담긴 board와 조작하려고 하는 문자열 operation이 주어질 때, 말이 해당 칸을 지나가면서 획득한 숫자의 합을 구하는 함수를 작성하시오. 만약, 말이 보드 밖으로 나갔다면 즉시 OUT 을 반환한다. 입출력 예시 const board1 = [ [0, 0, 0, 1], [1, 1, 1, 0], [1, 1, 0, 0], [0, 0, 0, 0] ] const output1 = boardGame(board1, 'RRDLLD'); console.log(output1); // 4 const board2 = [ [0, 0, 1], [1, 1, 1], [1, 0, 0] ] const output2 = boardGame(board2, 'UUUDD'); console.lo..
2022. 1. 12.
[algorithm] 편의점 알바
문제 편의점에서 아르바이트를 하고 있는 중에, 하필이면 피크 시간대에 손님에게 거스름돈으로 줄 동전이 부족하다는 것을 알게 되었다. 현재 가지고 있는 동전은 1원, 5원, 10원, 50원, 100원, 500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있다. 동전 개수를 최소화하여 거스름돈 K를 만들어야 한다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성하시오. 입출력 예시 // 4000원을 받았을 때 500원짜리 동전 8개를 반환합니다. const output1 = test1(4000); console.log(output1); // --> 8 // 4972원을 받았을 때 500원짜리 동전 9개, 100원짜리 동전 4개, 50원짜리 동전 1개, 10원짜리 동전 2개, 1원짜..
2022. 1. 12.
[algorithm] 짐 나르기
문제 짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하시오. 예를 들어, 짐의 무게가 [70kg, 50kg, 80kg, 50kg]이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다. 입출력 예시 let output = movingStuff([70, 50, 80, 50], 100); console.log(output); // 3 let output = movingStuff([60, 80, 120, 90, 130], 140); ..
2022. 1. 12.