반응형 분류 전체보기340 [알고리즘] 동적 계획법(Dynamic Programming) - 3 동적 계획법(Dynamic Programming) - 3 동적 계획법이라는 것은 순환식과 뗄레야 뗄수 없는 관계이다. 다시 말해 순환식을 효과적으로 푸는 테크닉이라고 할 수 있다.따라서 동적 계획법은 다음과 같은 특징을 가지고 있다. 1. 일반적으로 최적화문제 혹은 카운팅 문제에 적용된다.2. 주어진 문제에 대한 순환식을 정의한다.3. 순환식으로 Memoization 또는 Bottom up 으로 푼다. 동적계획법은 subproblem을 풀어서 원래 문제를 푸는 방식이다. 그런 의미에서 분할 정복법과 공통점이 있다.분할 정복법에서는 분할된 문제들이 서로 disjoint하지만 동적계획법에서는 그렇지 않다.즉 서로 overlapping하는 subproblem들을 해결함으로써 원래의 문제를 해결하는 것이다. 분.. 2017. 6. 9. [책] 멋진 신세계(Brave New World) 멋진 신세계(Brave New World) 원시 시대부터 4차 산업 혁명까지, 인류는 종족 보전과 발전을 위해 부단히 노력해 왔다. 인류의 기원에서 부터 제 1차 산업혁명까지, 다시 1차 산업혁명에서 현재까지를 비교해 보았을 때, 후자의 인구 변화가 더욱 급증한 것은 과학과 의료기술의 발전에 따른 따른 안정화와 수명 연장으로 인한 결과 라고 할 수 있다. 이처럼 과학의 발전은 시대가 흘러감에 따라 가속도가 점점 빨라지고 있다. 이러한 문명 발전의 시대 속에서 우리가 꿈꾸던 투명인간이나 복제 인간, 순간 이동 등의 기술은 더 이상 공상 과학 영화에서만 다루어지는 내용이 아닐수도 있다. 물론, 과학이 어떤 방향으로 발전하느냐에 따라 우리가 우려하는 핵전쟁 등의 디스토피아적 시나리오로 발전할수도 있는 것이고,.. 2017. 6. 9. [알고리즘] 동적 계획법(Dynamic Programming) - 2 동적 계획법(Dynamic Programming) - 2 지난 시간에 이어서 기본적인 동적 계획법의 예를 알아보자위의 그림은 정수들이 저장된 nXn의 좌상단에서 우 하단 까지 이동하는 문제이다.단 이때, 오른쪽이나 하단으로만 이동이 가능하다.또한 이렇게 이동하면서 지나간 모든 셀들에 저장된 값들의 합이 최소가 되도록 해야한다. 사실 이 문제는 그래프의 다익스트라 알고리즘으로 얼마든지 풀수 있지만 여기에서는 동적 계획법으로 풀어보도록하자앞선 포스팅에서는 이항계수와 피보나치를 구하는 문제를 보았는데, 거기에서는 순환식 자체가 주어졌다.그러나 실제로, 대부분의 경우에는 주어진 순환식을 푼다기 보다는 문제가 주어졌을 때, 문제를 풀기위한순환식을 세우고 이것을 계산하는 과정 전체를 동적 계획법이라고 한다.다시말해.. 2017. 6. 9. [알고리즘] 동적 계획법(Dynamic Programming) - 1 동적 계획법(Dynamic Programming) 우리가 전에 피보나치 수를 계산하기 위해 재귀 함수를 사용했었다.이는 같은 연산이 반복되기 때문이다. 그러나 이 함수의 진행 과정을 살펴보면 중복이 심하다는 것을 알수 있다. 위의 그림에서 보면 fib(2)가 여러번 반복되며 오버헤드가 증가함으로 결국 비효율적인 코드가 된다. 따라서 이러한 중복을 제거 하기 위해서 메모이제이션(Memoization)이라는 테크닉을 사용한다.이는 사전에는 나오지 않는 프로그래밍 테크닉이며, 계산된 값을 버리지 말고 저장한다는 뜻이다예를 들어 위의 그림에서 계산이 된 fib(2) 값을 저장해 놓고 있다가, 필요한 경우 계산없이 호출하게 된다.이렇게 저장되는 배열을 '캐시'라고 하며, 중간에 저장하는 걸 '캐싱한다'라고 부른다.. 2017. 6. 6. 이전 1 ··· 28 29 30 31 32 33 34 ··· 85 다음 반응형
