28 장 : 알고리즘 개발 방법론 1 ( Divide and Conquer , Dynamic Programming ) | Digital Dynamics 
 28 장 : 알고리즘 개발 방법론 1 ( Divide and Conquer , Dynamic Programming ) 
 지금 까지 살펴 본 알고리즘 들 은 주어진 문제 를 최적 으로 해결 하 는 것 들 이 었 습니다 . 우리 의 선조 들 이 힘든 연구 와 통찰 을 통해 찾아낸 아름답 고 도 멋진 해법 들 입니다 . 
 하지만 이 들 은 처음 접한 문제 들 에 대해 어떻게 해법 을 찾 을 수 있 었 을까요 ? 또 우리 가 새로운 문제 를 접하 게 될 때 , 참조 할 만 한 비슷 한 연구 결과 가 없 다면 어떻게 해결 해야 할까요 ? 
 " 알고리즘 개발 방법론 " 이 라는 소제목 으로 소개 시켜 드리 고자 하 는 네 가지 접근 법 은 바로 이렇게 특별 한 최적 화 된 해법 이 없 는 문제 에 대해 어떻게 접근 하 여 최적 화 된 혹은 쓸 만 한 해법 을 찾 을 수 있 는지 에 대한 " 방법론 " 을 살펴볼 것 입니다 . 
 대부분 의 알고리즘 교과서 들 에서 이 방법 론 이 먼저 소개 되 고 , 구체 적 인 문제 로 들어가 기 때문 에 알고리즘 을 공부 하 는 데 큰 진입 장벽 이 되 어 왔 던 영역 입니다 . 구체 적 인 걸 먼저 알아보 고 일반 적 인 해법 을 찾 는 순 으로 재 배치 해 보 았 는데 , 효과 가 있 을런지 모르 겠 네요 . 
 이번 장 에서 는 분할 점령 ( Divide and Conquer ) 와 동적 계획 ( Dynamic Programming ) 에 대해 알아보 겠 습니다 . 
 28 . 0 알고리즘 개발 방법론 1 - 시작 : 알고리즘 개발 방법 론 에서 는 새로운 문제 를 만났 을 때 이 에 대한 해법 을 찾 을 수 있 는 기본 도구 들 에 대해 알아봅니다 . 이 장 에서 는 분할 정복 과 동적 계획법 에 대해서 배웁니다 . 
 28 . 1 분 할 정복 ( Divide and Conquer ) 개념 : 분할 정복 으로 문제 를 푸 는 것 은 이미 여러 번 소개 된 바 있 습니다 . 분할 정복 은 해결 할 수 없 는 큰 문제 를 해결 할 수 있 는 수준 까지 쪼개 어 해결 한 다음 , 그 결과 를 병합 하 여 가 면서 최종 적 인 해답 을 찾 는 방법 입니다 . 재귀 적 인 구조 이 기 때문 에 대부분 재귀 호출 로 구현 됩니다 . 그리고 직관 적 이 고 아름다운 해법 입니다 . 
 28 . 2 Strassen 의 행렬 곱셈 : 분할 정복 으로 문제 를 푸 는 예 는 앞서 많이 소개 했 습니다 . 새로운 관점 을 드리 기 위해 행렬 의 곱셈 을 분할 정복 으로 최적 화 하 는 법 을 알 아 봅니다 . Strassen 은 2 x 2 행렬 의 곱셈 에 대해 최적 화 된 계산법 을 고안 했 는데 , 이 를 분할 점령 법 으로 응용 하 면 임의 차원 의 정방 행렬 에 대한 곱셈 을 할 수 있 습니다 . 
 28 . 3 가장 가까운 쌍 ( Closest Pair ) : 공기 가 좋 은 곳 에서 밤 하늘 을 보 면 엄청난 수 의 별 이 보입니다 . 이 별 들 중 에서 가장 가까이 붙 어 있 는 별 을 찾 을 수 있 습니까 ? 가장 가깝 다는 것 은 가장 충돌 할 가능 성 이 크 다는 걸 의미 하 기 때문 에 선박 이나 비행기 의 관제 에서 도 매우 중요 한 문제 입니다 . 특히 매우 빨리 찾 을 수 있 어야 하 므로 최적 의 알고리즘 이 필요 합니다 . 분할 점령 법 으로 가장 가까운 쌍 을 효율 적 으로 찾 아 봅니다 . 
 28 . 4 동적 계획법 ( Dynamic Programming ) : 동적 계획법 은 분할 점령 과 연관 되 어 있 습니다 . 분할 점령 은 문제 를 작 게 쪼개 는데 , 고로 작 은 문제 가 매우 많 아 집니다 . 그런데 작 은 문제 들 의 해 는 중복 될 가능 성 이 큽니다 . 그렇 다면 이미 풀이 한 문제 의 해 를 따로 저장 해 둔다면 중복 된 문제 는 계산 하 지 않 고 찾아보 는 것 으로 효율 을 높일 수 있 습니다 . 하지만 동적 계획법 은 분할 점령 하 는 문제 모두 에 적용 될 수 는 없 습니다 . 
 28 . 5 동적 계획법 으로 Knapsack 문제 풀 기 : 여러 개 의 베 낭 ( Knapsack ) 에 서로 다른 물건 을 담 는 Knapsack 문제 는 매우 유명 합니다 . 실제 이 해법 은 컨테이너 에 화물 을 어떻게 실어야 가장 이익 을 볼 수 있 는지 를 찾 는데 활용 될 수 있 습니다 . Knapsack 문제 는 조건 에 따라 해법 도 가지각색 입니다 . 여기 에서 는 Unbounded Knapsack 문제 를 동적 계획법 으로 푸 는 방법 을 알아봅니다 . 
 28 . 6 외판원 순회 ( Traveling Salesman ) 문제 : 외판원 순회 는 모든 정점 이 연결 된 그래프 에서 모든 정점 을 방문 하 고 원래 출발지 로 돌아오 는 최소 비용 의 경로 를 구하 는 문제 입니다 . 이 또한 실제 많이 제기 되 는 문제 이 지만 의외 로 쉽 게 풀 수 있 는 해법 은 찾 아 지 지 않 았 습니다 . 
 28 . 9 알고리즘 개발 방법론 1 - 결론 : 분할 점령 과 동적 계획법 에 대해서 살펴 보 았 고 , 알고리즘 분야 에서 유명 한 문제 들 을 살펴보 고 이 를 풀이 해 보 았 습니다 . 더 흥미 로운 내용 은 다음 장 에 이어집니다 . 
 - 29 장 : 알고리즘 개발 방법론 2 ( Greedy Method , Backtracking ) 
 시간 : 수요일 , 6 월 17 , 2015 
 eunsoo kim 2015 년 8 월 5 일 오후 7 : 37 
 강의 잘 보 고 있 습니다 . Traveling Salesman 문제 의 경우 유투 브 나 여기 나 강의 영상 이 없 는데요 혹시 이 부분 올려 주 실 수 있 으신 가요 ? 
 비터스 윗 2015 년 8 월 5 일 오후 7 : 54 
 이 다음 장 Backtracking 에 간단히 언급 되 어 있 습니다 . 도움 이 되 실 런지 모르 겠 네요 . 
 http : / / ddmix . blogspot . kr / 2015 / 06 / cppalgo - 29 - greedy - backtracking . html 
 eunsoo kim 2015 년 8 월 6 일 오후 4 : 18