개발하는 고라니

# 학습목표 동적 프로그래밍이 무엇인지 이해한다. 어떤 특성을 가진 문제가 동적 프로그래밍의 적용 대상인지 감지할 수 있도록 한다. 기본적인 몇 가지 문제를 동적 프로그래밍으로 해결할 수 있도록 한다. # 배경 재귀적 해법 큰 문제에 닮음꼴의 작은 문제가 깃든다. 잘 쓰면 보약, 잘못 쓰면 맹독 관계중심으로 파악함으로써 문제를 간명하게 볼 수 있다. 재귀적 해법을 사용하면 심한 중복 호출이 일어나는 경우가 있다. 재귀적 해법의 양면성 바람직한 예 퀵정렬, 병합정렬 등의 정렬 알고리즘 계승(Factorial) 구하기 그래프의 DFS(Depth First Search) 등 치명적인 예 피보나치수 구하기 행렬곱셈 최적순서 구하기 # 도입 문제 : 피보나치수 구하기 * f(n) = f(n-1) + f(n-2) ..

# 학 습 목 표 그리디 알고리즘의 특징을 파악한다. 그리디 알고리즘으로 최적해가 보장되는 예와 그렇지 않은 예를 관찰한다. # 그리디 알고리즘 눈 앞의 이익만 취하고 보는 알고리즘 현재 시점에 가장 이득이 되어 보이는 해를 선택하는 행위를 반복한다. 대부분 최적해와의 거리가 멀다. 드물게 최적해가 보장되는 경우도 있다. (최소 신장 트리, 최단 경로 등)do do { 우선 가장 좋아 보이는 선택을 한다 } until (해 구성 완료) # 그리디 알고리즘의 전형적 구조 Greedy(C) C : 원소들의 총 집합 { S 5원 짜리 -> 1원 짜리 - 이렇게 동전의 액면이 모두 바로 아래 액면의 배수가 되면 그리디 알고리즘으로 최적해가 보장 된다. But, 액면이 바로 아래의 액면의 배수가 되지 않으면 그리..