자료구조12 [자료구조] 그래프 (Graph) 그래프: 연결된 객체들 사이의 관계를 표현할 수 있는 자료구조 객체들이 서로 복잡하게 연결되어 있는 구조를 표현할 때 이러한 구조를 표현할 수 있는 가장 훌륭한 논리적 도구가 그래프이다. 지하철 노선도: 가장 대표적인 그래프의 예시 항공 노선도 전기회로 그래프는 정점(Vertex)과 간선(Edge)로 이루어진다. 정점 A와 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현하며, 그래프를 수학적으로 표현하고 싶다면 G = (V, E)와 같이 나타낼 수 있다. 그래프의 종류 1) 무방향 그래프: 간선에 방향이 표시되지 않은 그래프. 따라서 하나의 간선은 양방향으로 갈 수 있는 길을 의미하므로 (A, B)와 (B, A)는 동일한간선이다. 2) 방향 그래프: 간선에 방향이 존재하는 그래프. 간선은 화.. 2024. 1. 8. [자료구조] 탐색 트리 (Search Tree) 탐색 트리: 탐색을 위한 트리 기반의 자료 구조 일상생활이나 컴퓨터에서 탐색은 매우 중요한 역할을 한다. 우리가 원하는 데이터를 찾을 때 반드시 거쳐야 하는 과정이 탐색이다. 앞서 이진 탐색을 배웠지만, 레코드의 삽입과 삭제가 빈번히 일어나는 테이블에 대해서는 그다지 효율적이라고 말할 수 없었다. 해싱을 사용하면 매우 효율적이지만 메모리를 많이 사용할 뿐더러 해시 충돌과 오버플로 문제를 처리해야 하므로 매우 복잡하다는 단점이 있다. 그래서 고안된 방안이 탐색에 트리 구조를 이용하는 것이다. 즉 탐색을 위한 이진 트리 기반의 자료 구조가 고안되었는데, 이를 이진 탐색 트리라고 한다. 이진 탐색 트리의 특성 모든 노드는 유일한 키를 갖는다. 왼쪽 서브 트리의 키들은 루트의 키보다 작다. 오른쪽 서브 트리의 .. 2024. 1. 8. [자료구조] 트리 3. 힙 트리 힙 트리: 여러 개의 값들 중에서 가장 크거나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조 힙은 최대 힙과 최소 힙으로 나눌 수 있으며, 모든 힙 트리는 아래의 두 성질을 만족해야 한다. 모양 성질: 완전 이진 트리의 모양을 나타내야 한다. 힙 성질: 최대 힙 또는 최소 힙의 특성을 갖는다. 최대 힙의 특성: 각 노드에 저장된 값은 그 자식 노드에 저장된 값보다 크거나 같다. 최소 힙의 특성: 각 노드에 저장된 값은 그 자식 노드에 저장된 값보다 작거나 같다. 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 이번에는 최대 힙을 가지고 다뤄보도록 하겠다! 최대 힙의 구현 최대 힙.. 2024. 1. 8. [자료구조] 트리 2. 이진 트리의 활용 앞서 이진 트리의 개념과 표현법에 대해 간략하게 공부했다. 그럼 이렇게 이진 트리를 만들고 난 후, 어떻게 트리의 데이터에 접근할 수 있을까? 바로 순회를 이용하는 것이다. 순회란 트리에 속하는 모든 노드들을 한 번씩 방문하여 트리의 데이터에 접근하는 것으로, 트리에서 가장 기본적인 연산이다. 이진 트리의 표준 순회에는 전위 순회, 중위 순회, 후위 순회 3가지 방법이 있다. 이들은 루트의 왼쪽 서브 트리, 오른쪽 서브 트리를 각각 어떤 순서로 방문하느냐에 따라 구분된다. 루트를 방문하는 작업을 V, 왼쪽과 오른쪽 서브 트리를 방문하는 작업을 각각 L과 R이라고 할 때, 각 순회들을 구현하는 방법들은 아래와 같다. 전위 순회: VLR 중위 순회: LVR 후위 순회: LRV 순회의 구현 def preord.. 2024. 1. 8. [자료구조] 정렬 2. 간단한 정렬들 앞서 정렬의 개념에 대해 간략하게 설명했다. 이제 매우 간단한, 그러나 비효율적인 정렬을 쉽게 알아본다.1) 선택 정렬 (Selection Sort)선택 정렬은 리스트에서 가장 작은 숫자를 선택해서 앞쪽으로 옮기는 방법을 반복하여 정렬하는 방식이다.전체 숫자 리스트를 아직 정렬되지 않은 오른쪽 리스트와 정렬이 완료된 왼쪽 리스트로 분류하는데, 맨 처음에는 모든 숫자가 오른쪽 리스트(정렬되지 않은 상태)에 담겨져 있다.즉 오른쪽 리스트에서 가장 작은 숫자들을 계속해서 선택하여 왼쪽 리스트에 차례로 담는 방식을 반복하여 정렬하는 것이다!def printStep(arr, val): print(" Step %2d = " % val, end='') print(arr)def selection_sort(A.. 2024. 1. 7. [자료구조] 정렬 1. 정렬이란? 우리가 효율적으로 데이터를 저장하고 관리하기 위해서 필요한 것 중 하나가 정렬이다. 정렬은 순서를 기준으로 오름차순 정렬과 내림차순 정렬으로 나눌 수 있는데, 오름차순 정렬은 작은 순서대로 정렬하는 것이고 내림차순 정렬은 큰 순서대로 정렬하는 것이다. 정렬시켜야 될 대상을 보통 레코드(record)라고 부르며, 레코드는 여러 개의 필드(field)로 이루어진다. 여기서 정렬이 기준이 되는 필드를 키(key) 또는 정렬 키(sort key)라고 한다. 예를 들어 수많은 경주마(레코드)들을 정렬하고 싶은데… 경주마들은 각각 이름, 키, 나이, 품종 등(필드) 가지각색의 속성들을 가지고 있다 이 중 나는 이름을 기준으로 정렬하고 싶다면, 이름이 정렬 키가 되는 것이다. 정렬 장소에 따른 분류 내부 정렬: 모든.. 2024. 1. 7. 이전 1 2 다음 반응형
