1. [Greedy] 짐 나르기
김코딩과 박해커는 사무실 이사를 위해 짐을 미리 싸 둔 뒤, 짐을 넣을 박스를 사왔다. 박스를 사오고 보니 각 이사짐의 무게는 들쭉날쭉한 반면, 박스는 너무 작아서 한번에 최대 2개의 짐 밖에 넣을 수 없었고 무게 제한도 있었다. 예를 들어, 짐의 무게가 [70kg, 50kg, 80kg, 50kg]이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다. 박스를 최대한 적게 사용하여 모든 짐을 옮기려고 합니다. 짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요.
입력
- 인자 1: stuff
Number 타입의 40 이상 240 이하의 자연수를 담은 배열
ex) [70, 50, 80, 50] - 인자 2: limited
Number 타입의 40 이상 240 이하의 자연수
출력
Number 타입을 리턴해야 합니다.
모든 짐을 옮기기 위해 필요한 박스 개수의 최솟값을 숫자로 반환합니다.
주의사항
옮겨야 할 짐의 개수는 1개 이상 50,000개 이하입니다.
박스의 무게 제한은 항상 짐의 무게 중 최대값보다 크게 주어지므로 짐을 나르지 못하는 경우는 없습니다.
입출력 예시
let output = movingStuff([70, 50, 80, 50], 100);
console.log(output); // 3
let output = movingStuff([60, 80, 120, 90, 130], 140);
console.log(output); // 4문제풀이
function movingStuff(stuff, limit) {
// 사용 박스의 수
let count = 0;
// 오름차순으로 정렬해준 후,
//가장 가벼운 것과 가장 무거운 것이 같이 담길 수 있는지 확인한다
stuff.sort((a, b) => a -b)
let left = 0;
let right = stuff.length - 1;
// 가벼운 것과 무거운 것 하나씩 옮기다가 같아질 때까지 반복
while(left <= right) {
// 가벼운 것과 무거운게 limit보다 작으면 둘다 하나씩 이동,
// limit보다 크다면 아니면 무거운것만 하나 담는다
if(stuff[left] + stuff[right] <= limit){
left++
}
right--;
count++
}
return count
}pop과 shift를 사용해서 stuff를 하나씩 삭제하는 방법도 있지만 인데스를 활용하는게 좀 더 효율적이다.
처음에 물건 2개 제한있는 줄모르고 3개나 4개 담을 경우도 생각하니라 괜히 시간썼는데..ㅜ 문제를 잘 읽도록하자ㅜ
2. [Greedy] 편의점 알바
편의점에서 아르바이트를 하고 있는 중에, 하필이면 피크 시간대에 손님에게 거스름돈으로 줄 동전이 부족하다는 것을 알게 되었습니다. 현재 가지고 있는 동전은 1원, 5원, 10원, 50원, 100원, 500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있습니다.
동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성해 주세요.
입력
- 인자: k
number 타입의 k
1 <= k <= 100,000,000
출력
number 타입의 거스름돈 K원을 만드는데 필요한 동전 개수의 최솟값을 반환해야 합니다.
입출력 예시
// 4000원을 받았을 때 500원짜리 동전 8개를 반환합니다.
const output1 = partTimeJob(4000);
console.log(output1); // --> 8
// 4972원을 받았을 때 500원짜리 동전 9개, 100원짜리 동전 4개,
// 50원짜리 동전 1개, 10원짜리 동전 2개, 1원짜리 동전 2개, 총 18개를 반환합니다.
const output2 = partTimeJob(4972);
console.log(output2); // --> 18
문제풀이
function partTimeJob(k) {
//카운트하기 위해 변수 count에 0을 할당
let count = 0;
//입력값에 배열이 들어오지 않으므로 직접 배열 입력
const coins = [500, 100, 50, 10, 5, 1];
//모든 동전 사용을 한번씩 확인해 봐야하므로 coins의 길이-1 만큼 반복
for(let i = 0; i < coins.length; i++){
//거스름돈이 0원이 되면 중지
if(k === 0) break;
//거스름돈과 잔돈을 나눈 몫 세기(쓰인 잔돈의 개수 세기)
count += Math.floor(Number(k/coins[i]));
//거스름돈을 잔돈으로 나눈 나머지를 재할당(반복문을 통해 다음으로 큰 동전으로 반복)
k %= coins[i];
}
return count;
}greedy 방법을 사용할 수 있던 이유는 동전들이 배수 관계였기 때문이다. 배수관계가 아니였다면 이 방법으로 최소 동전 갯수 구할 수 없다.
3. [구현] 보드 게임
N * N의 크기를 가진 보드판 위에서 게임을 하려고 합니다. 게임의 룰은 다음과 같습니다.
1. 좌표 왼쪽 상단(0, 0)에 말을 놓는다.
2. 말은 상, 하, 좌, 우로 이동할 수 있고, 플레이어가 조작할 수 있다.
3. 조작의 기회는 딱 한 번 주어진다. 조작할 때 U, D, L, R은 각각 상, 하, 좌, 우를 의미하며 한 줄에 띄어쓰기 없이 써야 한다. 예시: UDDLLRRDRR, RRRRR
4. 한 번 움직일 때마다 한 칸씩 움직이게 되며, 그 칸 안의 요소인 숫자를 획득할 수 있다.
5. 방문한 곳을 또 방문해도 숫자를 획득할 수 있다.
6. 보드 밖을 나간 말은 OUT 처리가 된다. 칸 안의 숫자는 0 또는 1이다. 단, 좌표 왼쪽 상단(0, 0)은 항상 0이다.
7. 획득한 숫자를 합산하여 숫자가 제일 큰 사람이 이기게 된다.
보드판이 담긴 board와 조작하려고 하는 문자열 operation이 주어질 때, 말이 해당 칸을 지나가면서 획득한 숫자의 합을 구하는 함수를 작성하세요.
입력
- 인자 1: board
number 타입의 2차원 배열
2 <= board.length <= 1,000
예: [ [0, 0, 1], [1, 0, 1], [1, 1, 1] ] - 인자 2: operation
string 타입의 대문자 영어가 쓰여진 문자열
1 <= operation.length <= board.length * 2
U, L, D, R 이외의 문자열은 없습니다.
출력
Number 타입을 반환해야 합니다.
board와 operation이 입력값의 예시 `([ [0, 0, 1], [1, 0, 1], [1, 1, 1] ], DDR)`일 때, (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) 순서로 이동하게 되고, 각 0, 1, 1, 1을 얻어 3을 반환합니다.
주의사항
만약, 말이 보드 밖으로 나갔다면 즉시 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.log(output2); // 'OUT'
const board3 = [
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 0]
]
const output3 = boardGame(board3, 'DDRRRUDUDUD');
console.log(output3); // 0문제풀이
function boardGame(board, operation) {
// u, d, l, r 경우를 정의하고 oper 하나씩 해보기
let result = 0;
let x = 0;
let y = 0;
for (let i = 0; i < operation.length; i++) {
if (operation[i] === 'U') {y--;}
if (operation[i] === 'D') {y++;}
if (operation[i] === 'L') {x--;}
if (operation[i] === 'R') {x++;}
if (y < 0 || x < 0 || y >= board.length || x >= board.length) return 'OUT'
result += board[y][x];
}
return result;
}
// u, d, l, r를 경우를 객체로 정의해서 사용할 수도 있다.
function boardGame(board, operation) {
const DIR = {
'U': [-1, 0],
'D': [1, 0],
'L': [0, -1],
'R': [0, 1]
}
const LEN = board.length;
// 좌표가 유효범위에 있는지 확인하는 함수
const isValid = (y, x) => 0 <= y && y < LEN && 0 <= x && x < LEN;
let Y = 0;
let X = 0;
let score = 0;
for (let i = 0; i < operation.length; i++) {
// x, y좌표에 더해줄 값을 구조분해할당으로 가져온다
const [dY, dX] = DIR[operation[i]];
Y += dY;
X += dX;
if (isValid(Y, X) === false) return 'OUT';
score += board[Y][X];
}
return score;
};
4. (Advanced) [DP] 금고를 털어라
자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산하기 시작합니다.
예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.
- $50 한 장을 훔친다
- $20 두 장, $10 한 장을 훔친다
- $20 한 장, $10 세 장을 훔친다
- $10 다섯 장을 훔친다
훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 target 을 훔칠 수 있는 방법의 수를 리턴하세요.
입력
- 인자 1: target
Number 타입의 100,000 이하의 자연수 - 인자 2: type
Number 타입을 요소로 갖는 100 이하의 자연수를 담은 배열
출력
Number 타입을 리턴해야 합니다.
조지가 target을 훔칠 수 있는 방법의 수를 숫자로 반환합니다.
주의사항
모든 화폐는 무한하게 있다고 가정합니다.
문제풀이
target 금액이 10원이고, 돈의 종류가 1, 2, 5원인 경우
먼저 1원으로 0부터 타겟인 10까지의 수를 만드는 경우의 수는 아래와 같다.
예를 들어 1원으로 5를 만든다면 1+1+1+1+1 한 가지 경우의 수밖에 없다.
0은 훔치지 못하는 경우의 수로 1이다.
그 다음 1원과 2원으로 0부터 10까지의 수를 만드는 경우의 수를 생각해보면,
0과 1은 2원보다 작으므로 1원으로만 만든 경우의 수와 동일 할 것이다.
1원과 2원으로 2를 만드는 경우의 수를 구하면
1원만으로 만든 경우의 수 + 2원을 사용해 만든 경우의 수 이다.
여기서 2원을 사용해 만드는 경우의 수를 다시 보면 2원이 하나는 꼭 포함되었다는 것이고 포함되는 2원 하나를 빼고 생각한다면 2 - 2 = 0 으로 1원과 2원을 사용해 0을 만드는 경우의 수와 같다.
즉, 1원과 2원으로 2를 만드는 경우의 수 = 1 + 1 인 것이다.
같은 방식으로 빈칸을 채워간다면 1원과 2원으로 10을 만드는 경우의 수는
1원으로 10만드는 경우의 수 + (10 - 2)를 만드는 경우 수이다.
5원 또한 같은 방식으로 생각하면
최종적으로 1원, 2원, 5원을 사용해 10을 만드는 경우의 수는 10이 된다.
function ocean(target, type) {
// bag 이라는 배열에 금액을 만들 수 있는 경우의 수를 기록
// 각 인덱스는 만드려는 금액 을 의미
// ex) target = 5, type = [1, 2, 5] 면
// bag[3] = 2 => 3원을 만드는 경우의 수 = 1만 사용 & 1,2 함께 사용 (1*3, 1 + 2)
// bag[4] = 3 => 4원을 만드는 경우의 수 = 1만 사용 & 1,2 함께 사용 (1*4, 1*2 + 2, 2*2)
// bag[5] = 4 => 5원을 만드는 경우의 수 = 1만 사용 & 1,2 함께 사용 &
// 1, 2, 5 함께 사용 (1*5 , 1*3 + 2, 1 + 2*2, 5*1)
// 0 을 만들 수 있는 경우는 아무것도 선택하지 않으면 되기 때문에 bag[0] = 1 로 초기값 설정
let bag = [1];
// 인덱스는 만드려는 금액 이기 때문에
// bag 을 target 금액만큼의 길이를 가진 배열을 만들어 주고,
// 경우의 수를 저장하기 위해 초기값은 모두 0으로 만들어 준다
for(let i = 1; i <= target; i++)
bag[i] = 0;
// 돈의 종류가 담겨있는 배열을 순차적으로 탐색
for(let i = 0; i < type.length; i++) {
// target 금액까지 순차적으로 1씩 증가하면서
for(let j = 1; j <= target; j++)
// bag의 인덱스가 type[i] 보다 큰 구간만
// (작은 구간은 type[i]로 만들 수 없는 금액이기 때문에 탐색할 필요가 없다)
// (더 큰 동전으로 바뀐다고 해도 작은 동전만으로 만든 경우의 수와 같기 때문)
if(type[i] <= j)
// 기존 경우의 수에 type[i]를 뺀 금액을 만들 수 있는 경우의 수를 더해준다
// 작은 동전으로 만든 경우의 수 + 큰동전과 작은동전 사용한 경우의 수로 경우의 수 갱신
bag[j] += bag[j-type[i]];
}
// bag 의 target 인덱스에 target 금액을 훔칠 수 있는 경우의 수가 쌓이므로
// 해당 값을 리턴해 준다
return bag[target];
}
// 재귀함수로 사용 가능하나 효율은 좀 더 떨어짐
function ocean(target, type) {
function oceanRecursive(target, type, index) {
// 종료 조건: target이 0인 경우, 1을 반환
if (target === 0) {
return 1;
}
// 종료 조건: target이 0보다 작거나, type 배열이 없는 경우, 0을 반환
if (target < 0 || index === type.length) {
return 0;
}
// 현재 인덱스에 해당하는 동전을 사용하지 않는 경우와 사용하는 경우를 모두 고려
const currentCoin = type[index];
const numWithoutCurrentCoin = oceanRecursive(target, type, index + 1);
const numWithCurrentCoin = oceanRecursive(target - currentCoin, type, index);
return numWithoutCurrentCoin + numWithCurrentCoin;
}
return oceanRecursive(target, type, 0);
}이 문제는 진짜 너무 어려웠다. 이해도 경우 했다ㅜ
출처
코드스테이츠 코플릿 알고리즘
'CS > 알고리즘' 카테고리의 다른 글
| 알고리즘 연습문제 (0) | 2023.04.08 |
|---|---|
| 빅오 표기법 (Big O Natation) (0) | 2023.03.28 |