개념
- 탐욕법
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다
- 다익스트라 알고리즘 - 엄밀히 말하면 그리디 알고리즘으로 분류
- 암기가 필요 없음
- 해법이 정당한지 검증이 필요
그리디와 정렬 알고리즘과 짝을 이뤄 자주 출제됨
❓문제를 만났는데 바로 문제 유형을 파악할 수 없는 경우
- 그리디 알고리즘을 의심하고 해법을 고민
- 그리디로 해결할 수 없다면 → 다이나믹 프로그래밍이나 그래프 알고리즘으로 해결할 수 있는지 고민
예제 3-1 거스름돈
const COIN_TYPES = [500,100,50,10];
let n = 1260;
let cnt = 0;
for(const coin of COIN_TYPES) {
cnt += Math.floor(n/coin);
n %= coin;
}
console.log(cnt);실전문제
큰 수의 법칙
배열의 크기 N, 숫자가 더해지는 횟수 M, 연속가능한 횟수 K
1. 입력 : 입력 조건의 모든 값이 자연수이므로, 숫자로 타입을 변환해야한다
let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let [num,arr] = input;
let [n,m,k] = num.split(' ').map(v=>+v);
arr = arr.split(' ').map(v=>+v);.trim() : 문자열 양 끝의 공백을 제거하고 원본 문자열을 수정하지 않고 새로운 문자열을 반환 // 생략해도 결과 도출됨
input의 두줄을 num, arr로 받고
n, m, k 에 num 묶음을 split으로 분리해 map으로 각 변수에 할당
arr 배열에 split으로 분리해 각 배열 칸 마다 숫자 할당
*자바스크립트의 배열 할당 표현식 : 구조분해할당*
방법 1. `while`로 단순 풀이 → `O(m)`
function solution(n, m, k, arr){
arr.sort((a, b) => b - a);
const first = arr[0];
const second = arr[1];
let result = 0;
while(1){
if(m === 0) break;
result += first * k;
m -= k;
result += second;
m--;
}
return result;
}
console.log(solution(n, m, k, arr));`.sort()` : 정렬 메소드. `b-a`는 내림차순
m에서 덧셈 진행할 시 한번씩 빼면서 실행
*k 로 연속 가능한 횟수만큼 반복시킴
방법 2. for문 사용
function solution(n, m, k, arr){
arr.sort((a, b) => b - a);
const first = arr[0];
const second = arr[1];
let result = 0;
for(let i = 0, tmp = 0; i < m; i++){
if(tmp === k){
result += second;
tmp = 0;
} else{
result += first;
tmp++;
}
}
return result;
}tmp 로 횟수 측정, i로 횟수 제한
방법 3. 수학 식 (반복되는 순열) → `O(1)`
function solution(n, m, k, arr){
arr.sort((a, b) => b - a);
const first = arr[0];
const second = arr[1];
//가장 큰 수가 더해지는 횟수
let count = Math.floor((m / (k + 1)) * k);
count += m % (k + 1);
let result = 0;
result += count * first;
result += (m - count) * second;
return result;
}
console.log(solution(n, m, k, arr));수열 패턴이 반복되는 횟수 `(m / (k + 1)) * k`
남은 나머지(m % (k + 1)) 만큼은 가장 큰 수가 추가로 더한다
가장 큰 수와 두 번째로 큰 수를 곱하여 각각의 횟수에 맞게 더한다
예를들어, n=5, m=8, k=3일때
count = Math.floor((8 / (3 + 1)) * 3) + (8 % (3 + 1))
= Math.floor((8 / 4) * 3) + (8 % 4)
= Math.floor(2 * 3) + 0
= 6따라서, 가장 큰 수 6이 6번 더해지고, 두 번째로 큰 수 5가 2번`(m-count)` 더해지게 된다.
result = (6 * 6) + (2 * 5) = 36 + 10 = 46
숫자카드게임 → `O(nm)`
가장 높은 숫자자가 쓰인 카드 한 장. N 행 x M 열
1. 행을 선택 후 행에서 가장 낮은 카드 선택
-> 각 행의 가장 낮은 숫자 중 가장 큰 수 선택
let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let [nm, ...arr] = input;
let [n, m] = nm.split(' ').map(v => +v);
arr = arr.map(v => v.split(' ').map(v => +v));
function solution(n, m, arr){
let result = 0;
for(const cur of arr){
result = Math.max(result, Math.min(...cur))
}
return result;
}
console.log(solution(n,m,arr));`arr.map(v=>v.split(' ').map(v=>+v));` : 2차원 입력받기. 첫번째 map으로 배열의 각 요소에 대해 주어진 함수를 호출하고, 그 함수의 반환값으로 새로운 arr배열을 생성한다. 각 요소가 문자열 이므로, split으로 분리하고, map으로 숫자로 변환한다.
❓`arr = arr.split(' ').map(v=>+v);` 와 다른 점? 해당 변환 과정을 한번 더 map으로 묵어주는 형식! 즉 이 과정을 통해 1차원 배열이 2차원 배열로 입력 변환하는 방법
배열의 현재 행 `cur`로 for 문 탐색
- 예를들어, arr이 [[1, 2, 3], [4, 5, 6], [7, 8, 9]]와 같은 2차원 배열이라고 하면, 첫 번째 반복에서 cur은 [1, 2, 3]을 가리키고, 두 번째 반복에서는 [4, 5, 6]을 가리키고, 세 번째 반복에서는 [7, 8, 9]를 가리키게 된다.
cur 행에서 최소값을 찾고 Math.min() 메소드
그 중 max 값을 result에 할당하며 비교한다.
즉, 각 행별로 가장 작은 수의 원소를 찾은 후, 그 중에서 가장 큰 값을 구한다.
1이 될 때까지
어떤 수 n이 1이 될때까지 두 과정 중 하나 반복
1. n-1
2. n/k (단, 나누어떨어질때만 가능)
1, 2를 수행하는 최소 횟수 구하기
방법 1. 단순풀이 → `O(n)`
n이 10만 이하일때만 가능하다.
let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();
let [n,k] = input.split(' ').map(v => +v);
function solution(n, k){
let cnt = 0;
while(n > 1){
n % k === 0? n /= k : n--;
// if(n % k === 0){
// n /= k;
// } else{
// n--;
// }
cnt++;
}
return cnt;
}
console.log(solution(n, k));1. n이 1보다 큰 동안 반복한다. n이 1보다 작거나 같아질 때까지 반복한다.
2. if 문으로 n을 k로 나눌 수 있는 경우와, 그렇지 않는 경우로 분기한다. 그렇지 않는 경우 n을 감소시켜서 1에 가깝게 줄임.
3. cnt로 연산 횟수 측정한다.
방법 2. 한번에 빼기
function solution(n,k){
let cnt = 0;
while(true){
let target = Math.floor(n/k)*k;
cnt += n-target;
n = target;
if(n < k)
break;
n = n/k;
cnt++;
}
cnt= cnt+(n-1);
return cnt;
}
console.log(solution(n,k));연산과정
1. target : 현재의 n을 k로 나눌 수 있을 만큼 나눈 후, 그 몫에 k를 곱한 값 할당 -> n을 k의 배수로!
2. n이 k의 배수로 만들기 위해 뺀 나머지 연산 횟수를 더한다
3. n을 k의 배수로 만들었으므로 n에 target 값을 할당
4. 무한루프 종류문. 더이상 작으면 나눌 수 없다.
5. n을 k로 나누고, 이를 반복할 수 있는 만큼의 연산 횟수를 누적한다.
6. 남은 수에 대해 1만들기 위해 n-1번 더 빼줘야하는거 세기