💡 KEY POINT 그리디 = 탐욕법 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘 유형은 매우 다양하기 때문에 암기한다고 항상 잘 풀 수 있는 것이 아님. 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로', ‘가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. → 이는 정렬 알고리즘과 같이 사용함
[실전 문제] 큰 수의 법칙
💡KEY POINT 입력받은 수의 배열에서 가장 큰 수를 K만큼 더하고, 두 번째로 작은 수를 한 번 더하는 방식의 반복.
1. 입력받은 수를 역순으로 정렬 2. M만큼 반복하면서 K만큼 가장 큰 수를 더함 3. K만큼 가장 큰 수를 더했다면, 두 번째로 작은 수를 한 번 더함
[실전 문제] 숫자 카드 게임
💡KEY POINT 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는다. 1 ≤ N, M ≤ 100 이므로 O(N^3)도 가능하다. 꼭 모든 수를 입력받아 저장시켜두고 사용할 필요는 없다. (입력받으면서 최소값을 찾아도 된다.)
1. 한 행의 수 목록을 입력받고 최소값을 찾는다. 2. 다음 행도 1번과 동일하게 진행하면서 이전 행의 최소값과 현재 행의 최소값 중 최대값을 찾는다. 3. 끝까지 마쳤을 때의 최대 숫자값을 출력한다.
[실전 문제] 1이 될 때까지
💡KEY POINT 1. N에서 1을 뺀다. 2. N을 K로 나눈다. 위와 같은 두 가지 연산 중 2번 연산이 가장 빠르게 숫자를 줄일 수 있는 방법이다. 따라서 되도록 2번 연산을 수행하되, 나누어 떨어지지 않을 때만 1번 연산을 진행한다.
1. N이 1이 될 때까지 반복한다. 2. K로 나눌 수 있는지 판단한다. 3. 가능하면 K로 나누는 2번 연산을, 불가능하면 1을 빼는 1번 연산을 수행한다.
Tip.) 여러번 계속 연산을 수행할 수 있는지 확인하면서 진행하는 것보다, N이 K의 배수가 되는 가장 큰 수일 때를 찾고 한번에 나눈 후에 나머지를 한번에 빼는 것이 더 빠르다.