[알고리즘 대비 - 이코테] 2. 그리디

탐욕 알고리즘(Greedy Algorithm)

• 미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식

When?

• 탐욕 알고리즘 이외의 알고리즘이 매우 느린 경우 사용한다.
• 탐욕 알고리즘이 최적의 답을 보장해주는 경우 사용한다.

 

최적 부분 구조(Optimal Substructure)

: 부분 문제들의 최적의 답을 이용하여 기존 문제의 최적의 답을 구할 수 있다는 것

부분 문제를 만들 수 있으며 부분 문제의 최적화된 값이 전체 결과까지 최적화된 값을 주는가?

 

 

탐욕적 선택 속성(Greedy Choice Property)

: 각 단계에서 탐욕스런 선택이 최종 답을 구하기 위한 최적의 선택

당장의 상황에서 목표를 위해 가장 도움이 되는 것이라고 할만한 것을 고를 수 있는가?

 

💡 최적 부분 구조와 탐욕적 선택 속성이 있는 경우 탐욕 알고리즘이 최적의 선택이 된다.

💡 두 속성은 분리될 수 있으며 둘 중 하나만 충족하는 경우도 있다.

 

 

⭐가장 큰 순서대로 또는 가장 작은 순서대로 와 같이 문제에서 기준을 제시해주는 경우

→ 정렬 알고리즘과 그리디 알고리즘을 적용해본다!

---

Q1. 거스름돈

• 가장 큰 화폐단위부터 돈을 거슬러준다.

그리디 알고리즘의 정당성

• 그리디 알고리즘으로 문제를 풀었다고 해도 해당 풀이가 항상 최적의 해를 보장하는지 따져봐야한다.
• 가지고 있는 동전 중 큰 단위의 동전이 항상 작은 동전의 배수이므로 다른 해가 나올 수 없다.

---

Q2. 큰 수의 법칙

문제 설명

배열의 크기 N, 숫자가 더해지는 횟수 M, 연속해서 더할 수 있는 최대값 K가 주어질 때, 큰 수의 법칙에 따라 더해진 답을 출력하시오.

큰 수의 법칙 : 입력된 배열에서 특정 인덱스의 수를 최대 K번 반복하여 더할 수 있고 K번 초과하여 더하면 안된다.

예) N = 5, M = 8, K = 3
주어진 배열 : [2, 4, 5, 4, 6]
최대값 : 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46

입력 조건

• 첫째 줄에 N(2 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건

• 첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

풀이

TRY 1

💯 반복 구조의 경우 규칙을 찾아내면 풀이 과정을 더 단축 시킬 수 있다!

from sys import stdin

a = list(map(int, stdin.readline().split())) # a[0] : N, a[1] : M, a[2] : K
b = list(map(int, stdin.readline().split()))
b.sort(reverse=True) # 입력받은 숫자 정렬
cnt = a[2]
answer = 0
for _ in range(a[1]): # M번 연산 진행
    if cnt == 0:
        cnt = a[2]
        answer += b[1]
    else:
        answer += b[0]
        cnt -= 1

print(answer)

• 해당 문제에선 배열의 가장 큰 값 2개만을 가지고 답을 도출할 수 있다.
• 가장 큰 값을 K번(연속해서 더할 수 있는 최대값) 더하면 해당 값을 더는 더할 수 없으므로 두 번째 큰 값을 더한다.
• 두 번째 큰 값을 더하고 나서는 다시 연속으로 더할 수 있는 횟수를 초기화 시켜준다.

cnt = a[2] # 기존 K값으로 돌려놓음

 

TRY 2

💡 가장 큰 수와 두 번째 큰 수는 더해질 때 특정한 수열 형태로 일정하게 반복된다.

→ 해당 반복 구조는 굳이 반복문을 쓰지않고 구현할 수 있다.

from sys import stdin

a = list(map(int, stdin.readline().split()))
b = list(map(int, stdin.readline().split()))
b.sort(reverse=True)

# 1. 가장 큰 수가 더해지는 횟수로 cnt 정하기
cnt = (a[1] // (a[2]+1)) * a[2] + (a[1] % (a[2]+1))

# 2. 두번째 큰 수가 더해지는 횟수로 cnt 정하기
# cnt2 = a[1] // (a[2]+1)
answer = (cnt * b[0]) + (a[1] - cnt) * b[1]

print(answer)

방법 1️⃣

• 부분 수열의 길이는 K + 1
• ∵ 가장 큰 수 K번 반복 (K) + 두 번째 큰 수 (1)
• 부분 수열의 반복 횟수에서 K번 더하므로 a[1] // (a[2]+1)) * a[2] .
• 나머지 부분도 더한다. a[1] % (a[2]+1)

방법 2️⃣

• 두번째 큰 수는 k+1의 부분 수열의 개수만큼 더해진다.

---

Q3. 숫자 카드 게임

문제 설명

1. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 굿자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

입력 조건

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 ≤ N, M ≤ 100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

출력 조건

• 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

풀이

💯 카드 행렬을 리스트에 담는 과정과 최댓값을 비교하는 과정을 하나의 반복문 내에 넣으면 더욱 깔끔하게 코드를 짤 수 있다.

from sys import stdin

N, _ = map(int, stdin.readline().split())
card, rst = [], 1
# 카드 배열을 리스트 card에 담는다.
for _ in range(N):
    card.append(list(map(int, stdin.readline().split())))
# 입력된 카드의 행을 비교하며 가장 큰 값을 찾는다.
for i in card:
    if rst < min(i):
        rst = min(i)
print(rst)

• _ 은 해당 위치에 들어갈 변수를 따로 사용하지 않을 때 사용한다.
• 각 행 마다 가장 작은 값 탐색 :

min(i) # 이때 i는 리스트 형태이다.​

• 그 수 중에서 가장 큰 수 탐색 :

rst < min(i) # 큰 값을 찾을 경우 값을 갱신한다.​

Q4. 1이 될 때까지

문제 설명

어떠한 수 N이 1이 될 떄까지 다음의 두 과정 중 하나를 바녹적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

입력 조건

• 첫째 줄에 N(2≤ N ≤ 100,000)과 K(2 ≤ K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력 조건

• 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

풀이

from sys import stdin

N, K = map(int, stdin.readline().split())
cnt = 0
while N > 1:
    if N % K == 0:N //= K
    else:N -= 1
    cnt += 1
print(cnt)

• 최대한 많이 나누는 것이 최적의 해를 보장하므로 if 문의 조건으로 N을 K로 나눌 수 있는 경우, N을 나누도록 조건 지정
• N을 K로 나눌 수 없는 경우, 단순 -1 연산 수행

 

728x90

---

 

해당 포스팅의 내용은

저)나동빈님의 『이것이 취업을 위한 코딩 테스트다 with 파이썬』을

통해 공부한 내용을 토대로 작성하였습니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬

저자 | 나동빈

출판 | 한빛미디어

발매 | 2020.08.05.