자료구조 요점정리

소개글

자료구조 요점정리에 대한 보고서 자료입니다.

목차

1. 트리의 개념과 용어 정리(노드,근노드와 레벨 깊이 등)p.185~188

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가 빠른 경우가 상당히 많다

키워드

자료구조,   요점정리,   트리,   이진트리,   그래프,   인접행렬,   인접리스트