- 1. 그래프의 운행
- 그래프를 구성하는 모든 정점들을 체계적으로 방문하는 방법
- 스택을 이용한 깊이 우선 탐색 방법과
- 대기열을 이용한 넓이 우선 탐색 방법이 있다.
- 2. 그래프의 응용
- 최단 경로(shortest path)
- 단일 점 출발 최단 경로 문제 (single source shortest path problem)
- 모든 노드 간의 최단 경로 문제 (all pairs shortest path problem)
- 최소 비용 신장 트리(minimal cost spanning tree)
- 신장 트리
- 최소 비용 신장 트리 알고리즘
- Kruskal의 방법
- 작업 네트워크의 위상 정렬과 임계 경로
- 최단 경로(shortest path)
자료구조/핵심요약2017. 7. 4. 21:31
자료구조/핵심요약2017. 7. 4. 21:30
자료구조/핵심요약2017. 6. 26. 16:06
- 1. 그래프의 개념
- 그래프의 정의
- 정점(vertex)이라고 불리는 원소들의 집합 V와 간선(edges)이라 불리는 V의 원소들의 비순서화된 쌍들의 집합 E로 구성
- V는 공집합이 아닌 정점들의 유한집합
- E는 간선, 즉 연결선의 집합
- V(G)는 그래프의 정점의 집합
- E(G)는 그래프의 간선의 집합
- 그래프의 정의
- 2. 그래프의 종류
- 무방향 그래프(undirected graph 또는 graph)
- 방향 그래프(directed graph 또는 digraph)
- 다중 그래프(multi graph 또는 multiple graph)
- 단순 그래프(single graph 또는 tree graph)
- 완전 그래프(complete graph)
- 서브그래프(subgraph)
- 정규 그래프(regular graph)
- 연결그래프(connected graph)
- 강력 연결 그래프
- 약 연결 그래프
- 단절그래프(disconnected graph)
자료구조/핵심요약2017. 6. 26. 16:05
- 1. 트리의 산술식의 내부 표현
- 산술식의 내부 표현(polish notation)
- 중위 표기법(infix notation) : left - root - right 운행 -> 산술식의 표현에서 변수 - 연산자 - 변수의 순으로 표시된다.
- 후위 표기법(postfix notation) : left - right - root 운행 -> 산술식의 표현에서 변수 - 변수 - 연산자의 순으로 표시된다.
- 전위 표기법(prefix notation) : root - left - right 운행 -> 산술식의 표현에서 연산자 - 변수 - 변수의 순으로 표시된다.
- 산술식의 내부 표현(polish notation)
- 2. 이진 트리의 삽입
- 어떤 새로운 노드를 입력한다면 그의 키를 이용하여 이진 트리의 성질을 만족 한 어떤 자식 노드가 될 것인가의 위치를 결정하여 저장하는데 키 값을 중심으로 키 값보다 큰 수는 오른쪽 자식 노드가 되고, 키 값보다 작은 수는 왼쪽 자식 노드가 된다.
- 3. 이진 트리의 삭제
- 삭제할 노드를 단 노드로 대치시킨다.
- 대치시키기 위해 선택하는 단 노드는 삭제할 노드의 왼쪽 서브 트리 내에 있고, 맨 오른쪽에 있는 단 노드이다.
- 먼저 삭제할 노드가 단 노드일 경우에는 바로 해당 노드를 삭제한다.
- 삭제할 노드의 왼쪽 서브 트리에 오른쪽 노드가 없는 경우 해당 노드를 삭제 한 후 왼쪽 단 노드가 빈 자리로 옮겨 간다.
- 삭제할 노드의 왼쪽 노드에 서브 트리가 있는 경우 해당 노드를 삭제한 후 왼쪽 서브 트리의 제일 오른쪽 노드를 삭제된 노드에 채워준다.
자료구조/핵심요약2017. 6. 19. 21:14
자료구조/핵심요약2017. 6. 19. 21:13
자료구조/핵심요약2017. 6. 19. 13:04
- 1. 트리의 운행(tree traversal)
- 트리의 운행(tree traversal) 이란?
- 트리 구조의 각 노드를 전부 한번씩 방문하여 검색해내는 방법
- 트리의 운행(tree traversal) 이란?
- 2. 일반 트리의 운행법
- 레벨 순서 (level order) 운행법
- 하향식 레벨 순서(topdown level order) 운행법
- 상향식 레벨 순서(bottom up level order) 운행법
- 노드의 위치에 따른 운행법
- 전위 운행법(preorder traverse)
- 후위 운행법(postorder traverse)
- 패밀리 순서(family order)운행법
- 레벨 순서 (level order) 운행법
- 3. 이진 트리의 운행(tree traversal)법
- 왼쪽 서브트리가 오른쪽 서브트리보다 우선하는 경우
- 근 노드→ 왼쪽 서브트리→ 오른쪽 서브트리
- 왼쪽 서브트리→근 노드→ 오른쪽 서브트리
- 왼쪽 서브트리→ 오른쪽 서브트리→근 노드
- 오른쪽 서브트리가 왼쪽 서브트리보다 우선하는 경우
- 근 노드→ 오른쪽 서브트리→ 왼쪽 서브트리
- 오른쪽 서브트리→근 노드→ 왼쪽 서브트리
- 오른쪽 서브트리→ 왼쪽 서브트리→근 노드
- 왼쪽 서브트리가 오른쪽 서브트리보다 우선하는 경우
- 4. 이진 트리의 운행 알고리즘
- 전위 운행법(root-left-right)의 알고리즘(polish 표기법)
- 중위 운행법(left-root-right)의 알고리즘
- 후위 운행법(left-right-root)의 알고리즘
자료구조/핵심요약2017. 6. 19. 13:04
- 1. 이진 트리의 표현 방법
- 배열을 이용한 이진 트리의 표현 방법
- 연결 리스트를 이용한 이진 트리의 표현 방법
- 각 노드마다 가변적인 개수의 링크필드(link field)를 갖도록 표현하는 방법
- 기억 장소에 이진 트리 표현 방법(기억 장소에 저장된 트리상태)
- 형제 노드를 연결하는 방법
- 선형 리스트로 이진 트리를 표현하는 방법
- 2. 이진 트리의 상호 변환 방법
- 일반 트리를 이진 트리로 변환하는 방법
- 주어진 일반 트리에서 근 노드와 가장 왼쪽 노드는 그대로 둔다
- 이때 나머지 노드는 근 노드와의 관계를 끊는다.
- 연결이 끊어진 형제 노드들을 가장 왼쪽 노드와 연결한다.
- 45°아래로 기울인다.
- 이진 트리를 일반 트리로 변환하는 방법
- 이진 트리에서 근 노드와 가장 왼쪽 노드는 그대로 둔다.
- 이때 형제 노드끼리 관계를 끊는다.
- 연결이 끊어진 형제 노드를 각 서브 트리의 근 노드와 연결한다.
- 일반 트리를 이진 트리로 변환하는 방법
자료구조/핵심요약2017. 6. 8. 12:33
- 1. 이진트리의 정의
- 공 트리(empty tree)이거나 근 노드와 왼쪽 서브트리(left subtree)와 오른쪽 서브트리(right subtree)라 부르는 2개의 분리된 노드의 유한 집합으로 모든 노드가 2개 이하의 가지를 가진 즉, 각 노드의 차수가 모두 2이하인 트리
- 2. 이진트리(binary tree)의 종류
- 정 이진 트리(full binary tree 또는 포화 이진 트리
- 완전 이진 트리(complete binary tree)
- 엄밀한 이진 트리
- Knuth 이진 트리
- 사향 이진 트리(skewed binary tree, 경사 이진 트리)
자료구조/핵심요약2017. 6. 8. 12:32
- 1. 트리의 정의
- 트리는 자료의 항목(node)들이 가지(edge)로 연결될 수 있게 자료가 조직되는 것
- 다음 조건을 만족하는 하나 이상의 노드(node)들로 구성된 유한 집합 T를 의미
- 2. 트리의 종류
- 자유 트리(free tree)
- 방향성 트리(oriented tree 또는 directed tree)
- 순서 트리(ordered tree)
- 닮은 트리(similar tree)
- 동일 트리(equivalent tree)
