자료구조3 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. 재귀 함수 이론 정리와 피보나치 수열 재귀함수 : 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 기법이다. 따라서 순환적으로 정의된 문제나 알고리즘을 풀기 적합하다. 예를들어 팩토리얼, 피보나치수열, 이항계수, 이진트리, 이진탐색, 하노이탑 문제를 풀기 적절하다. 재귀함수는 호출부분과 멈추는 부분으로 나뉘어진다. 멈추는 부분이 없으면 무한히 호출하게 된다. 장점: 알고리즘을 명확하고 간결하게 쓸 수 있다. 단점: 함수호출을 여러번 하므로 메모리와 속도면에서 성능이 떨어진다. 반복문보다 재귀가 더 빠른 경우가 있다. 재귀함수는 재귀호출을 할 때마다 더 작은 문제로 쪼개지는데, 선형적으로 작아진다면 시간복잡도는 O(n)으로 반복문과 동일하다. 문제를 반으로 쪼개서 해결하는 경우 시간복잡도는 O(logn)으로 효율적이다. Head Re.. 2020. 9. 6. 이전 1 다음
