알고리즘(Algorithm)/동적프로그래밍(Dynamic Programming) (3) 썸네일형 리스트형 동적 프로그래밍 basic 문제-이항계수(Binomial Coefficient) - DP1 동적프로그래밍(Dynamic Programming)이란? 에서 동적프로그래밍이 무엇인지 알아보았고 동적 프로그래밍 문제를 해결하는 방법 에서는 dp 문제를 어떻게 접근해서 풀어야 하는지 설명하였다. 여기서는 기본적인 dp 문제를 풀어보면서 감을 익혀보자. 이항계수((Binomial Coefficient) 조합론에서, 이항 계수(二項係數, 영어: binomial coefficient)는 주어진 크기의 (순서 없는) 조합의 가짓수라고 정의되어 있다. 즉, 전체 집합에서 원소의 개수 n에 대해 r개의 아이템을 뽑는 이항계수(조합의 수)는 수학에서 다음과 같이 정의된다. 공식에 대한 자세한 설명은 생략한다. 이것을 재귀로 풀면 다음과 같다. 1 2 3 4 5 6 int binomial(int n, int k) .. 동적 프로그래밍 문제를 해결하는 방법? 동적프로그래밍(Dynamic Programming)이란? 에서는 동적프로그래밍 개념을 알아 보았다. 여기서는 동적프로그래밍으로 문제를 해결하는 방법에 대해서 설명한다. 동적프로그래밍 문제를 풀기위한 단계는 다음과 같다. step1. 요놈이 동적프로그래밍(DP) 방식으로 풀수 있을지 없을지부터 구분해라. 문제를 만나면 DP로 분류되는 문제인지 판단해야 한다. DP로 분류될수 있는 문제는 몇가지 특성이 있는데 문제의 해가 중복되는 하위문제(subproblems) 해를 사용하여 풀 수 있는 (Overlapping Subproblems) 특성이 있는지 또는 문제의 최적 해가 그 하위 문제의 최적 해로부터 얻을 수 있는 최적 하부 구조를 갖는 문제(Optimal Substructure)를 갖고 있는지 확인해라. .. 동적프로그래밍(Dynamic Programming)이란? 동적프로그래밍이란 동적계획법이라고도 부르는데 문제를 풀기위해 필요한 알고리즘이라기보다 문제를 푸는 방식을 말한다. 처음 알고리즘 공부할때 동적프로그래밍이 무엇인지 개념 잡기가 어려웠다. 개념 잡기가 어려웠던 이유는 아마 동적프로그래밍(dynamic programming ) 이름 자체의 모호함 때문이 아니였다 생각든다. 아직도 왜 동적프로그래밍이라고 부르는지 잘 모르겠지만 동적프로그래밍이 무엇인지 이해만 하면 된다. 개념 부터 설명하면 동적프로그래밍이란 ? 풀기가 복잡한 문제(complex problem)가 있다. 이 문제를 자세히 뜯어보니 큰 문제를 작은(하위) 문제(subproblems) 들로 나눌 수 있을거 같고 하위 문제들의 결과(답)를 이용하여 큰 문제를 풀려고 하는 방식이다. 복잡한 문제를 하위.. 이전 1 다음
