In University ☆ In Bucket Place ☆ Hobby & Study Room ☆

* 신장 트리 - 기존 그래프의 모든 노드를 포함 - 순환이 존재하지 않는 부분 그래프 > 신장트리도 트리의 일종이므로 순환이 존재하면 안된다. - 그래프 탐색을 통해 생성 가능 * 최소비용 신장 트리 - 그래프에서 모든 노드를 방문할 때 가중치의 합이 가장 적은 신장트리 ⓐ Kruskal 알고리즘 - 모든 간선을 가중치 순으로 정렬하여 초기화 - 낮은 가중치를 가지는 간선을 선택하여 트리를 완성 (단, 간선 선택시 순환이 발생하면 안된다.) ex) 1) 초기화 (가중치에 의한 오름차순 정렬) 간선 / 가중치 (1,2) / 1 (2,5) / 2 (2,3) / 3 (3,5) / 4 (1,4) / 5 (4,5) / 6 2) 낮은 가중치의 간선을 차례대로 선택, 이때 순환이 발생하면 안된다. ⓑ Prim 알고..

- 간선을 이용하여 그래프 상의 모든 노드를 한번식 방문하는 것 1) 깊이 우선 탐색 - 선택된 노드와 연결될 노드 중 아직 탐색 되지 않은 노드를 먼저 선택하는 방법 ⓐ 재귀 깊이우선(node n){ visit n; // n방문 print n; // n 출력 for(n에 연결된 모든 노드를 하나씩 선택 = u){ if(u!=visit){ // u가 방문되지 않은 노드라면 깊이우선(u); // u 탐색 시작 } } ⓑ 스택이용 깊이우선(node n){ stack S; visit n; // n 방문 push(S,n); // 스택 S에 n을 push while( !empty(S) ){ // S가 비어 있지 않으면 계속 실행 u = pop(s); // S에 들어 있는 값 Pop > u에 저장 for(u에 연결..

* 특징 - 객체 사이의 연결관계를 표현하는 자료구조 - 표현 능력 우수 > 현실세계의 다양한 문제를 효과적으로 모델링 가능 - 선형구조, 계층구조도 아닌 순환이 존재 * 개념 - 그래프 = 노드 + 간선 / G = (V(G),E(G)) = (V,E) > 노드 : 일반적으로 모델링하려는 스스템을 구성하는 객체 > 간선 : 객체 사이의 관계를 정의 * 그래프의 종류 ⓐ 간선의 특성에 따른 그래프의 종류 1) 무방향 그래프 - 두 노드를 연결하는 간선 방향이 없는 그래프 ex) 무방향 그래프 G1 G1의 노드 : V(G1) = {1,2,3,4} G1의 간선 : E(G1) = {(1,3), (1,2), (2,4), (2,4)} 2) 방향 그래프 = 다이그래프 - 두 노드를 연결하는 간선에 방향이 있는 그래프 ..

*이진 탐색 트리 1. 특징 ⓐ 트리의 모든 노드의 키 값은 유일 해야한다. ⓑ 왼쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 작아야 한다. ⓒ 오른쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 커야한다. ⓓ 왼쪽과 오른쪽 서브트리 모두 이진 탐색 트리이다. - ⓐ~ⓓ의 특징을 만족해야만 이진 탐색 트리라고 할수 있다. - "탐색"이라는 단어가 들어 있을 만큼 자료 탐색에 효율을 두기 위해 만든 자료구조 ( >특정 키 값에 해당하는 노드를 찾는 것이 기본 기능 ) ex) 2. 이진 탐색 트리의 삽입/삭제 ⓐ 삽입 Step 1: 추가되는 키 값이 트리에 존재하는지를 탐색한다.(값의 탐색연산) (같은 키 값이 존재하면 False / 다른 키 값을 가지면 Step 2 실행) Step 2: 추가되는..

*히프 1. 특징 - 루트 노드가 언제나 그 트리의 최대값 혹은 최솟값을 가지는 독특한 구조의 완전 이진 트리 2. 종류 - 최대 히프 : 최대 트리(각 노드의 키 값이 작은 자식 노드의 키 값보다 크가나 같은 트리)의 속성을 가진 히프 ex) - 최소 히프 : 최소 트리(각 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 트리)의 속성을 가진 히프 ex) 3. 히프의 삽입/삭제 연산 - 히프의 삽입/삭제 연산은 연산 뒤에 정렬이 따른다. ⓐ 히프의 삽입 : 히프에 값을 삽입하면, 완전 이진 트리의 특징에 맞는 위치에 값이 삽입되며, 그 뒤에 그 값이 히프로서의 특징을 가질 수 있는 위치로 정렬/이동을 하게된다. ex) 최대 히프에서의 삽입을 예로 들겠다. ⓑ 히프의 삭제 : 삭제 연산은 루트에서 이..

