TIL - 15 알고리즘
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
출처 - codeit(알고리즘)
Author And Source
이 문제에 관하여(TIL - 15 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@eagle5424/TIL-15-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)