학습개요 그래프에 대해서 할 수 있는 가장 기본적인 연산은 특정 정점이 그래프 내에 있는지 찾는 것입니다. 그러기 위해서는 그래프내의 모든 정점을 빠짐없이 그리고 중복 없이 돌아다녀야 합니다. 그것을 그래프 순회라고 합니다. 그래프 순회에는 두 가지 방법이 있습니다. 15장에서는 깊이 우선 탐색(Depth First Search; DFS)과 너비 우선 탐색(Breadth First Search; BFS)이라는 그래프 순회에 대해 설명합니다. 마지막으로 … Read more
학습개요 수학자 오일러(Euler)가 쾨니히스베르크 다리 문제를 해결하면서 사용한 그래프는 오늘날 가장 강력한 모델링 수단으로 세상의 많은 것들 특히 “관계”를 잘 표현합니다. 이 장은 먼저 그래프 개념을 소개하고 많은 용어를 정의합니다. 용어에 익숙해야 이어지는 내용을 잘 파악할 수 있습니다. 특히 그래프를 수학의 집합 즉 G=(V,E)로 정의하는 것을 잘 이해해야 합니다. 그리고 그래프를 컴퓨터로 다루기 위한 추상 자료형을 … Read more
학습개요 13장은 트리를 다루는 마지막 장입니다. 지금까지 배운 내용을 간략하게 정리해 봅시다. 7장에서 일반적인 트리를 정의하고 이어서 차수가 2인 즉, 자식을 두 개만 갖는 이진 트리를 다루었습니다. 그리고 여러 가지 확장된 이진 트리에 대해 11장까지 소개했습니다. 특히 11장에서는 이진 탐색 트리와 그것을 개선한 트리들에 대해 배웠습니다. 이때까지 우리는 자식을 2개 까지만 허용하는 이진 트리를 줄 … Read more
학습개요 앞에서 학습한 이진 탐색 트리를 장점을 살려서 더 효율적으로 사용하기 위해 만든 멀티웨이 탐색 트리에 대해 학습합니다. 처음으로 이진 탐색 트리를 확장한 것으로 ｍ개 이하의 가지를 가질 수 있는 ｍ원 탐색 트리가 있습니다. 탐색 트리의 제한을 유지하면서 2개 이상(ｍ개 이하)의 자식을 가질 수 있습니다. BS 트리가 2-way 탐색에 해당합니다. m원 탐색 트리는 파일의 인덱스를 … Read more
학습개요 삽입, 삭제 연산을 보다 효과적으로 작업하기 위해 만든 이진 탐색 트리에 대한 정의와 이진 트리와 같이 순회 방법에 대해서도 학습하게 됩니다. 이진 탐색 트리에서는 각 노드를 식별하기 위해서 별도의 이름을 붙여준 키(key)라는 용어를 사용합니다. 노드의 데이터라고 생각해도 됩니다. 정해진 노드()를 기준으로 왼쪽 서브 트리에 있는 모든 노드는 의 킷값보다 값이 작아야 하고, 오른쪽 서브 … Read more
학습개요 차례로 정렬된 데이터 리스트 k를 완전한 순서를 유지하는 하나의 리스트로 만드는 과정을 합병 정렬 이라고 합니다. 이 합병 정렬에 사용하는 트리가 선택트리입니다. 선택트리를 구성하는 방법에는 승자트리와 패자트리가 있습니다. 승자트리는 각 노드가 두 개의 자식노드 보다 더 작은 값을 갖는 완전 이진트리입니다. 작은 값이 승자로 올라가는 토너먼트 경기와 유사하다고 할 수 있습니다. 패자트리는 루트노드 위에 … Read more
학습개요 단순 연결 리스트는 하나의 링크 부분이 존재하고, 각각의 노드는 후행 노드만을 가리키는 구조입니다. 따라서 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 합니다. 이러한 단점을 보완하기 위해, 선행 노드를 가리키는 링크 부분과 후행 노드를 가리키는 링크 부분을 갖는 이중 연결 리스트가 제안되었습니다. 단순 연결 리스트가 사용하지 않는 마지막 노드의 링크 부분을 활용하면서도 프로그램 … Read more