🤔 알고리즘?
문제를 해결하는 최선의 선택
🤔 시간 복잡도
- 시간 복잡도는
최악의 경우를 고려하여 대비하기 위하여Big-o표기법을 사용한다. - 최악의 경우에 알고리즘이 얼마나 느려질 수 있는지를 나타내는 지표
Big-O 표기법 종류
- O(1): 입력 크기와 상관없이 일정한 시간이 소요되는 경우
- O(log n): 입력 크기가 커질수록 시간이 조금씩 더 소요되는 경우
- O(n): 입력 크기에 비례해서 시간이 소요되는 경우
- O(n log n): 입력 크기가 커질수록 시간이 더 빨리 소요되는 경우
- O(n^2): 입력 크기의 제곱에 비례해서 시간이 소요되는 경우
- O(2^n): 입력 크기의 지수에 비례해서 시간이 소요되는 경우
Greedy Algorithm
그리디 알고리즘 : 눈앞에 보이는 최적의 상황만 쫓아 해답에 도달하기.
Dynamic Programming(DP, 동적 계획법)
- 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결
- 하나의 문제는 단 한번 만 풀도록 하는 알고리즘
ex) 피보나치 수열
function fib(n) {
if(n <= 2) {
return 1;
};
return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...
function fibMemo(n, memo = []) {
// 이미 해결한 하위 문제인지 찾아본다
if(memo[n] !== undefined) {
return memo[n];
}
if(n <= 2) {
return 1;
}
// 없다면 재귀로 결괏값을 도출하여 res에 할당
let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo에 저장
memo[n] = res;
return res;
}04_[DP] 금고를 털어라
✅ 금고를 털어라
🖥️ 문제
- 자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산하기 시작합니다.
- 예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.
- $50 한 장을 훔친다
- $20 두 장, $10 한 장을 훔친다
- $20 한 장, $10 세 장을 훔친다
- $10 다섯 장을 훔친다
훔치고 싶은 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🔑 문제 접근 전 힌트
동전 교환 알고리즘 (Coin Change) : 어떤 금액을 동전으로 교환할 때, 필요한 동전의 최소 개수를 구하는 알고리즘
ex)
예를 들어, 100원을 교환할 때 10원, 50원, 100원 동전이 있다면 최소 1개의 100원 동전이 필요합니다.
만약 10원, 50원, 100원이 아니라 1원, 5원, 10원 동전만 있다면 10원짜리 10개가 필요하다!
- 보통 동적 계획법을 이용해 구현한다!
- 각 금액에 대한 최소 동전 개수를 저장하는 배열을 만들어 놓고, 이를 이용해 구하려는 금액까지의 최소 동전 개수를 구해나가는 방식으로 구현
예시 코드)
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity); // 각 금액의 최소 동전 개수를 저장할 배열, 초기값은 Infinity로 설정
dp[0] = 0; // 0원을 교환하는데 필요한 최소 동전 개수는 0개
for (let i = 1; i <= amount; i++) {
for (let j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount]; // 만약 교환할 수 없는 금액이면 -1을 반환, 아니면 해당 금액의 최소 동전 개수 반환
}
console.log(coinChange([1, 10, 50], 100)); // 2
🥹 문제 풀이
풀이 1
function ocean(target, types) {
const dp = Array(target + 1).fill(0); // 각 금액별 훔칠 수 있는 경우의 수를 저장할 배열
// 초기값 설정
dp[0] = 1;
for (let i = 0; i < types.length; i++) {
// 각 돈의 종류에 대해
for (let j = types[i]; j <= target; j++) {
// target 금액까지
dp[j] += dp[j - types[i]]; // 경우의 수 누적
}
}
return dp[target]; // target 금액을 훔칠 수 있는 경우의 수 반환
}레퍼런스 코드
function ocean(target, type) {
// bag 이라는 배열에 금액을 만들 수 있는 경우의 수를 기록
// 각 인덱스 no# = 만드려는 금액 을 의미
// 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];
// 인덱스 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];
}✅ 학습 내용
Array.prototype.fill() : fill() 메서드는 배열의 시작 인덱스부터 끝 인덱스의 이전까지 정적인 값 하나로 채웁니다.
arr.fill(value[, start[, end]])- value : 배열을 채울 값
- start (옵션) : 시작 인덱스 , 기본 값 0
- end (옵션) : 기본 값 this.length
ex)
const array1 = [1, 2, 3, 4];
// Fill with 0 from position 2 until position 4
console.log(array1.fill(0, 2, 4));
// Expected output: Array [1, 2, 0, 0]
// Fill with 5 from position 1
console.log(array1.fill(5, 1));
// Expected output: Array [1, 5, 5, 5]
console.log(array1.fill(6));
// Expected output: Array [6, 6, 6, 6]ex2)
[1, 2, 3].fill(4); // [4, 4, 4]
[1, 2, 3].fill(4, 1); // [1, 4, 4]
[1, 2, 3].fill(4, 1, 2); // [1, 4, 3]
[1, 2, 3].fill(4, 1, 1); // [1, 2, 3]위 에서 나열한 동전 교환 알고리즘에서 사용
const amount = 5;
const dp = new Array(amount + 1).fill(Infinity);
console.log(dp);
//[Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]풀이 코드에서 사용
let output = ocean(50, [10, 20, 50]);
console.log(output); // 4
const dp = Array(target + 1).fill(0); // 각 금액별 훔칠 수 있는 경우의 수를 저장할 배열
//target +1 만큼 0으로 채운 배열 생성
매일매일