[하나라도 제대로] 그리디알고리즘(3)

1. 서론

강의링크: https://youtu.be/2zjoKjt97vQ

2. 본론

그리디 알고리즘은 '현재 상황에서 당장 좋은 것만' 고르는 방법을 의미한다.
코딩 테스트 문제에 기준에 따라 가장 좋은 것을 선택하는 알고리즘이므로 문제를 잘읽고 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 잡고 문제 풀이를 진행하자.

1) 예제문제: 모험가 길드

여기서 나는 함수형태로 만듬으로, [] 리스트 형태로 1개 받는걸로 하겠다.

(1) 내코드

A. 오름차순으로 정렬
B. 모험가 수보다 cur가 크면 stop

import heapq
def heapsort(dataset):
    h = []
    result = []
    for value in dataset:
        heapq.heappush(h, value)
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

def explorer(N):
    s_tmp = heapsort(N)
    result = 0
    cur = 0
    while(1):
        cur += s_tmp[cur]
        if cur >= len(s_tmp):
            break
        result += 1
    return result
print(explorer([1,1,4,2,2,1]))

정답!

(2) 모범답안

def explorer_dongbinna(N):
    N.sort()
    result = 0
    cnt = 0
    for i in N:
        cnt += 1
        if cnt >= i:
            result += 1
            cnt = 0
    return result

배울점

• 내 코드의 sort가 더 효율성이 좋은것으로 알고 있다. heapsort 외워서 저거 쓰자.
• 움직이는걸 표현하기위해서 if문 만족하기 전까지 돈다

마무리

그리디 알고리즘, 3번째 문제  정답을 맞추기는 했고 코드 효율성도 더 좋다.

내일은 2개씩 풀어보자