그리디 알고리즘

경주마같은, 상남자 같은 문제라고 생각하면 개념이 쉽다. 

 

문제에서 생각했던 것처럼, 

동전으로 값을 맞출때 가장 큰 금액부터 넣으면 되는 경우 이다 .

 

가장 큰 값의 동전부터 , 지금 최선인 것부터 일단 진행하는 것이다. 

 

어떻게 최적의 해가 될 수 있을까?

 

당연히, 당상 최적이 항상 전체의 최적은 아니다 .

 

선택의 조건 ?

 

1. 현재 선택이 이후 선택에 영향을 주지 않는다. 

a->b->c로 갈때, a->b로 어떤 비용으로 가든, b->c로 가는데 영향을 주지 않는다

 

2. 부분의 최적해를 모으면 전체의 최적이 된다.

a->c까지의 최적해는, a->b+b->c의 최적이된다. 

 

백준 11047

import sys

N,K = map(int,sys.stdin.readline().split())

coinlist = []

for i in range (N) :
    coinlist.append(int(sys.stdin.readline()))

coinlist.sort(reverse= True)

start = 0
cnt = 0
while K>0 :

    if coinlist[start]<=K :
       K = K- coinlist[start]
       cnt += 1
       continue
    else :
        start+=1
        continue

print(cnt)

시간 초과가 나왔다. 

아마 k를 계속 계산해서 그런 것이라 추측된다. 

 

import sys

N,K = map(int,sys.stdin.readline().split())

coinlist = []

for i in range (N) :
    coinlist.append(int(sys.stdin.readline()))

coinlist.sort(reverse= True)

start = 0
cnt = 0
while K>0 :

    if coinlist[start]<=K :
        cnt = cnt + K // coinlist[start]
        K = K % coinlist[start]
        continue
    else :
        start+=1
        continue

print(cnt)

나머지와 몫을 활용하여 , 연산 수를 크게 줄였다. 

 

<값을 채울때는, 그리디 알고리즘이 성립했다> (물론 경우에 따라 다름)

 

백준 11399

import sys

N= int(sys.stdin.readline())

Nlist = [0] +list(map(int,sys.stdin.readline().split()))

Nlist.sort()

dp = [0] * (N+1)

for i in range(1,N+1) :
    dp[i] = dp[i-1]+Nlist[i]

print(sum(dp))
    

dp를 활용해서 쉽게 풀었다.

 

<일단은 손으로, 이 문제가 그리디인지를 파악하는 것이 중요하다>

 

백준 1931번

어떠한 방식으로 풀지 먼저 고민하였다. 

 

1. 수업시간이 가장 짧은 강의부터 풀자. 

이렇게 작성하였다. 허나 문제가 발생했다.

 

(두개를 뽑을 수 있는데 하나만 뽑아야 하는 경우가 발생했다.)

 

2. 가장 빨리 시작하는 강의

0 - 12시간 시 바로 시작되기 때문에, 문제가 발생한다. 

 

3. 가장 빨리 끝나는 강의부터 진행하면 어떨까? 
*증명을 진행하진 않지만, 찾아보니 이 방식이 정답이었다. 이걸 생각하지 못한 것이 아쉽다. 

 

Nlist.sort(key = lambda x : x[1])

*key로 정렬을 변경할때는 lambda를 써야함을 그렇게 배웠음에도 까먹었다. 주의하자 .

 

import sys

N= int(sys.stdin.readline())

Nlist = []

for i in range(N) :

    Nlist.append(list(map(int,sys.stdin.readline().split())))

Nlist.sort(key = lambda x : (x[1],x[0]))

cnt = 1

beforeend = Nlist[0][1]

for i in range (1,N) :

    if Nlist[i][0] >= beforeend :

        beforeend = Nlist[i][1]

        cnt += 1

print(cnt)

 

끝나는 순으로 정리하고(key = lambda x : (x[1],x[0]))을 활용해서 1 이후 0으로도 정렬해주어야 한다 !

 

이후 처음에 가장 작은 값은 반드시 넣고, 이후 값은 이후 들어갈 수 있으면 넣으면 해결된다.

 

<현재 선택이, 이후 선택에 관여하지 않고. 지금 가장 작은 값을 넣는것이 최소이다> 

 

백준 1541 

 

import sys

N= sys.stdin.readline().strip()

M = N.split('-')

answer = 0

x= sum(map(int,(M[0].split('+'))))

if N[0] == "-" :

    answer = answer-x

else:

    answer = answer+x

for x in M[1:] :

    x = sum(map(int, (x.split('+'))))

    answer = answer-x

print(answer)

 

-가 있을때는, 그 뒤에 있는 모든 +들을 다 더한다음에 -하면

최소가 나온다. 

 

 

다만, 처음에는 음수가 있을 수 있다. 해당 내용을 추가했다. 

 

백준 13305

import sys

N = int(sys.stdin.readline())

lengthlist = list(map(int,sys.stdin.readline().split()))

moneylist = list(map(int,sys.stdin.readline().split()))

moneylist.pop()

ministmoneystation = moneylist.index(min(moneylist))

#전것 까진 ok

#처음애가 쭉 살수도 있음.

sumlength = sum(lengthlist)

summoney = 0

#처음 가야할 곳만큼만 충전하기

#처음 간곳 만큼 길이 뺴기

for i in range(ministmoneystation+1) :

    if i == ministmoneystation :

        summoney = summoney + (moneylist[i] * sumlength)

        break

        #남은 거리만큼 다 여기서 산다

    else:

        #최소가 아니라면, 최소만큼만

        summoney = summoney + (moneylist[i] * lengthlist[i])

        sumlength = sumlength - lengthlist[i]

   

print(summoney)

 

백준 질문 게시판의 모든 반례를 통과하지만, 17점을 받았다. 이는 시간 초과로 판단하여 시간을 줄이는 방법을 고민해보았다. 

 

import sys

N = int(sys.stdin.readline())

lengthlist = list(map(int,sys.stdin.readline().split()))

moneylist = list(map(int,sys.stdin.readline().split()))

minmoney = moneylist[0]

totalmoney = 0

for i in range(N-1):

    if moneylist[i] < minmoney :

        minmoney = moneylist[i]

    totalmoney = totalmoney + minmoney * lengthlist[i]

print(totalmoney)

 

min을 계산하지 않는 방법이 있었다.

해당 위치를 지나든 말든, min값을 비교하여 다음 갈 비용은 해당 min에서 다음 경로를 구매하는 형식으로

구현하면 되었던것. 

 

1. 반례를 생각하고

2. 시간초과를 고민하자. 

 

moneylist.sort(key = lambda x : x[0])

newlist = sorted(moneylist,key = lambda x: x[0])

 

**추가! 

람다정렬은 절대 절대 까먹지 말자. x에는 자동으로 앞의 변수가 들어간다. 

 

프로그래머스 큰 수 찾기

def solution(number, k):
    answer = []
    
    for num in number:
        while answer and answer[-1]<num and k>0 :
            answer.pop()
            k = k -1
         
        answer.append(num)
    if k>0 :
        return ''.join(answer[0:len(answer)-k])
    else:
        return ''.join(answer)

 

굉장히 어렵게 풀었다. 처음엔 list를 활용하였지만, pop이 remove보다 매우 느리다는 것을 간과하였다. 

최대한 pop을 사용하는 형태로 사용하는것이 유리하다.

다음 숫자보다 본인이 작을때 pop되는 것은 기억해냈지만.. 해당 방식을 선형 array로 하여 75점이라는 성공과

시간 초과가 발생했었다 . stack과 queue를 최대한 활용하자.