Algorithm5

Apr 5, 2022 » 2022

5주차 실습 : Greedy, Dynamic Programming

Greedy Algorithm

탐욕스러운 선택 조건 : 안전하다 보장 = 이 선택으로 인해 전체 문제의 최적해를 반드시 도출
최대/최소의 경우의 수를 구하는 것 요구하는 문제
정렬 후 푸는 문제가 많다.

ex) 거스름돈 문제
거스름돈으로 사용할 500원, 100원, 50원, 10원이 존재한다. 거슬러 줘야 할 돈이 N원일 때, 필요한 동전의 최소 개수? (단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.)

‘가장 튼 단위 부터 생각하자’

N = 2240 인 경우, 조건에서 ‘최소 개수’를 구하는 문제이므로 가장 큰 단위부터 거슬러 나머지를 그 다음 단위 화폐로 거슬러 주는 것.

def solution(money):
    answer = 0
    change = [500, 100, 50, 10]
    remain = money
    for i in change:
        answer += remain // i
        remain = remain % i
    return answer

활동 선택 문제 : 시간표짜기, 회의실 시간 분배
한 강의실에서 여러개의 수업을 하려고 할 때 한번에 가장 많은 수업을 할 수 있는 경우?

최적해를 구하기 위해서는 가장 빨리 끝나는 수업을 골라야 한다.

n = int(input())
time_list = []
last_idx = 0
cnt = 0
for i in range(n):
    time_list.append(list(map(int,input().split())))

time_list.sort(key=lambda x: (x[1], x[0])) #Fi 기준 정렬 후, Si 기준 정렬

for i in range(len(time_list)):
    if time_list[i][0] >= last_idx:
        last_idx = time_list[i][1]
        cnt += 1
        continue
    else:
        continue
print(cnt)

Dynamic Programming

큰 문제를 작은 문제로 나누어 푸는 문제

분할정복과 비슷해보이지만, 작은 문제에서 반복이 일어나는 부분이 없다!

작은 문제들은 한번만 풀어, 정답을 구한 작은 문제를 저장해놔, 큰 문제를 풀어갈 때 저장한 결과값 이용

작은 문제가 반복이 일어나는 경우
같은 문제는 구할 때마다 정답이 같다

def memoization_fibo(n):
    memo[0] = 1
    memo[1] = 1

    if n < 2:
        return memo[n]
    for i in range(2, n+1):
        memo[i] = memo[i-2] + memo[i-1]

    return memo[n]

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    memo = [0 for i in range(n+2)]
    print(momoization_fibo(n))

# 배열 이용시 인덱스 주의