흰연
2022. 1. 17. 19:36
2022. 1. 17. 19:36
목차
- 당장 좋은 것만 선택하는 그리디
- [실전문제] 큰 수의 법칙
- [실전문제] 숫자 카드 게임
- [실전문제] 1이 될 때까지
당장 좋은 것만 선택하는 그리디
- 그리디 알고리즘
- 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법 -> 최적의 해가 아닌 경우가 많다.
- 나중에 미칠 영향에 대해서는 고려하지 않는다.
- 그리디 알고리즘은 코딩테스트에서 정렬 알고리즘과 짝을 이뤄 출제되는 경우가 많다.
- 가장 큰 순서대로, 가장 작은 순서대로 등
- 거스름돈
- 500원, 100원, 50원, 10원 동전이 있을 경우 손님에게 거슬러줘야 하는 동전의 최소 개수
- 해결 방법 : 가장 큰 화폐 단위부터 돈을 거슬러 준다.
- 화폐의 종류만큼 반복 수행 -> 화폐의 종류가 K일 경우 -> 시간 복잡도 O(K)
- 큰 단위가 항상 작은 단위의 배수 형태이므로, 최적의 해를 보장 가능
- 코딩테스트 문제를 보고, 유형 파악이 어려울 경우 그리디 알고리즘으로 해결법을 찾아보고, 방법을 찾을 수 없으면 DP나 그래프 알고리즘 등으로 문제 해결 방법을 찾아본다.
실전문제 (1)
- 문제 요약
- 다양한 수로 이루어진 배열이 주어질 때 수들을 M번 더하여 가장 큰 수를 만든다.
- 특정한 인덱스가 연속 K번을 초과하면 안된다.
- 2, 4, 5, 4, 6으로 이루어진 배열일 경우 M이 8이고, K가 3일 경우
- 6 + 6 + 6 + (3연속X) 5 + 6 + 6 + 6 + (3연속X) + 5 = 46
- 3, 4, 3, 4, 3으로 이루어질 경우 4 + 4 + 4 + 4 + 4 + 4 가능
- 문제 해설
- 입력 값 중에서 가장 큰 수와 두 번째로 큰 수만 저장한다.
- 가장 큰 수를 K 번 더하고, 두 번째 큰 수를 한 번 더하는 연산 반복
- M의 크기가 100억처럼 커질 경우, 시간 초과
- 예시로 가장 큰 수 6, 두 번째로 큰 수 5, M이 8, K가 3이면 반복되는 수열이 존재한다 (6+6+6+5)*2
- 이러한 문제에서 가장 먼저 반복되는 수열에 대해서 파악하는 것이 중요
- 반복되는 수열의 길이 = K+1
- M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수
- 반복 횟수에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다.
<가장 큰 수가 더해지는 횟수> int (M / (K+1)) * K + M & (K+1)
실전 문제 (2)
- 문제 요약
- 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장 뽑기
- N X M 개의 카드
- 먼저 뽑으려는 카드가 포함된 행 선택
- 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드 뽑기
- 행을 선택할 때, 가장 숫자가 낮은 카드를 뽑는 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있는 전략 세우기
- 1, 2번째 행을 선택하는 경우 최종적으로 뽑는 카드 1
- 3번째 행을 선택하는 경우 최종적으로 뽑는 카드 2
- 따라서 세번째 행을 선택 후 숫자 2가 쓰인 카드를 뽑는 것이 정답
- 문제 해설
- 각 행마다 가장 작은 수를 찾은 뒤, 그 수 중에서 가장 큰 수를 찾는다.
Collections.max(list); // 리스트에서 최대 값을 출력
Collections.min(list); // 리스트에서 최소 값을 출력
실전 문제 (3)
- 문제 요약
- 어떤 수 N이 1이 될 때까지 아래의 과정 중 하나를 반복적으로 수행
- 두 번째 연산은 N이 K으로 나누어 떨어질 때만 선택 가능
- N에서 1을 뺀다.
- N을 K로 나눈다.
- N 17, K 4일 경우, 1번 과정 수행 시 N은 16
- 2번 과정을 두 번 수행 시 N은 1
- 결과적으로 전체 과정 실행 횟수 3
- 문제 해설
- 주어진 N에 대하여 '최대한 큰 수로 나누기'를 수행