목차 그래프 그래프순회 -DFS -BFS 백트래킹 그래프 순회 문제 -섬의 개수 -순열 만들기 그래프 이론을 배우는 이유 그래프 이론이 사용되는 곳 -인터넷 망 운영 -코로나 감염 경로 조사 -소셜 네트워크 -도로 -상하수도 -단백질 상호작용 -신경망 그래프 그래프(graph,G) 그래프는 노드들과 노드들을 연결하는 엣지들의 집합 - 그래프는 G={V,E} 로 표현 노드(node,vertex,정점) 객체를 개념적으로 나타낸 것 v: 노드의 집합 엣지 (edge.link,간선) 노드들의 관계를 개념적으로 나타낸 것 E: 엣지의 집합 방향을 가질 수 있음 가중치를 가질 수 있음 그래프용어 방향 그래프 엣지에 방향이 있는 그래프 -화살표 방향으로 이동 가능 -노드 A에서 노드 B로 가는 간선을 로 표현 무방향..

문제1 insert_to_subtree(), delete_in_subtree(), find_in_subtree(), preorder(), levelorder() 메소드를 완성하시오. 결과 | ┌──── 11 | ┌──── 10 └──── 9 | ┌──── 8 | ┌──── 7 | | └──── 6 └──── 5 | ┌──── 4 | | └──── 3 └──── 2 └──── 1 Inorder: 1 2 3 4 5 6 7 8 9 10 11 Preorder: 9 5 2 1 4 3 7 6 8 10 11 Postorder: 1 3 4 2 6 8 7 5 11 10 9 Level order: 9 5 10 2 7 11 1 4 6 8 3 최소노드키: 1 최대노드키: 11 탐색: I E J B G K A D F H C 5..

정렬(sorting) -이름, 학번, 학점등의 키(key)를 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어 놓는 작업 오름차순 정렬 -값이 작은 데이터가 앞쪽에 오는 순서로 정렬 내림차순 정렬 -값이 큰 데이터가 앞쪽에 오는 순서로 정렬 안정적인 (stable) 정렬이란? -키값이 같은 원소들에서 정렬 전의 순서가 정렬한 후에도 유지되는 것 선택 정렬 (selection sort) -가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하여 정렬하는 알고리즘 선택 정렬 구현 시간복잡도 •최선: O(N2) •평균: O(N2) •최악: O(N2) 장점 비교 정렬 알고리즘들 중에서 교환 횟수가 가장 작임 단점 불안정 정렬 같은 키를 가지는 원소의 순서가 정렬 후 뒤바뀜 효율성이 낮아 거의 활..

깊이우선탐색(Depth-first search,DFS) -서브트리를 재귀적으로 순회 루트 , 왼, 오 inorder():중위순회 1.왼쪽서브트리를 중위순회 2.루트를 방문 3.오른쪽 서브트리를 중위순회 preorder(): 전위순회 1.루트를 방문 2.왼쪽서브트리를 전위순회 3.오른쪽 서브트리를 전위순회 postorder(): 후위순회 1.왼쪽서브트리를 후위순회 2.오른쪽서브트리를 후위순회 3.루트를 방문 self.inorder(sroot.left)

노드 삭제 -노드 삭제는 삽입과정보다 복잡함 이진탐색트리의 노드 삭제는 3가지 경우를 가짐 1.자식 노드가 없는 노드를 삭제하는 경우(가장 간단) 2.자식노드가 1개인 노드를 삭제하는 경우(간단) 3.자식노드가 2개인 노드를 삭제하는 경우(복잡) 자식 노드가 없는 노드를 삭제하는 경우 1. 삭제될 노드 탐색 2. 부모노드를 이용하여 삭제 자식 노드가 1개인 노드를 삭제하는 경우 삭제할 노드의 자식노드를 삭제할 노드의 부모노드와 연결시킨다. 자식 노드가 2개인 노드를 삭제하는 경우 1.삭제할 노드의 왼쪽서브트리에서 키값이 가장 큰 노드 탐색 -이 노드를 왼쪽최대노드 라고 하자 2.왼쪽 최대 노드의 키와 값을 삭제할 노드에 복사한다 -이떄 삭제할 노드가 삭제 된다. 3. 왼쪽 최대 노드를 삭제한다 -재귀적 ..

이진탐색트리를 배우는 이유 이진탐색트리가 널리 활용되는이유? -구조가 단순하다 -쉽게 노드의 키들의 정렬된 결과를 얻을 수 있다. -이진 검색과 비슷한 방식으로 아주 빠르게 탐색 할 수 있다. 이진탐색트리(binary search tree)란? 이진탐색(binary search)의 개념을 트리 형태의 구조에 접목한 자료구조 이진탐색트리의 조건 각 노드 키가 왼쪽 서브트리에 있는 키들보다 크고, 오른쪽 서브트리에 있는 키들보다 작다. 일반적으로 키값이 같은 노드는 복수로 존재하지 않아야한다. 이진참색트리의 구조 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져있다. 루트의 왼쪽 서브트리와 오른쪽..