그리디 알고리즘
그리디 알고리즘
당장 좋은 것만 선택하는 알고리즘
그리디 알고리즘은 전체적으로 최적의 해를 보장하지는 못하지만, 그 순간에 대해서는 최적인 알고리즘이다. 따라서 각 단계의 선택이 최종적인 결과에 미치는 영향을 고려하지 않고 진행된다.
실전문제
이코테-그리디 알고리즘에는 3문제가 수록되어있는데 모두 어렵지 않게 해결할 수 있었다.
문제의 목적만 잘 파악하면 코드를 짜는 것은 시간문제였다.
코드를 짤 때 자잘하게 필요한 기본기들을 정리해볼 수 있었다.
1. 큰 수의 법칙
리스트를 입력받고 그 리스트의 요소들을 이용하여 M번 더하여 가장 큰 수를 만들어내는 알고리즘이다. 단, 같은 요소를 K번까지 밖에 연속적으로 사용하지 못한다.
나의 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
N, M, K = map(int, input().split())
problem_input = input()
result = 0
count = 0
arr = list(map(int, problem_input.split()))
arr.sort(reverse=True) # 오름차순 정렬
while count < M: # M번 횟수 제한
for j in range(K): # 같은 요소 더하는 횟수, K번 제한
if count < M:
result += arr[0]
count += 1
else:
break
if count < M:
result += arr[1]
count += 1
print(result)
사실상, 필요한 숫자는 가장 큰 숫자와 2번째로 큰 숫자이므로, 오름차순 정렬해주고 0번째와 1번째 요소를 이용하여 주어진 조건에 맞춰서 더해주기만 하면 된다.
입출력 예시
1
2
3
5 8 3
2 4 5 4 6
46 // 출력
2. 숫자 카드 게임
문제
2개 이상의 행들 중에 하나를 뽑고, 그 행에 포함된 숫자들 중 가장 낮은 숫자를 뽑았을 때, 최종적으로 가장 높은 숫자를 뽑을 수 있도록 하는 전략이다.
1
2
3
4
5
6
7
8
9
10
N,M = map(int, input().split()) # N(행), M(열)의 개수 입력받기
arr = []
for i in range(N):
arr_input = list(map(int, input().split())) # i번째 행의 요소들을 입력받고
arr_input.sort() # 내림차순 정렬하고
arr.append(arr_input[0]) # 가장 낮은 값을 arr에 저장하기
print(max(arr)) # arr에서 가장 큰 값을 출력
2차원 배열이 떠오르는 문제이지만, 문제에서 원하는 것들을 코드로 짜주기만 하면 된다. 직접 2차원 배열을 짜지않아도, 각 행의 요소들 중 가장 작은 값만 뽑아내면 되기 때문에 2차원 배열을 쓰지 않았다. 2차원 배열을 쓰면 각 행의 0번째 요소들을 비교하여 가장 큰 값을 뽑아내는 과정에서 코드가 더 복잡해지므로, 이렇게 짜는 것이 더 그리디스러운 풀이인 것 같다.
입출력 예시
1
2
3
4
5
3 3
3 1 2
4 1 4
2 2 2
2 // 출력
3. 1이 될 때까지
문제
- N에서 1을 뺀다.
- N에서 K를 나눈다.
이 두가지를 이용해서 N을 1로 만들 때까지의 최소 횟수를 구하는 문제이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
N,K = map(int, input().split())
count = 0
while N != 1:
if N % K == 0:
N = N // K
count += 1
else:
N -= 1
count += 1
print(count)
나누는게 1을 빼는 것보다 먼저가 되어야 횟수가 줄어드니까 나누는 것을 우선적으로 확인해준다.
입출력 예시
1
2
25 5
2 // 출력
깨달은 것 정리
N, M, K = map(int, input().split())
map(함수, 적용할 객체) 이걸 이용하면 입력받으면서 바로 정수형으로 바꿀 수 있다.
arr_input = list(map(int, input().split()))
배열을 입력받을 경우, 앞에 list만 추가해주면 된다. list를 안쓰고 괜히 append()를 이용해보려고 했다가 오류가 떴다.
그리디 알고리즘은 깔끔한 전략를 짜는 것이 아니라, 그냥 원하는 것을 얻어내기만 하면 되는 마인드를 가지고 코드를 짜면 되는 것 같다. 마음을 열고 문제를 받아들이는 마음가짐을 가져야겠다.