TIL - 15 알고리즘

이동근·2021년 1월 2일

알고리즘

python

목록 보기

7/18

Dynamic programing(동적 계획법)

큰 문제를 작은 문제로 나누어서 문제를 해결하는 방식
부분문제들의 최적의 답을 이용해서 최적의 답을 구할 수 있다는 것

사용 조건

중복되는 문제들이 많다.
최적부분 구조가 있다.

최적 부분 구조란?

큰 문제의 답을 작은 문제를 통해 구할 수 있다는 의미

Dynamic programing의 방법

1. Memoization(재귀, 상향식접근)

중복되는 부분을 cache에 저장해 놓고 필요할 때 마다 꺼내서 사용하는 방법이다. 위쪽 부터 필요한 계산을 요구해서 해 나가는 방식으로, 필요없는 계산은 하지 않는다.근

2. Tabulation(반복문, 하양식 접근)

테이블에 작은 값부터 하나씩 저장해서 채워가는 방식으로 n번째 값을 구한다.

피보나치의 수열 - 다음 항이 그 전의 값과 그 다음값의 합으로 이루어 이루어지는값
1. Memoizaion으로 해결하는 방법(재귀)

def fib_memo(n, cache):
    # base case
    if n < 3:
        return 1
        
   # recursive case
   # 이미 계산 된 값이 cache에 저장 되어 있으면 호출
   if n in cache:
       return cache[n]
   # 만약 없으면 cache에 저장
   cache[n] = fib_memo(n- 1, cache) + fib_memo(n - 2, cache)
   
   return cache[n]

Tabulation으로 해결 하는 방법(반복문)

def fib_tab(n):
    # 저장할 테이블 호출
    fib_table = [0, 1, 1]
    
    # 3번째 항 부터 앞의 두 핪으로 값을 추가해 n번째 수를 구한다.
    for i in range(3, n + 1):
        fib_table.append(fib_table[i - 1] + fib_table[i - 2])
    
    return fib_table[n]

Greedy Alorithm

미래를 생각하지 않고 눈 앞에 보이는 최적의 선택을 하는 방식

장점 : 간단하고 빠르다.
단점 : 최적의 답이 보장되지 않는다.

언제 Greedy Alorithm을 사용할까

문제를 해결하는 알고리즘이 너무 느려서 사용할때와, 당장 답만이 필요할 때 사용.

Greedy Algorithm이 최적의 답을 구해주는 경우

최적부분 구조가 존재할때
탐욕적 선택속성(Greedy choice Property) - 각 단계에서 탐욕스런 선택이 최종의 답을 구하기 위한 최적의 선택 이 존재할 때

예제
수강 신청 분석
1. 최대한 많은 수업을 들을 수 있는 방법을 찾으려고 한다. 튜플 (2, 5) 는 각 수업시간의 시작과 끝을 의미 한다.
2. 수강 리스트 - [(4, 7), (2, 5), (1, 3), (8, 10), (5, 9), (2, 6), (13, 16), (9, 11), (1, 8)]

질문
1. 이 수강 리스트에는 최적부분 구조가 있습니까?
답 YES
-> 서로 서로 비교해서 구하면 구할 수 있음

이 수강 리스트에는 탐욕적 선택 속성이 있습니까?
답 YES
-> 남은 수업 중 가장 일찍 끝나는 수업을 고르면 할 수 있다.

따라서 Greedy Algorithm이 가능합니다.

def course_selection(course_list):

    # 1. 리스트 상에서 튜플 두 번째항을 기준으로 정렬 을 해주기
    sorted_list = sorted(couse_list, key = lambda x: x[1])
    
    # 2. 나의 수강신청 리스트 만들기
    my_couse_list = [couse_list[0]]  -> 첫 번째 항은 제일 일찍 끝나는 수업이므로 넣어줌
    
    # 3. 차례로 넣어주기 단 리스트에 있는 끝나는 시간과 남아있는  수업의 시작시간이 겹치면 안됨
    for course in couse_list:
        if course[0] < my_couse_list[-1][1]:   -> 리스트에 있는 -1항 가장 마지막항의 [1]끝나는 시간
        my_couse_list.appen(cousrse)
    
   return course