자료구조4 11장 - 그래프 11.1 그래프란? 그래프란 데이터 (객체)들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다. 정점 (Vertex, or Node)와 간선 (Edge, or Link)의 집합으로 정의된다. 정점과 간선의 집합이 같으면 시각적으로 다른 그래프여도 같은 그래프라는 것을 유의하자. 그래프의 종류 무방향그래프, 방향그래프, 가중치 그래프, 부분 그래프 무방향 그래프는 방향 그래프로 매핑해서 표현한다. 가중치 그래프에 연결관계가 없다고 함부로 0을 쓰지 말자. 그래프의 용어 adjaent vertex, in-degree, out-degree path : 간선을 따라 갈 수 있는 길, 정점의 나열로 표시된다. 경로의 길이 : 경로의 간선의 개수 단순경로 : 반복되는 간선이 없는 경로 사이클 : 단순 경.. 2020. 11. 27. 8장 - 트리 지금껏 살펴본 자료구조들은 선형 자료구조였다. 파일 디렉토리처럼 계층적인 자료를 나타낼 때는 트리라는 자료구조를 사용한다. 트리는 노드라는 데이터 단위들이 수직으로 연결되어 있는 형태다. 트리 용어 정리 노드, 루트, 서브트리, 간선, 부모노드, 자식노드, 단말노드,레벨는 기본적으로 알고 있을 것이다. 차수(Degree)란 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다. 트리의 차수는 차수 중 최대값이다. 트리의 높이는 트리의 최대 레벨을 의미한다. 레벨 h는 log2(n+1)보다 크고 n보다 작다. 차수가 동적이면 표현하기 복잡하니 노드들의 차수가 모두 2인 트리인 이진트리만 다루도록 하자. (이진트리의 단말 노드도 차수가 2이다.) 이진트리란? 1. 공집합이거나 2. 루트와 왼쪽 서브트리, 오.. 2020. 11. 14. 이진트리와 순회 이진트리는 모든 노드가 두개의 서브트리를 가지고 있는 트리를 이진트리라고 한다. 서브트리는 공집합일 수 있다. 따라서 이진트리의 노드에는 최대 두개의 자식노드를 가질 수 있다. 또한 서브 트리간에 순서가 존재한다. 정확히 설명하자면 1. 공집합이거나 2. 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한집합으로 정의된다. 이진트리의 서브 트리들은 모두 이진트리여야한다. 이처럼 이진트리는 재귀적으로 정의되기 때문에 재귀 알고리즘을 쓰는 것이 여러모로 편리하다 이진트리의 종류 포화 이진트리 트리의 각 레벨에 노드가 꽉 차 있는 트리, 높이를 k라 한다면 등비수열 합 공식에 의해 노드 수는 2^k -1개 완전 이진트리 트리의 높이가 k일 때 k-1까지는 노드가 모두 채워져있고 마지막 레벨에서는 노.. 2020. 9. 7. 재귀 함수 이론 정리와 피보나치 수열 재귀함수 : 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 기법이다. 따라서 순환적으로 정의된 문제나 알고리즘을 풀기 적합하다. 예를들어 팩토리얼, 피보나치수열, 이항계수, 이진트리, 이진탐색, 하노이탑 문제를 풀기 적절하다. 재귀함수는 호출부분과 멈추는 부분으로 나뉘어진다. 멈추는 부분이 없으면 무한히 호출하게 된다. 장점: 알고리즘을 명확하고 간결하게 쓸 수 있다. 단점: 함수호출을 여러번 하므로 메모리와 속도면에서 성능이 떨어진다. 반복문보다 재귀가 더 빠른 경우가 있다. 재귀함수는 재귀호출을 할 때마다 더 작은 문제로 쪼개지는데, 선형적으로 작아진다면 시간복잡도는 O(n)으로 반복문과 동일하다. 문제를 반으로 쪼개서 해결하는 경우 시간복잡도는 O(logn)으로 효율적이다. Head Re.. 2020. 9. 6. 이전 1 다음
