🍊당장 좋은 것만 선택하는 그리디
- 현재의 상황에서 지금 당장좋은 것만 고르는 방법을 의미한다
- 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다
- 그리디 알고리즘은 다른 유형의 알고리즘과 비교했을 때 '사전에 외우고 있지 않아도 풀 가능성이 높은 문제 유형'으로 분류된다
- 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이다. 따라서 문제에서 '가장 큰(혹은 작은) 순서대로'와 같은 기준을 제시해준다
🍊예제 - 거스름돈
❓문제
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.
손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야할 동전의 최소 개수를 구하라.
단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
💡해설
가장 큰 화폐 단위부터 돈을 거슬러 준다
let n = 1260
let count = 0
// 큰 단위의 화폐부터 차례대로 확인
const coinTypes = [500, 100, 50, 10]
for (let i = 0; i < coinTypes.length; i++) {
// 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
count += Math.floor(n / coinTypes[i])
n %= coinTypes[i]
}
console.log(count)화폐의 종류만큼 반복한다
만약 화폐의 종류가 N개라 하면, 위 예제의 시간 복잡도는 O(N)이다
위 예제의 시간복잡도는 동전 종류 수에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다
🍊그리디 알고리즘의 정당성
- 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다
- 거스름돈 예제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이기 때문이다 ➡ 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다
만약 거스름돈 예제의 화폐 단위가 500원, 400원, 100원인데 800원을 거슬러 줘야 한다면❓
그리디 알고리즘으로 문제를 풀면 답은 4가 나온다 (500원 + 100원 + 100원 + 100원)
🔥하지만🔥
최적의 해는 2이다 (400원 + 400원) ➡ 이 경우, 다이나믹 프로그래밍으로 해결할 수 있다
(뒷 장에서 배움❗)
🍊정리
- 대부분의 그리디 알고리즘 문제는 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다
- 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘 의심❗
🍊실전문제
문제1. 큰 수의 법칙
❓문제
'큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다.
동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때, 주어진 수들은 M번 더하여 가장 큰 수를 만드는 법칙이다.
단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.
예를 들어, 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고 K가 3이라고 가정하자.
이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다.
단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.
예를 들어, 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때, M이 7이고 K가 2라고 가정하자.
이 경우 두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이 가능하다. 결과적으로 4 + 4 + 4 + 4 + 4 + 4 + 4인 28이 도출된다.
배열의 크기 N, 숫자가 더해지는 횟수 M 그리고 K가 주어질 때, 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.
✅입력예시
5 8 3
2 4 5 4 6
✅출력예시
46
🔥내 답안
🧩나의 접근법
입력된 배열 중에서 가장 큰 수와 그 다음으로 큰 수가 2가지만 사용된다
배열을 내림차순으로 정렬한 후 0번째와 1번째 수만 사용한다
연속해서 K번 밖에 더할 수 없기 때문에, 한 숫자가 몇 번 더해졌는지를 나타내는 변수 count가 필요하다
count의 값이 K와 같아질 때까지 입력된 배열 중에서 가장 큰 수를 K번 더한다
count의 값이 K보다 커지면 입력된 배열 중에서 2번째로 큰 수를 한 번만 더한다
그 후 다시 제일 큰 수를 K번 더하고, count의 값은 1로 초기화한다
<script>
function solution(arr) {
let answer = 0;
let count = 1;
const [m, k, input] = arr
input.sort((a, b) => b - a)
for (let i = 0; i < m; i++) {
if (count <= k) {
answer += input[0]
count++
} else {
answer += input[1]
count = 1
}
}
return answer;
}
// const arr = [8, 3, [2, 4, 5, 4, 6]]
const arr = [7, 2, [3, 4, 3, 4, 3]]
console.log(solution(arr));
</script>
💡답안
🔷방법 1🔷
입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다
연속으로 더할 수 있는 횟수는 최대 K번이므로,
가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산을 반복하면 된다
<script>
function solution(arr) {
let [n, m, k, data] = arr
// 입력받은 수들 오름차순으로 정렬하기
data.sort((a, b) => a - b)
const first = data[n - 1] // 가장 큰 수
const second = data[n - 2] // 두 번째로 큰 수
let result = 0
while (true) {
// 가장 큰 수를 K번 더하기
for (let i = 0; i < k; i++) {
if (m === 0) break // m이 0이라면 for문 탈출
result += first
m -= 1 // 더할 때마다 1씩 빼기
}
if (m === 0) break // m이 0이라면 while문 탈출
result += second // 두 번째로 큰 수를 한 번 더하기
m -= 1 // 더할 때마다 1씩 빼기
}
return result;
}
const arr = [5, 8, 3, [2, 4, 5, 4, 6]]
console.log(solution(arr));
</script>🔥하지만🔥
M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받을 것이다⏱
간단한 수학적 아이디어를 이용해서 더 효율적인 풀이를 도출할 수 있다
예를 들어, N은 5 M은 8 K는 3 입력값은 2 4 5 4 6 이라 가정해보자
이때 가장 큰 수는 6이고 두 번째로 큰 수는 5이다
(6 + 6 + 6 + 5) + (6 + 6 + 6 + 5) 로 더했을 때 합이 최대가 된다
이처럼 반복되는 수열을 파악하면 더 효율적인 풀이로 문제를 풀 수 있다
가장 큰 수와 두 번째로 큰 수가 더해질 때는 특정 수열 형태가 일정하게 반복해서 더해지는 특징이 있다
위의 예시에서는 수열 {6, 6, 6, 5}가 반복된다
따라서, 수열의 길이는 K + 1가 된다
수열이 반복되는 횟수는 M을 K + 1로 나눈 몫이 된다
다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다
만약 M이 K + 1로 나누어 떨어지지 않는 경우에는, M을 K + 1로 나눈 나머지만큼 가장 큰 수를 추가로 더하면 된다
Math.floor(M / (K + 1)) * K ➕ M % (K + 1)
🔷방법 2🔷
<script>
function solution(arr) {
let [n, m, k, data] = arr
// 입력받은 수들 오름차순으로 정렬하기
data.sort((a, b) => a - b)
const first = data[n - 1] // 가장 큰 수
const second = data[n - 2] // 두 번째로 큰 수
// 가장 큰 수가 더해지는 횟수 계산
let count = Math.floor(m / (k + 1)) * k
count += m % (k + 1)
let result = 0
result += count * first // 가장 큰 수 더하기
result += (m - count) * second // 두 번째로 큰 수 더하기
return result;
}
const arr = [5, 8, 3, [2, 4, 5, 4, 6]]
console.log(solution(arr));
</script>문제2. 숫자 카드 게임
❓문제
숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.
단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.
- 숫자가 쓰인 카드들이
N x M형태로 놓여 있다. 이때, N은 행의 개수를 M은 열의 개수를 의미한다.- 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
- 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
- 따라서 처음에 카드를 콜라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
예를 들어, 3 x 3 형태로 카드들이 다음과 같이 놓여 있다고 가정하자.
3 1 2
4 1 4
2 2 2
여기서 카드를 골라낼 행을 고를 때 첫 번째 혹은 두 번째 행을 선택하는 경우, 최종적으로 뽑는 카드는 1이다.
하지만, 세 번째 행을 선택하는 경우 최종적으로 뽑는 카드는 2이다.
따라서 이 예제에서는 세 번째 행을 선택하여 숫자 2가 쓰여진 카드를 뽑는 것이 정답이다.
카드들이 N x M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.
✅입력예시1
3 3
3 1 2
4 1 4
2 2 2
✅출력예시1
2
✅입력예시2
2 4
7 3 1 8
3 3 3 4
✅출력예시2
3
🔥내 답안
🧩나의 접근법
각 행에서 제일 작은 수들 중 제일 큰 수를 구하면 된다
각 행에서 제일 작은 수를 모두 구한다
각 행의 제일 작은 수들의 배열에서 제일 큰 수를 고른다
<script>
function solution(arr) {
let answer = [];
let row = arr[0]
for (let i = 2; i < row + 2; i++) {
answer.push(Math.min(...arr[i]))
}
return Math.max(...answer);
}
// const arr = [
// 3, 3,
// [3, 1, 2],
// [4, 1, 4],
// [2, 2, 2]
// ];
const arr = [
2, 4,
[7, 3, 1, 8],
[3, 3, 3, 4]
];
console.log(solution(arr));
</script>💡답안
각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는다
🔷방법 1🔷
min( ) 함수를 이용한 답안 예시
<script>
function solution(arr) {
const n = arr[0];
let answer = 0;
let min_value = 0;
for (let i = 2; i < n + 2; i++) {
// 한 줄씩 입력받아서 현재 주렝서 가장 작은 수 찾기
min_value = Math.min(...arr[i]);
// 가장 작은 수들 중에서 가장 큰 수 찾기
answer = Math.max(answer, min_value)
}
return answer;
}
// const arr = [
// 3, 3,
// [3, 1, 2],
// [4, 1, 4],
// [2, 2, 2]
// ];
const arr = [
2, 4,
[7, 3, 1, 8],
[3, 3, 3, 4]
];11
console.log(solution(arr));
</script>🔷방법 2🔷
이중 반복문을 이용하는 답안 예시
<script>
function solution(arr) {
const n = arr[0];
const m = arr[1];
let answer = 0;
let min_value = 0;
for (let i = 2; i < n + 2; i++) {
// 한 줄씩 입력 받는다
min_value = 10001
// 현재 줄에서 가장 작은 수 찾기
for (let j = 0; j < m; j++) {
min_value = Math.min(min_value, arr[i][j])
}
// 가장 작은 수들 중에서 가장 큰 수 찾기
answer = Math.max(answer, min_value)
}
return answer;
}
const arr = [
3, 3,
[3, 1, 2],
[4, 1, 4],
[2, 2, 2]
];
// const arr = [
// 2, 4,
// [7, 3, 1, 8],
// [3, 3, 3, 4]
// ];
console.log(solution(arr));
</script>
문제3. 1이 될 때까지
❓문제
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.
단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
N에서 1을 뺀다.N을K로 나눈다.
예를 들어, N이 17 K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다.
이후에 2번의 과정을 두 번 수행하면 N은 1이 된다.
결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다.
N과 K가 주어질 때, N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
✅입력예시
25 5
✅출력예시
2
🔥내 답안
🧩나의 접근법
최소 횟수를 구하기 위해서는 최대한 많이 나눈다
N의 값이 1이 되기 전까지 반복문을 수행하면서 연산한다
<script>
function solution(arr) {
let count = 0;
let [n, k] = arr
while (n !== 1) {
if (n % k === 0) {
n = n / k
} else {
n -= 1
}
count++
}
return count;
}
const arr = [25, 5]
console.log(solution(arr));
</script>💡답안
주어진 N에 대하여 최대한 많이 나누기를 수행하면 된다
'2이상의 수로 나누는 것'이 '1을 빼는 것'보다 숫자를 훨씬 더 많이 줄일 수 있다
다음의 과정을 반복할 수 없을 때까지 반복하면 정답을 구할 수 있다
N이K의 배수가 될 때까지 1씩 빼기N을K로 나누기
🔷방법 1🔷
단순하게 푸는 답안 예시
<script>
function solution(arr) {
let count = 0;
let [n, k] = arr
// N이 K이상이라면 K로 계속 나누기
while (n >= k) {
// N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
while(n % k != 0) {
n -= 1
count++
}
n /= k // K로 나누기
count++
}
// 마지막으로 남은 수에 대하여 1씩 빼기
// (K가 2 이상의 자연수이기 때문에 N의 값이 1이 아닌 2가 될 수도 있다)
while (n > 1) {
n -= 1
count++
}
return count;
}
const arr = [25, 5]
console.log(solution(arr));
</script>🔷방법 2🔷
N이 100억 이상의 큰 수가 되는 경우에도 빠르게 동작하기 위해서,
N이 K의 배수가 되도록 한 번에 빼는 방식을 사용한다
(이해가 잘 안간다...😥💦)
<script>
function solution(arr) {
let count = 0;
let [n, k] = arr
while (true) {
// N이 K로 나누어 떨어지는 수가 될 때까지 1씩 빼기
target = Math.floor(n / k) * k
count += (n - target)
n = target
// N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
if (n < k) break
n /= k // K로 나누기
count++
}
// 마지막으로 남은 수에 대하여 1씩 빼기
count += (n - 1)
return count;
}
const arr = [25, 4]
console.log(solution(arr));
</script>
