목차
1. 트리의 개념과 용어 정리(노드,근노드와 레벨 깊이 등)p.185~188
2. 트리와 이진트리의 차이점, 트리를 이진트리로 변환해야 하는 이유(p.192~194)
3. 이진트리의 종류(p.201~202)
4. 이진트리의 운행(p.212~223)-중위,전위,후위 운행 방식
5. 트리를 이진트리로 변환하는 방법(p235~237)
6.그래프(p.247~287)-그래프의 개념, 그래프의 종류와 그 용어의 뜻, 그래프의 인접행렬, 인접리스트 표현, 최단경로 탐색 알고리즘.
2. 트리와 이진트리의 차이점, 트리를 이진트리로 변환해야 하는 이유(p.192~194)
3. 이진트리의 종류(p.201~202)
4. 이진트리의 운행(p.212~223)-중위,전위,후위 운행 방식
5. 트리를 이진트리로 변환하는 방법(p235~237)
6.그래프(p.247~287)-그래프의 개념, 그래프의 종류와 그 용어의 뜻, 그래프의 인접행렬, 인접리스트 표현, 최단경로 탐색 알고리즘.
본문내용
를 해결하고자 할 때 사용되는 선택규칙이 궁극적으로 최적해를 구해낸다는 것에 대한 증명이 반드시 뒷받침 되어야 한다.
Dynamic이라는 것은 Divide and Conquer의 반대말이다. Divide and Conquer는 큰 문제를 먼저 작은 문제들로 분할하고 각각 해결해나가는 것인데 반해, Dynamic은 작은 문제를 먼저 해결하고, 그 결과를 저장한 다음, 후에 똑같은 계산을 반복하는 대신, 그 저장한 결과를 이용하는 방식이다.따라서 메모리가 많이 필요하다는 것이 Dynamic의 단점이다
플로이드 알고리즘 (Floyd Algorithm)
Dijkstra 알고리즘이 Greedy한 방법이었다면 Floyd 알고리즘은 동적계획법이 들어간 보다 고차원적인 알고리즘이라 할 수 있다. 혹자는 Dijkstra 알고리즘이 나중을 고려치 않음을 보며 단순무식하다(?)고 평하기도 한다.
최적해를 구하는 문제를 푸는 방법들은 의례적으로 여러 단계를 거치게 되고, 각 단계에서는 일반적으로 선택을 하게된다. 이러한 최적해를 구하는 문제들은 동적 계획법을 적용하면 모든 경우에 최적해를 구할 수 있지만, 더욱 간단하고 효과적인 Greedy 방법에 의해 해결되는 문제들도 많이 있다. Greedy 방법은 최적해를 구하는 문제를 풀기위해서 행하는 각 단계에서의 선택시, 그 단계에서의 상황만 고려해서 최선의 선택을 한다. 즉, 최적해를 구하기위해서 각 단계에서 최선의 선택만 하면 궁극적으로 최적해를 구할 수 있기를 바라는 것이다. 물론, 구할 수 없는 경우도 많이 있겠지만, 실제, 이런 방법으로 해결될 수 있는 최적화 문제들이 상당히 존재한다.
이런 문제들에 대해서 동적 계획법을 적용하여 문제를 해결하려 하는 것은 시간과 노력의 낭비가 아닌가 하는 입장도 있지만 실제 프로그래머의 입장에서 보면Dijkstra알고리즘보다 본 Floyd알고리즘이 코딩면에서 훨씬 간단하다. 어차피 계산은 컴퓨터가 하는 것이므로 간단한 코딩이 더 선호될 수도 있다.
그런데 더욱 재미있는 것은 실제 성능에서도 Floyd 알고리즘이 앞선다는 것이다. Dijkstra 알고리즘의 시간복잡도가 O(n^2) 인데 반해 플로이드 알고리즘은 O(n^3)이다. 이것만 봐서는 Floyd 알고리즘이 더 느릴 것이라고 생각하기 쉽다. 하지만 Dijkstra 알고리즘이 한번의 루프를 돌 때마다 하는 일이 많다보니(복잡하다보니) 실제로는 Floyd가 빠른 경우가 상당히 많다
Dynamic이라는 것은 Divide and Conquer의 반대말이다. Divide and Conquer는 큰 문제를 먼저 작은 문제들로 분할하고 각각 해결해나가는 것인데 반해, Dynamic은 작은 문제를 먼저 해결하고, 그 결과를 저장한 다음, 후에 똑같은 계산을 반복하는 대신, 그 저장한 결과를 이용하는 방식이다.따라서 메모리가 많이 필요하다는 것이 Dynamic의 단점이다
플로이드 알고리즘 (Floyd Algorithm)
Dijkstra 알고리즘이 Greedy한 방법이었다면 Floyd 알고리즘은 동적계획법이 들어간 보다 고차원적인 알고리즘이라 할 수 있다. 혹자는 Dijkstra 알고리즘이 나중을 고려치 않음을 보며 단순무식하다(?)고 평하기도 한다.
최적해를 구하는 문제를 푸는 방법들은 의례적으로 여러 단계를 거치게 되고, 각 단계에서는 일반적으로 선택을 하게된다. 이러한 최적해를 구하는 문제들은 동적 계획법을 적용하면 모든 경우에 최적해를 구할 수 있지만, 더욱 간단하고 효과적인 Greedy 방법에 의해 해결되는 문제들도 많이 있다. Greedy 방법은 최적해를 구하는 문제를 풀기위해서 행하는 각 단계에서의 선택시, 그 단계에서의 상황만 고려해서 최선의 선택을 한다. 즉, 최적해를 구하기위해서 각 단계에서 최선의 선택만 하면 궁극적으로 최적해를 구할 수 있기를 바라는 것이다. 물론, 구할 수 없는 경우도 많이 있겠지만, 실제, 이런 방법으로 해결될 수 있는 최적화 문제들이 상당히 존재한다.
이런 문제들에 대해서 동적 계획법을 적용하여 문제를 해결하려 하는 것은 시간과 노력의 낭비가 아닌가 하는 입장도 있지만 실제 프로그래머의 입장에서 보면Dijkstra알고리즘보다 본 Floyd알고리즘이 코딩면에서 훨씬 간단하다. 어차피 계산은 컴퓨터가 하는 것이므로 간단한 코딩이 더 선호될 수도 있다.
그런데 더욱 재미있는 것은 실제 성능에서도 Floyd 알고리즘이 앞선다는 것이다. Dijkstra 알고리즘의 시간복잡도가 O(n^2) 인데 반해 플로이드 알고리즘은 O(n^3)이다. 이것만 봐서는 Floyd 알고리즘이 더 느릴 것이라고 생각하기 쉽다. 하지만 Dijkstra 알고리즘이 한번의 루프를 돌 때마다 하는 일이 많다보니(복잡하다보니) 실제로는 Floyd가 빠른 경우가 상당히 많다
추천자료
- 경북 동해안방언의 어휘적 특징
- 상린관계
- 디지털 시대의 최초판매원칙에 대한 수정원리와 국제동향
- 다익스트라와 DBF알고리즘
- FPGA를 이용한 OFDM 모뎀 구현
- 상린관계와 공동소유
- 수도권규제완화 정책의 문제점 및 올바른 방향
- 제 6장. 행동주의와 사회인지학습이론
- 글쓰기와 스토리 텔링 줄거리 요약 및 감상문, 느낀점, 독후감, 나의 견해, 나의 소감, 시사...
- [A+] 저작권의 의의와 저작물의 종류
- 음반저작권(음악저작권, MP3저작권) 개념, 의의, 음반저작권(음악저작권, MP3저작권) 영향, ...
- 채만식 (탁류, 태평천하, 작품분석, 논이야기, 미스터 방, 민족의 죄인, 교과서 기출문제)
- [지역관광개발과 자치단체협력] 관광개발과 자치단체 협력의 필요성, 자치단체간 협력의 목적
소개글