이코테 그리디 알고리즘
그리디 알고리즘은 그대로 번역되어 탐욕법으로 소개된다. 이름에서 알 수 있는데 지금 당장 좋은 것만 고르는 방법을 의미한다.
그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓기 대문에, 다익스트라 알고리즘과 같은 특이 케이슬를 제외하고는 단순 암기를 통해 모든 문제를 대체하기는 어렵다.
그리디 알고리즘 유형의 문제는 매우 다양하기 때문에 암기한다고 해서 항상 잘 풀 수 있는 것은 아니다. 많은 유형을 접해보고 문제를 풀어봐야한다. 보통 코테에서는 창의력, 즉 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
내 벨로그 첫 게시물이다. 훗날 내가 개발자가 되었을 때, 이렇게라도 군대에서 하길 잘했다라고 생각했음 좋겠다
1.예제 3-1 거스름돈
나의 코드)
N=int(input())
arr1 = [500,100,50,10]
cnt =0
for i in range(0,len(arr1)):
cnt += N // arr1[i]
N = N % arr1[i]
print(cnt)comment) 이것만 할만 한 것 같다.
책 코드)
N=int(input())
arr1 = [500,100,50,10]
cnt =0
for i in arr1:
cnt += N // i
N %= i
print(cnt)시간복잡도 O(k) -> 동전의 개수에만 영향을 받는다
그리디 알고리즘의 정당성
그리디 알고리즘을 모든 문제에 적용할 수는 없다. 대부분의 문제는 그리디 알고리즘을 이용할때 최적의해를 찾을 수 없을 가능성이 많다. 하지만 이 문제와 같이, 탐욕적으로 접근했을 대 정확한 답을 얻을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.
그런데 이 문제에서는 주어진 동전이 서로 배수 관계여서 가능한 것이다. 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 대문이다.
ex)500, 400, 100으로 800원을 만들 때 400원 두 개를 쓰는게 최적이다.
대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
- 실전문제 - 큰수의 법칙 p.92
나의 코드)
n,m,k = map(int,input().split())
data = list(map(int,input().split()))
data.sort()
mx1 = data[n-1]
mx2 = data[n-2]
count=0
result =0
order1 =m+1//k
order2 =m%k
if order1%2 == 0:
if m//2k >= 1:
m1=m//2k
for i in range(0,m1):
result += mx1*k
result += mx2*k
result+=comment) 하... 다시 한번 느꼈다. 난 진짜 ㅈ밥인 것 같다. 군인이여서 그런가 뇌가 굳은건가.. 연등은 2시간이기 때문에 내일 한번 더 복습하는 것으로 하고 답을 봤다.
책코드)
#입력받기
n,m,k = map(int,input().split())
data = list(map(int,input().split()))
#정렬
data.sort()
#큰수와 그다음수
mx1 = data[n-1]
mx2 = data[n-2]
result = 0
while True:
#가장 큰 수 k번 더하기
for i in range(k):
#m이 0이면 반복문 탈출
if m ==0:
break
result += mx1
m-=1 #더할때 마다 1씩 차감
#m이 0이면 반복문 탈출
if m ==0:
break
result += mx2 #두번째 수 한번만 더하기
m-=1 #더할때 마다 1씩 차감
print(result)
바보 같았다. 왜 mx1을 k번 더한 후에 mx2도 k번 더해야 한다고 생각했을까...
mx2는 한번만 더해줘도 연속수는 초기화 되는데... 이건 내가 멍청한 것 같다.
코딩하면서 주석을 달아서 정리하는 법도 알아야할 것 같다. 난이도 '하'라고 하던데 개발자로 취직하기는 틀려먹은 것 같다.
M이 10000이하라 위의 코드로 문제를 해결할 수 있지만 M의 크기가 100억처럼 커지면 시간초과가 될 것이다. 수학적 아이디어를 얻어야한다.
수학적 아이디어)
반복되는 수열을 파악해야한다. 가장 큰 수와 두 번째로 큰 수가 더해질 때는 k+1의 길이를 가진 수열이 반복된다. 예를들어 k=3 이라면 가장 큰 수가 3번 더해지고 두 번째 큰 수가 1번 더해진다. 그럼 총 4번의 합이 반복된다. 그럼 우리는 큰 수와 작은 수가 몇번 더해지는지 파악하면 문제를 해결할 수 있다.
(M//K+1)K 만약 M/K+1이 나누어 떨어지지 않는다면 M%K+1을 더해 줘야한다.
그럼 총 가장 큰 수를 더하는 횟수는 (M//K+1)K + M%K+1 이다.
두 번째 큰 수를 더하는 횟수는 총 횟수 M에서 위의 공식을 빼주면 될 것이다.
수학적 코드)
#입력받기
n,m,k = map(int,input().split())
data = list(map(int,input().split()))
#정렬
data.sort()
#큰수와 그다음수
mx1 = data[n-1]
mx2 = data[n-2]
result = 0
#횟수 구하기
count = (m//(k+1))*k
count += m%(k+1)
result = 0
result += mx1 * count
result += mx2 * (m-count)
print(result)
comment) 약간 펜으로 공식을 최적의 로드를 생각해보면서 풀어보는 연습을 가져야할 것 같다. 나의 코드는 아마 저런방식으로 풀려고 했을 것이다. 꾸준한 복습이 필요할 것 같다.
- 실전문제 - 숫자 카드 게임 p.96
나의 코드)
# n,m 입력받기
n, m = map(int,input().split())
arr_result = []
# 반복문을 통해서 리스트로 입력 받기
for i in range(0,n):
arr_mx = list(map(int, input().split()))
# 각 줄마다 정렬하여 작은 원소를 arr_result에 대입
arr_mx.sort()
arr_result.append(arr_mx[0])
arr_result.sort()
# 각 줄의 가장 작은 원소 중 작은 원소
result = arr_result[-1]
print(result)comment) 이 문제는 예상외로 빨리 풀었다. 그리디는 탐욕법 그대로 문제를 빨리 이해하고 그 문제에 타당한 해결법을 직관적으로 찾아내는 것이 중요한것 같다.
책 코드 min() 이용)
# n,m 입력받기
n, m = map(int,input().split())
result =0
# 반복문을 통해서 리스트로 입력 받기
for i in range(0,n):
data = list(map(int, input().split()))
# 현재 줄에서 가장 작은 수 찾기
min_value = min(data)
# 작은 수중 가장 큰 수 찾기
result = max(result,min_value)
print(result)책 코드 2중 반복문 이용)
# n,m 입력받기
n, m = map(int,input().split())
result =0
# 반복문을 통해서 리스트로 입력 받기
for i in range(0,n):
data = list(map(int, input().split()))
min_value = 10001
for a in data:
min_value = min(a, min_value)
# 작은 수중 가장 큰 수 찾기
result = max(result,min_value)
print(result)comment) 시간을 한번 측정해보았다.
나의 코드)
min()코드)
2중 for문 코드)
min()을 이용한 코드는 정말 간결한 것 같다. 나는 최솟값을 구하기 위해서 리스트를 정렬하였다. 그럴 필요없이 최솟값을 저장하면서 하면 더 빠를 것이라 생각했지만 내코드가 제일 빠르다... 왜? 그런거지..ㅋㅋㅋㅋㅋㅋ 빨리 다음문제나 풀고 코드 복습하자..
복습하면서 느낀 것인데 min,max를 변수이름으로 사용하지말자
TypeError: 'int' object is not callable 오류 뜬다
4.실전문제 - 1이 될 때까지 p.99
나의 코드)
import math
import time
start = time.time()
# n, k 입력 받기
n,k = map(int,input().split())
result = 0
# 1을 빼야할 횟수
remain = n%k
# data는 k로 나누어 떨어진다
data = n - remain
# 반복문을 통하여 data 1로 만들기
while True:
data /= k
result += 1 # 횟수 더해주기
# data가 1이라면 stop
if data == 1:
break
# 총 횟수 산출
result += remain
print(result)
comment) 오 이것도 조금 빨리 풀었던 것 같다. 사실 책 사기전에 유튜브로 해설을 조금 본게 도움이 된 것 같다. 이 문제의 핵심은 1을 만들기라는 점에서 -1과 나누기 k 라는 도구가 있는데, 최소의 횟수로 1을 만들려면 2이상으로 주어지는 k로 나누기를 택하는 것이 최소 횟수로 만들 수 있다는 것을 알 수 있다.
책의 코드)
import math
import time
start = time.time()
# n, k 입력 받기
n,k = map(int,input().split())
result = 0
while n>=k:
while n%k !=0:
n-=1
result +=1
n//=k
result +=1
# 마지막으로 남은 수에 대하여 1씩 빼기
while n>1:
n-=1
result +=1
print(result)
end = time.time()
print(f"{end - start:.5f} sec")
comment) 흠 마지막으로 남은 수에 대하여 1씩 빼는 부분이 이해가 가지 않는다.
혹시몰라서 그런건가..? 위에 n>=k 일때 반복문이 적용 된다. 위에서 n이 k로 나누어 떨어지게끔 만들어진다. 그러면 결국 마지막은 n=1이 되지 않나..? 라고 생각한다. 책 해설의 마지막에서는 엄청 큰 수를 가지고 왔을 때, 나처럼 한번에 빼고 한번에 나누는 방식이 더 효율적이라고 한다. 실제로 time을 돌려봤을 때, 내코드가 살짝 빨랐다....나는 바보였다. 쓰면서 깨달았다. 예로 25 3이라면 24/3=8이다
즉 8은 3으로 나누어 떨어지지 않는다. 그것을 고려를 안한 것 같다. 다시 짜야 겠다. 나중에 이불킥 일듯
책의 코드 -한번에 하기)
# n, k 입력 받기
n,k = map(int,input().split())
result = 0
while True:
target = (n//k)*k
result += n - target
n = target
if n < k:
break
result +=1
n//=k
result += (n-1)
print(result)comment) 첫 번째 코드는 2중 반복문이라 n이 커지면 시간이 오래걸릴 것이다
두 번째 코드로 빨리 풀 수 있을 것 같다.
이상 chapter 그리디는 끝났다
느낀점은 더욱더 연습을 해야한다는 것이다.... 문제를 보자마자 직관적으로 해결책을 찾고 타당한지 제한사항과 비교하면서 풀어야하는 능력을 키워야한다. 왤케 바보인가 복습하자 대학교 어떻게 갔는지 모르겠다. 근데 재밌어서 좋았다
복습)
복습 1번
- 코드는 쓸 때마다 달라지지만 최적의 방법으로 한번에 해결완료
복습 2번
