🔎 그리디
탐욕법, 욕심쟁이 알고리즘 => 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘
- 탐욕적: '현재 상황에서 지금 당장 좋은 것만 고르는 방법'
매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려 X
✏️ 예제
📝 거스름돈
카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재, 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수는? (단, 거슬러 줘야 할 돈 N은 항상 10의 배수)
문제 해설
그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제
아이디어 = '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것
📍 그리디 알고리즘의 정당성
대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해' 찾을 수 없을 가능성 높음
But, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장 있다면 매우 효과적이고 직관적!
그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 함
거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유
=> 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있음
🔑 포인트
-
특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지 파악할 수 있어야 함!
-
문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해줌 (그리디 = 기준에 따라 좋은 것을 선택하는 알고리즘이므로)
-
정렬 알고리즘과 짝을 이뤄 출제되는 경우가 많음
-
어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형 파악하기 어렵다면 그리디 알고리즘을 의심해보고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자
✏️ 실전 문제
📝 큰 수의 법칙
다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙 (단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수는 없으며 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주함)
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 위에서 설명한 큰수의 법칙에 따른 결과를 출력하시오
- 입력 조건
- 첫째 줄에 N, M, K의 자연수가 주어지며, 각 자연수는 공백으로 구분함 (2 ≤ N ≤ 1,000), (1 ≤ M ≤10,000), (1 ≤ K ≤ 10,000)
- 둘째 줄에 N개의 자연수가 주어짐, 각 자연수는 공백으로 구분함 (각각 1 이상 10,000 이하의 수)
- 입력으로 주어지는 K는 항상 M보다 작거나 같음 - 출력 조건
- 첫째 줄에 위에서 설명한 큰 수의 법칙에 따라 더해진 답을 출력함
문제 해설
전형적인 그리디 알고리즘 문제, 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 됨
연속으로 더할 수 있는 횟수는 최대 K번이므로 '가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산' 반복
반복되는 수열에 대해서 파악
소스코드
📝 숫자 카드 게임
여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임 (단, 아래의 게임의 룰을 지키며 카드 뽑아야 함)
1. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있음 (N은 행의 개수, M은 열의 개수 의미)
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택함
3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 함
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 함
카드들이 N x M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오
- 입력 조건
- 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어짐 (1 ≤ N, M ≤ 100)
- 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어짐, 각 숫자는 1 이상 10,000 이하의 자연수 - 출력 조건
- 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자들을 출력함
문제 해설
'각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수'를 찾는 것이 이 문제를 푸는 아이디어
소스코드
📝 1이 될 때까지
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 함 (단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있음)
1. N에서 1을 뺌
2. N을 K로 나눔
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오
- 입력 조건
- 첫째 줄에 N(2 ≤ N ≤ 100,000)과 K(2 ≤ K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어짐, 이때 입력으로 주어지는 N은 항상 K보다 크거나 같음 - 출력 조건
- 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력함
문제 해설
주어진 N에 대하여 '최대한 많이 나누기'를 수행하면 됨
어떠한 수가 있을 때, '2 이상의 수로 나누는 것'이 '1을 빼는 것'보다 숫자를 훨씬 많이 줄일 수 있기 때문
소스코드
📒 이것이 코딩 테스트다 교재를 통해 학습한 내용을 정리하였습니다.
