- ๊ณจ๋ ๋๋น ์ฝ๋ฉ ํ ์คํธ ํฉ๊ฒฉ์ ๋๊ธฐ ํ์ด์ฌ ํธ์ 15์ฅ ์จ๋จธ๋ฆฌ๊ฐ ํฌํจ๋์ด ์์ต๋๋ค.
- ๋ง์ง๋ง ์ฑํฐ์ด๋ค. ๊ฐ์ด ์คํฐ๋ํ ๋ฉค๋ฒ๋ค๊ณผ ํ์ฅ๋๊ป ๊ณ ๋ง์ด ์ธ์ฌ๋ฅผ ์ฌ๋ฆฐ๋ค.
- ๋ฌธ์ ๋ถํฐ ํ๋ฉด์ greedy์ ์ต์ํด ์ง๋ ๊ฒ์ด ๋ชฉํ์ด๋ค.
๋ชธํ๊ธฐ ๋ฌธ์
๊ฑฐ์ค๋ฆ๋ ์ฃผ๊ธฐ
๊ฑฐ์ค๋ฆ๋ amount๊ฐ ์์ ๋ ํํ๋จ์ [1,10,50,100] ์ ์ต์ํ์ ์ฌ์ฉํ ํํ๋ฆฌ์คํธ๋ฅผ ๋ฐํํ๋ solution() ํจ์๋ฅผ ๋ฐํํ์ธ์. ์ ์ฝ์กฐ๊ฑด
- ๋ฐํํ๋ ๊ฐ์ ํํ๋จ์๋ ๋ด๋ฆผ์ฐจ์
ํํ๋จ์๋ฅผ ์ต์ํ์ผ๋ก ์ฌ์ฉํ๊ธฐ ์ํด์ , ํฐ ๋จ์์ ํํ๋ฅผ ์ด์ฉํ์ฌ ๊ฑฐ์ค๋ฆ๋์ ์ค๋ค.
์ค๋ฆ์ฐจ์ ์ ๋ ฌ ๋ถ๋ถ์ ์๊ฐ ๋ณต์ก๋๊ฐ ๊ฐ์ฅ ๋์ผ๋ฏ๋ก O(N)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
function change_coin(amount){
const answer = [];
const changes = [1, 10, 50, 100]
changes.sort((a,b)=> b-a)
for(const c of changes){
const count = Math.floor(amount/c);
amount = amount % c;
for(let i=0; i<count; i++){
answer.push(c)
}
}
return answer
}
console.log(change_coin(123))
console.log(change_coin(350))
๋ถ๋ถ ๋ฐฐ๋ญ ๋ฌธ์
๋ฌธ์ ์ค๋ช ๋ฌด๊ฒ์ ๊ฐ์น๊ฐ ์๋ ์ง items์ ๋ฐฐ๋ญ weight_limit์ด ์ฃผ์ด์ง ๋, ๋ถ๋ถ ๋ฐฐ๋ญ๋ฌธ์ ๋ฅผ ํธ๋ solutionํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์. ์ ์ฝ์กฐ๊ฑด 1<=
weight_limit
<=10,000 1<=items.length<=1,000
- ์ฃผ์ด์ง ๋ฌด๊ฒ ์ ํ์ ์ด๊ณผํ์ง ์์ผ๋ฉด์ ๊ฐ์น๊ฐ ์ต๋๊ฐ ๋๋๋ก ๋ฌผ๊ฑด์ ๋ฃ๋ ๋ฌธ์
- ๊ฐ ๋ฌผ๊ฑด์ ๋ฌด๊ฒ์ ๊ฐ์น๋ก ํํ๋๋ค.
- ๋ฌผ๊ฑด์ ์ชผ๊ฐค ์ ์์ผ๋ฏ๋ก ๋ฌผ๊ฑด์ ์ผ๋ถ๋ถ์ด ๋ด๊ธธ ์ ์๋ค.
- ์๊ฐ๋ณต์ก๋๋ ์ ๋ ฌ๋ก ์ธํด O(nlogn) ์ด ๋๋ค.
function fractional_knapsack(items, limit) {
let total_v = 0;
// ๋ฌด๊ฒ๋น ๊ฐ์น ๊ณ์ฐ
items.forEach((item) => item.push(item[1] / item[0]));
// ๋ฌด๊ฒ๋น ๊ฐ์น๋ก ๋ด๋ฆผ์ฐจ์ ์ ๋ ฌ
items.sort((a, b) => b[2] - a[2]);
for (const [w, v, _v] of items) {
if (w <= limit) {
total_v += v;
limit -= w;
} else {
total_v += _v * limit;
break;
}
}
return Math.round(total_v * 100) / 100;
}
console.log(
fractional_knapsack(
[
[10, 19],
[7, 10],
[6, 10],
],
15,
),
); //27.33
console.log(
fractional_knapsack(
[
[10, 60],
[20, 100],
[30, 120],
],
50,
),
); //240
์์ฐ ๋ฌธ์ ์ถ์ฒ: ํ๋ก๊ทธ๋๋จธ์ค
๋ฌธ์ ์ค๋ช ๋ถ์๋ณ๋ก ์ ์ฒญํ ๊ธ์ก์ด ๋ค์ด์๋ ๋ฐฐ์ด d์ ์์ฐ budget์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ต๋ ๋ช ๊ฐ์ ๋ถ์์ ๋ฌผํ์ ์ง์ํ ์ ์๋์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ d๋ ๋ถ์๋ณ๋ก ์ ์ฒญํ ๊ธ์ก์ด ๋ค์ด์๋ ๋ฐฐ์ด์ด๋ฉฐ, ๊ธธ์ด(์ ์ฒด ๋ถ์์ ๊ฐ์)๋ 1 ์ด์ 100 ์ดํ์ ๋๋ค. d์ ๊ฐ ์์๋ ๋ถ์๋ณ๋ก ์ ์ฒญํ ๊ธ์ก์ ๋ํ๋ด๋ฉฐ, ๋ถ์๋ณ ์ ์ฒญ ๊ธ์ก์ 1 ์ด์ 100,000 ์ดํ์ ์์ฐ์์ ๋๋ค. budget์ ์์ฐ์ ๋ํ๋ด๋ฉฐ, 1 ์ด์ 10,000,000 ์ดํ์ ์์ฐ์์ ๋๋ค.
- ์ต๋ ๋ง์ ๋ถ์์ ๋ฌผํ ์ง์์ ํ๊ธฐ ์ํด์ ์ ๊ฒ ์์ฒญํ ์์ฐ ์์ผ๋ก ๋จผ์ ๊ณ์ฐํ๋ค.
- ์์ฐ์ด ๋จ์์๋ ๋์ ์์ฒญํ ์์ฐ์ ๋ํจ
- ํ์ฌ ์ฌ์ฉํ ์์ฐ์ด ์ฃผ์ด์ง ์์ฐ ๋ณด๋ค ์์ผ๋ฉด ๋ถ์์ ์++
- ํ์ฌ ์ฌ์ฉํ ์์ฐ์ด ์ฃผ์ด์ง ์์ฐ ๋ณด๋ค ํฌ๋ฉด ์ข ๋ฃํ๋ค.
- ์๊ฐ๋ณต์ก๋ O(nlogn)
function solution(d, budget) {
return d
.sort((a, b) => a - b)
.reduce((cnt, b) => {
return (cnt += (budget -= b) >= 0);
}, 0);
}
console.log(solution([1, 3, 2, 5, 4], 9)); //3
console.log(solution([2, 2, 3, 3], 10)); //4
๊ตฌ๋ช ๋ณดํธ ๋ฌธ์ ์ถ์ฒ: ํ๋ก๊ทธ๋๋จธ์ค
- ์ฌ์ด๋ฏ ํ๋ฉด์๋ ๋ธ๋ฃจํธํฌ์ค๋ก ์ ๊ทผ ํ ๋ ์ด๋ป๊ฒ ํ๋ฉด 2๋ช ์ weight์ ๊ฐ์ฅ ๊ฐ๊น๊ฒ ์ฑ์์ ๊ตฌํํ๊ธฐ ์ํด ํ์ํ ์ ๋ต์ด ์ฝ๊ฒ ๋ ์ค๋ฅด์ง ์์๋ค.
- ํฌํฌ์ธํฐ๋ฅผ ์ด์ฉํ ํ์ด๋ก ์ต๋ 2๋ช ์ด๊ณ , limit์ ์ต๋ํ ๊ฐ๊น๊ฒ ๋ง๋ค๊ธฐ ๊ฐ์ฅ ๋ฌด๊ฑฐ์ด ์ฌ๋๊ณผ ๊ฐ์ฅ ๊ฐ๋ฒผ์ด ์ฌ๋์ ๊ฐ์ด ํ์ด๋ค.
function solution(people, limit) {
var answer = 0;
let left = 0;
let right = people.length-1;
people.sort((a,b)=>a-b)
//ํฌํฌ์ธํฐ
while(left<right){
// ๋๋ช
์ด ๊ฐ์ด ํ ์ ์๋ ์กฐ๊ฑด : ๋์ ํฉ์ด limit๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์์ผํจ
// ๊ฐ์ด ํ ์ ์์ผ๋ฉด left์ right๋ฅผ ํ์นธ์ฉ ์ฎ๊ฒจ์ค
if(people[left] + people[right] <= limit){
answer+=1
left+=1;
right-=1;
}else{
//๊ฐ์ด ํ ์ ์๋ ๊ฒฝ์ฐ : limit์ ๋๋ ๊ฒฝ์ฐ
// ๋ ์์ ์ฌ๋์ ํ์์ผ ํจ .
// right๋ฅผ ์ฎ๊ธฐ๋ฉด์, ํฐ ์ฌ๋์ ํผ์ ํ๊ฒ ํจ
right-=1;
answer+=1
}
}
// ๋ง์ง๋ง ๋จ์ ํ๋ช
ํ์ฐ๊ธฐ
if(left===right){
answer+=1
}
return answer
}
console.log(solution([70, 50, 80, 50],100)) //3
console.log(solution([70, 80, 50],100)) //3
๊ทค๊ณ ๋ฅด๊ธฐ ๋ฌธ์ ์ถ์ฒ: ํ๋ก๊ทธ๋๋จธ์ค
๋ฌธ์ ์ค๋ช ๊ฒฝํ๊ฐ ํ ์์์ ๋ด์ผ๋ ค๋ ๊ทค์ ๊ฐ์ k์ ๊ทค์ ํฌ๊ธฐ๋ฅผ ๋ด์ ๋ฐฐ์ด tangerine์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋๋ค. ๊ฒฝํ๊ฐ ๊ทค k๊ฐ๋ฅผ ๊ณ ๋ฅผ ๋ ํฌ๊ธฐ๊ฐ ์๋ก ๋ค๋ฅธ ์ข ๋ฅ์ ์์ ์ต์๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. 1 โค k โค tangerine์ ๊ธธ์ด โค 100,000 1 โค tangerine์ ์์ โค 10,000,000
- ์ข ๋ฅ์ ์๋ฅผ ์ต์ํ ํ๊ธฐ ์ํด์ ๋ง์ ๊ฐ์๋ฅผ ๊ฐ์ง ์ข ๋ฅ ๋ถํฐ ์ ํ ํ๋ค.
function solution(k, tangerine) {
let cnt =0;
// mapper
const mapper = {}
//๊ทค์ ์ข
๋ฅ๋ณ๋ก ๊ฐ์ ์ธ๊ธฐ
tangerine.forEach((t)=> mapper[t]=(mapper[t]||0)+1)
// sort ๋ด๋ฆผ์ฐจ์ - ์ข
๋ฅ์ ์๋ฅผ ์ต์ํํ๊ธฐ ์ํด ๋ง์ ๊ฐ์๋ฅผ ๊ฐ์ง ์ข
๋ฅ๋ถํฐ ์ ํํ๊ธฐ ์ํด
const sortedMapper =Object.entries(mapper).sort((a,b)=>b[1]- a[1])
// loopํ๋ฉด์
for (const [_, t] of sortedMapper){
k-=t // ๊ทค ๋ด๊ธฐ
cnt+=1 // ์ข
๋ฅ ์ ์ฆ๊ฐ
if(k<=0) break // ๊ทค ๋ค ๋ด์์ผ๋ฉด ์ข
๋ฃ
}
return cnt;
}
console.log(solution(5, [3, 1, 4, 1, 5])) //3
console.log(solution(6, [1, 3, 2, 5, 4, 5, 2, 3])) //3