📦 Greedy : 짐 나르기
박스를 최대한 적게 사용해 모든 짐을 옮기려고 할 때, 짐의 무게를 담은 배열 stuff와 박스의 무게 제한인 limit가 매개변수로 주어질 때 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 반환하는 함수를 작성하라.
(박스에는 최대 2개의 짐 밖에 넣을 수 없고, 무게 제한이 있다. )
예를 들어, 짐의 무게가 70kg, 50kg, 80kg, 50kg이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다.
//내가 작성했던 (틀린) 수도코드
//stuff 배열을 내림차순으로 정렬한다.
//박스 개수를 세는 변수인 box를 정의하고 0을 할당한다.(초기값)
//sum이라는 변수를 선언한다. (물건 무게를 계산할 때 사용할 변수)
//stuff의 요소 개수만큼 반복문을 돌린다.
//stuff[i]의 요소를 sum에 넣는다.
//그 다음 차례(stuff[i+1])에서 sum + stuff[i+1]의 합이 limit보다 큰지 비교한다.
//만약 크다면 sum에는 suftt[i+1]을 할당하고, box 변수에 +1 해준다.
//만약 limit값과 같다면 sum을 0으로 변경하고, box 변수에 +1 해준다.
//만약 limit값보다 작다면 다음 차례로 넘어간다. (근데 마지막 요소인 경우 box + 1 해주어야 함.)
//반복문을 마친다.
//box 값을 반환한다. 위 수도코드의 문제점은 아래와 같다
1.박스에는 두 개의 물건만 담을 수 있다는 조건 간과
2.제일 무거운 것과 제일 작은 것을 합쳤을 때 함께 옮길 수 있는 경우가 있을 수 있음 간과
//래퍼런스 참고해서 작성한 코드
//: 가장 무거운 것 - 가장 가벼운 것 부터 짝을 지어 박스에 담을 수 있는지 확인한다.
function movingStuff(stuff, limit) {
let sorted = stuff.sort((a,b)=>a-b);//오름차순으로 정렬함
let twoStuffSum = 0;//2개의 짐 짝지을 수 있는 경우의 수 카운트
let minIdx = 0;
let maxIdx = sorted.length-1;
//작은 인덱스가 큰 인덱스보다 작은 동안 반복문을 돌린다.
while(minIdx < maxIdx){
if(sorted[minIdx]+sorted[maxIdx] <= limit){
twoStuffSum++;
minIdx++
maxIdx--
}else{
maxIdx--
}
}
return sorted.length - twoStuffSum
}👩🔧 Greedy : 편의점 알바
현재 가지고 있는 동전은 1원, 5원, 10원, 50원, 100원, 500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있다. 동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성하라.
//내가 작성한 수도 코드
// coins = [500,100,50,10,5,1] 배열을 만든다.
//동전 개수를 셀 변수 count를 만든다.
//coins의 개수만큼 반복문을 돌린다. (if (k===0) break;)
//반복문 내부 :
//count 변수에 거스름돈을 차례가 된 동전 요소를 나눈 몫을(버림) 할당
// 거스름돈에는 해당 요소로 나누고 남은 나머지를 할당한다
//반복문이 끝나면 count를 리턴한다. function partTimeJob(k) {
const coins = [500,100,50,10,5,1];
let count = 0;
for(let i=0;i<coins.length;i++){
if(k===0)break;
count += Math.floor(k/coins[i]);
k%=coins[i];
}
return count;
}
✋ 구현 : 보드 게임
N * N의 크기를 가진 보드판 위에서 게임을 한다.
게임의 룰은 아래와 같다.
보드판이 담긴 board와 조작하려고 하는 문자열 operation이 주어질 때, 말이 해당 칸을 지나가면서 획득한 숫자의 합을 구하는 함수를 작성하라.
- 좌표 왼쪽 상단(0, 0)에 말을 놓는다.
- 말은 상, 하, 좌, 우로 이동할 수 있고, 플레이어가 조작할 수 있다.
- 조작의 기회는 딱 한 번 주어진다.
- 조작할 때 U, D, L, R은 각각 상, 하, 좌, 우를 의미하며 한 줄에 띄어쓰기 없이 써야 한다.(예시: UDDLLRRDRR, RRRRR)
5.한 번 움직일 때마다 한 칸씩 움직이게 되며, 그 칸 안의 요소인 숫자를 획득할 수 있다.
6.방문한 곳을 또 방문해도 숫자를 획득할 수 있다.
7.보드 밖을 나간 말은 OUT 처리가 된다.
8.칸 안의 숫자는 0 또는 1이다. 단, 좌표 왼쪽 상단(0, 0)은 항상 0이다.- 획득한 숫자를 합산하여 숫자가 제일 큰 사람이 이기게 된다.
//내가 짠 수도코드
//현재 위치를 기억하는 position 변수를 만들어서 [0,0] 배열을 할당한다.
//board의 밖으로 나갔는지 확인 위한 변수 limit = [board.length, board[0].length]
//지나간 자리들의 숫자들의 합을 계산하는 변수 만듦. sum = 0;
//operation의 길이만큼 반복문을 돌린다.
//반복문 내부에서는 operation[i]의 값이 U/D/L/R일 때마다 각각 행동이 달라진다.
//U일 때, position 에서 0번째 인덱스 값을 -1 한다.
//D일 때, position의 0번째 인덱스 값을 +1한다.
//L일 때, position의 1번째 인덱스 값을 -1한다.
//R일 때, position의 1번째 인덱스 값을 +1한다.
// 반복문의 한 차례가 끝날 때마다 position 밖으로 나왔는지 확인해야 하는데,
//limit의 0번째와 position의 0번째가 동일하거나 or 1번째와 1번째가 동일하면 OUT을 리턴한다.
//OUT이 아니라면 sum = sum + board[position[0]][position[1]]
//반복문이 끝나면 sum을 리턴한다.function boardGame(board, operation) {
const position = [0,0]
const limit = [board.length-1, board[0].length-1]
let sum = 0;
for(let i=0; i<operation.length;i++){
if(operation[i] === 'U'){
position[0] = position[0]-1;
}else if(operation[i] === 'D'){
position[0] = position[0] + 1;
}else if(operation[i]=== 'L'){
position[1] = position[1] - 1;
}else if(operation[i]==='R'){
position[1] = position[1] + 1;
}
if(position[0] < 0 || position[1] < 0 || limit[0] < position[0] || limit[1] < position[1] ){
return 'OUT';
}else{
sum = sum + board[position[0]][position[1]]
}
}
return sum;
};👮 DP : 금고를 털어라 (Advanced)
훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, target 을 훔칠 수 있는 방법의 수를 반환하는 함수를 작성하라. (모든 화폐가 무한히 있다고 가정함)
예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.
$50 한 장을 훔친다
$20 두 장, $10 한 장을 훔친다
$20 한 장, $10 세 장을 훔친다
$10 다섯 장을 훔친다
해당 문제를 풀기 위한 힌트로 '동전 교환 알고리즘(Coin Change)'를 활용하면 된다고 되어 있어서 구글링을 해보다 이분의 블로그를 보고 작성해보았다.
일단 동전 교환 알고리즘에 대해서 이해하는 게 필요한데, 아래 표를 보게 되면 아래 래퍼런스 코드들이 왜 그런 방식으로 경우의 수를 구하고 있는지 이해할 수 있다.
세로축은 사용할 돈의 종류 (type)을 나타내고 있고,
가로축은 만들고자 하는 금액(target)에 대해서 나타내고 있다.
첫번째 줄은 1원으로 만들 수 있는 x원의 경우의 수를 나타내는데,
예를 들어 1원,2원,5원 각각이 0원을 만드는 경우의 수는 언제나 1가지이다.
그리고 1원을 가지고 1원부터 10원까지 만드는 경우의 수는 언제나 1가지이므로 1원의 줄은 1로 채워진다.
다음으로 넘어가서 2원으로 각 금액을 만들 때,
2원보다 적은 금액은 2원으로 만들 수 없으므로 1원의 경우의 수와 동일하다.
(2원의 줄에서 구하는 것은 1원과 2원의 조합으로 만들 수 있는 x원의 경우의 수라는 점을 주의해야 한다.
2원 하나만 가지고 금액을 만드는 것이 아님)
2원부터는 1원으로 2원을 만들 수 있는 경우의 수 1과 2원으로 0을 만들 수 있는 경우의 수 1을 더하게 되는데,
해당 경우의 수를 찾을 때
'바로 위쪽의 경우의 수'와
'만들고자 하는 금액에서 사용하고 있는 금액권(type)을 뺀 금액을 만드는 경우의 수(2원으로 0(=2-2)을 만드는 경우의 수'
를 합한 값이 해당 경우의 수가 되기 때문이다.
| 0 1 2 3 4 5 6 7 8 9 10
---|----------------------
1 | 1 1 1 1 1 1 1 1 1 1 1
2 | 1 1 2 2 3 3 4 4 5 5 6
5 | 1 1 2 2 3 4 5 6 7 8 10 사실 위 매커니즘이 정확하게 왜???? 그런 거냐고 묻는다면 답하기 힘들겠지만... 이런 방식으로 경우의 수를 구할 수 있다는 점을 잘 활용하면 여러가지 문제들을 해결할 수 있을 거 같다고 생각했다.
//이 코드는 위에 참조해둔 블로그를 참고해 작성했던 코드임.
function ocean(target, type) {
// 동적 계획법은 주어진 문제를 여러 개의 작은(하위)문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합해 최종 문제를 해결함.
//처음에 재귀적인 방식으로 푸려고 했는데, 재귀는 실행 시간이 초과되었음.
// const change = (i, sum) => {
// if (sum < 0 || i < 0) return 0;
// if (sum === 0) return 1
//더 작은 금액권으로 target 금액을 만들어서 더해준다.
// return change(i - 1, sum) + change(i, sum - type[i]);
// }
// return change(type.length - 1, target)
//시간 복잡도를 충족하려면 메모이제이션 방식으로 풀어야 함.
//memo라는 변수에는 Array.from 매서드를 이용해 배열을 할당해주는데
//이 배열은 type배열의 길이*(target+1)의 2차원 배열을 만들어주고, 배열에는 -1로 가득차있는 형태...
const memo = Array.from(Array(type.length),el => Array(target + 1).fill(-1))
const change = (i, sum) => {
if (sum < 0 || i < 0) return 0;
if (sum === 0) return 1;
if (memo[i][sum] !== -1) return memo[i][sum];
return memo[i][sum] = change(i - 1, sum) + change(i, sum - type[i]);
}
return change(type.length - 1, target)
}아래는 래퍼런스 코드이다.
// 래퍼런스
function ocean(target, type) {
// bag 이라는 배열에 금액을 만들 수 있는 경우의 수를 기록
// 각 인덱스 no# = 만드려는 금액 을 의미
// ex) target = 5, type = [1, 2, 5] 면
// bag[3] = 2 => 3을 만드는 경우의 수 = 1만 사용 & 1,2 함께 사용
// bag[4] = 2 => 4를 만드는 경우의 수 = 1만 사용 & 1,2 함께 사용
// bag[5] = 4 => 5를 만드는 경우의 수 = 1*5 , 1*3 + 2, 1 + 2*2, 5*1
// 0 을 만들 수 있는 경우는 아무것도 선택하지 않으면 되기 때문에 bag[0] = 1 로 초기값 설정
let bag = [1];
// 인덱스 no# = 만드려는 금액 이기 때문에
// 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) {
//bag의 0번째 요소는 1로 고정
//훔칠 수 없는 경우의 수도 1개라고 생각한다
let bag = [1];
//target+1 길이의 배열을 만들어준다.(bag)
//target+1 길이의 배열을 만드는 이유는 만들 수 없는 경우도 고려하기 위함. (0원을 만드는 경우의 수를 고려하기 위함)
for (let i = 1; i < target + 1; i++) {
bag[i] = 0;
} //[1, 0, 0, 0, 0, 0, 0, 0, 0]
//type의 종류별로
for (let i = 0; i < type.length; i++) {
//bag을 순회하면서(이중 for 문)
for (let j = 0; j < bag.length; j++) {
//j가 type[i]보다 크거나 같을 경우, j = 2, type[i] = 1
if (j >= type[i]) {
// bag[j]의 값을 "bag[j]+bag[j-type[i]]"로 바꿔준다.
//bag[2] = bag[2] + bag[2 - 1] = bag[2] + bag[1]
bag[j] = bag[j] + bag[j - type[i]];
}
}
}
//for문이 끝난 후 bag[target]을 리턴해준다.
return bag[target];
}
키보드로 그려내는 일