~프로로그~ Microsoft Visual C++ 2010 Express, 즉, 체험판을 열심이 쓰고 있었는데.... 만료 됬다. 다시 다운 받아서 해야된다... ㅠ_ㅠ 귀차니즘에 구현은 둘째치고 트리의 순회에 대해서 알아보도록하자~ ----------------------------------------------------------------------------------------------------- *트리의 순회란? - 트리의 모든 노드를 한 번씩 방문 하는 것 *특징 - 이진트리의 최대 차수가 2이기 때문에 현재 방문중인 V(Visit)노드 왼쪽자식노드 L(Left node), 오른쪽자식노드 R(Right)로 나눠 일반화 하여 생각할수 있다. *트리의 순회 종류 ⓐ 전위 순회 - 순회 순..

* 이진 트리 > 모든 노드의 차수가 2이하인 트리 > 종류 : 포화 이진트리, 완전 이진트리, 편향 이진트리 ⓐ 포화 이진 트리 : 모든 레벨의 노드가 꽉 차 있는 이진 트리 : 저장 가능한 총 노드의 개수 > 2^h - 1 // h : 트리의 높이 = 같은 높이의 이진 트리에서 가질 수 있는 가장 많은 노드의 개수 ⓑ 완전 이진 트리 : 마지막 레벨에서 왼쪽 부터 오른쪽으로 노드가 채워져 있는 트리, 중간에 빈 노드가 있어서는 안된다. ⓒ 편향 이진 트리 : 같은 높이의 이진 트리중 최소 개수의 노드 개수를 가진 트리 : 오른쪽 or 왼쪽 서브 트리만 가지는 것 ------------------------------------------------------------------------------..

* Tree 트리구조 ⓐ 특징 > 노드와 간선의 집합 > 계층 구조 - 트리를 구성하는 노드의 관계가 부모-자식이라는 의미 - 특정 부모노드 하나에 여러개의 자식 노드들이 연결되는 구조 > 트리를 구성하는 부모-자식 노드의 관계가 1:1 이 아님! → 비선형구조! > 특정 노드 하나가 여러개의 자식을 보유 가능하나, 각 노드는 단 하나의 부모노드만을 가질 수 있음. ⓑ 용어정리 > 노드의 구성 - 노드 : 일반적으로 모델링하는 자료구조/시스템의 객체 - 간선 : 노드 사이의 연결선(부모-자식 관계를 정의해줌) > 노드의 종류 - 루트 노드 : 트리의 첫번째 노드 / 부모노드가 없는 노드 - 단말 노드 : 자식 노드가 없는 노드 - 내부 노드 : 자식 노드가 있는 노드 / 모든 노드 집합 - 단말 노드 집..

~프로로그~ 어느 덧 책에서 재귀라는 단어가 나오게 되었습니다. 재귀라는 것은 전에 포스팅한 글 보다 잘쓰기가 힘들거 같아서 설명은 링크로 하고... 하노이 탑에 대해서 설명해볼까합니다. 재귀호출에 대한 설명 글 보기! 자 그럼 S t A r T !! ------------------------------------------------------------ 하노이 탑에 대해서 일단 설명 해보겠습니다. 위 그림에서 원판이 있는 막대를 A 중앙을 B 가장 왼쪽을 C 막대로 지칭하도록 하겠습니다. 일단, 목표는 간단합니다. A막대에서 C막대로 모든 원판을 크기 순서대로 옮기면 됩니다. 이때 제약 사항이있죠~ ⓐ 한번에 하나의 원판만 이동 가능!! ⓑ 맨 위에 있는 원판만 이동 가능!! ⓒ 크기가 작은 원판 ..

스택의 응용 분야 ① 산술 연산 : 중위 연산 - * 나 / 가 + 와 -보다 우선순위가 높은것을 감안하여 연산자를 우선 스택에 저장하고 우선순위가 더 높은것이 나중에 들어오면 하나식 빼는 과정을 가지고 있습니다. ② Subroutine call과 return(서브루틴의 복귀 번지) 주프로그램에 의해 호출되는 프로그램. (C로 작성한 프로그램에서 함수를 사용했을때 main()함수에서 a();라는 함수를 호출했을때 현재 가지고 있는 번지 수를 기억하였다가 a(); 함수가 종료되면 스택에 저장되어있는 주소를 꺼내어 다시 되돌아 갈때 쓰입이다 ) ③ 인터럽트 처리 현재 프로세스가 메모리를 할당받어 실행하고 있는도중 인터럽트가 발생하면 현재 프로세스 정보를 스택에 저장하고 인터럽트 처리후에 다시 사용합니다 ④ ..