greedy : 이코테 강의 정리

Greedy 알고리즘 (탐욕법)

현재 상황에서 지금 당장 좋은 것만 선택하는 방법
문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있어야 함
그리디로 최적의 해를 구할 수 있는지 정당성도 검토해야 함
ex. 단순히 매 순간 가장 큰 값만 고른다고 tot가 최대일 수 있는지? -> no

예제. 가장 적은 동전 개수로 돈 거슬러주기

큰 단위부터 거슬러주는 것이 최적의 해를 보장한다

1. money=800, coin=500,100

가장 큰 화폐 단위부터 돈을 거슬러주면 된다

2. money=800, coin=500,400,100

가장 큰 화폐 단위부터 거슬러주면 500+100*3 이지만 실제로 최적의 해는 400*2이다

• 시간복잡도= 화폐의 개수(동전의 종류) O(K)

예제. 1이 될 때까지

빼기, 나누기가 가능할 때 최대한 많이 나누는 것이 최적의 해를 보장한다.

#나의 코드
n,k=map(int,input().split())
cnt=0

# 매번 n의 값을 확인해야 하므로 시간복잡도가 높다
while(True):
    if n==1:
        break
    if n%k==0:
        n/=k
        cnt+=1
    else:
        n-=1
        cnt+=1
print(cnt)

#모범답안
#log시간복잡도를 갖는 코드
n,k=map(int,input().split())
result=0

while(True):
    #n이 k로 나누어 떨어질때까지 빼기
    #n=25, k=3인 경우,
    #target=(25//3)*3=24
    target=(n//k)*k
    #result=1 (-하는 횟수)
    result+=(n-target)
    #n=24 ...반복
    n=target

    #더이상 나눌 수 없을때(n<k) 반복문 탈출
    if n<k:
        break
    # k로 나누기
    result+=1
    n//=k

# 마지막으로남은 수에 대하여 1씩 빼기
result+=(n-1)
print(result)

• 그리디 문제 만나면 위처럼 푸는 연습! 매번 초기값을 확인하지 않는 쪽으로

예제. 곱하기 혹은 더하기

앞뒤의 수가 0이나 1이 아닐 경우에는 모두 곱하는 것이 최적의 해를 보장한다

#나의 코드
s=list(map(int,input()))
tot=s[0]

#앞뒤 수 중 하나라도 0 or 1인지 확인하고 맞다면 더하기, 아니면 곱하기
for i in range(len(s)-1):
    if s[i]==0 or s[i]==1 or s[i+1]==0 or s[i+1]==1:
        tot+=s[i+1]
    else:
        tot*=s[i+1]
print(tot)

# 모범답안
s=list(map(int,input()))
res=s[0]

for i in range(1,len(s)):
    num=s[i]
    if num<=1 or res<=1:
        res+=num
    else:
        res*=num
print(res)

예제. 모험가

한 그룹의 인원은 max(공포도)만큼의 인원수를 가져야 하므로 최대한의 그룹을 만들기 위해서는 공포도가 적은 사람부터 그룹을 결성해야 한다.

n=int(input())
#공포도 오름차순 정렬
p=sorted(list(map(int,input().split())))

#공포도 작은 애부터 그룹 결성

result=0 #총 그룹의 수
cnt=0 #현재 그룹에 포함된 모험가의 수

for i in p: #한명씩 확인하며
    cnt+=1 #현재 그룹에 해당 모험가를 포함
    
    if cnt>=i: #현재 그룹에 포함된 모험가 수>현재 공포도, 그룹결성
        result+=1 #결성되었으니 그룹 수 증가
        cnt=0 #cnt 초기화하고 다시 시작
print(result)

후기

그리디 문제는 아이디어 자체는 떠올리기 어렵지 않을 것 같은데 코드로 구현하기가 어려웠다. 특히 지금까지는 그리디 문제를 구현으로 풀다보니 대충 리스트에 append하고 len(list)으로 개수룰 세는 노가다를 해왔기 때문에 새롭게 느껴졌던것 같다. 결론은,.연습

문제 그대로 구현하기보다는 필요한 부분만 변수로 설정해서 구하는 연습을 해야겠다

참고 : 이코테 해설 강의