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

1. 서론

강의링크: https://youtu.be/2zjoKjt97vQ
그리디 알고리즘, 탐욕 알고리즘 이라고 불리는 이것은 추후 배우게될 완전 탐색이나 dfs,bfs 등 역량을 키우는데 중요한 경험이 될것이다.

2. 본론

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

1) 예제문제: 1이 될 때 까지

어떠한 수 N이 1이 될 때까지 2가지 연산을 반복적으로 수행할 수 있다.

• N에서 1을 뺀다
• N을 K로 나눈다.내 코드

(1) 내코드

A. N이 1이 되면 반복을 멈추라고 함
B. 처음에 K로 나눠지면 N = N / K 라고 설정하고 cnt를 1 증가시킴
C. 안나눠지면 N = N - 1이라고 하고 cnt를 1 증가 시킴 

def untilBeOne(N, K):
    cnt = 0
    while(N!=1):
        if N % K == 0:
            N = N / K
            cnt = cnt + 1
        else:
            N = N - 1
            cnt = cnt + 1
    return cnt
print(untilBeOne(17,4)) #위는 한번 반복할때마다 반복횟수마다 기하급수적으로 올라간다.

반례
N=3, K=4 일때 3이여야하는데 내 코드는 2가 나온다.

(1) N이 K보다 작을때 나눠지지 않으므로 빼기만 만복해야한다.

(2) 모범답안

def untilBeOne_dongbinna(N, K): # 동빈나는 코드가 좀 빨리 실행될 수 있도록 테크닉을 가미하였다.
    result = 0
    while 1:
        tmp = (N // K) * K
        result += (N - tmp)
        N = tmp
        if N < K:
            break
        result += 1
        N //= K
    result += (N - 1)
    return result
    
 print(untilBeOne_dongbinna(3,4))

마무리

탐욕법으로 얻은 해가 최적의 해인지 아닌지 추론할 수 있도록 하자.