코테 대비겸 공부하면서 정리하는 내용 해시 또한 배열과 비교하면서 생각하면 정말 쉬운 자료구조이다. 지정된 데이터들을 묶어서 저장하는 것은 배열과 같으나, 해당 데이터들의 묶음 내 가리키는 인덱스 값이 배열은 무조건 숫자인 것과 다르게 해시에서는 다양한 형태로 사용이 가능하다. 그림으로 표현하면, 다음처럼 비교된다. 배열 각 element는 선언된 자료형의 데이터만을 가진다. 각 element는 저장된 위치에 따라 0부터 시작해서 순서대로 숫자로 된 인덱스를 가진다. 해시 각 element는 선언된 자료형의 데이터와 함께 미리 선언된 자료형의 key를 가진다. 각 element는 저장된 위치와 무관하게 미리 저장된 key를 통해 접근할 수 있다. 좀 더 파보면, key가 특정한 인덱스로 변환되도록 하는 ..

Binary Tree, 이진 트리는 모든 자식 노드의 개수가 2 이하인 트리를 말한다. 형태에 따라 주로 3가지로 나뉜다. 1. 편향 이진 트리 : 한쪽으로 노드들이 편향돼 불균형한 형태를 띄는 트리 2. 포화 이진 트리 : 모든 부모 노드들이 2개의 자식 노드를 가져 제일 낮은 레벨까지 꽉찬 형태의 트리 3. 완전 이진 트리 : 제일 낮은 레벨을 제외하고 꽉 찼으며, 제일 낮은 레벨에서는 왼쪽부터 노드가 차 있는 트리 일반적으로 코테에서는 완전 이진 트리를 사용한다고 생각하면 좋다. 가장 편리한 형태로 1차원 배열을 사용해 구현할 수 있다. 인덱스에 몇 가지 규칙이 있는데, 1. 루트 노드는 1 2. 부모 노드는 자식 노드 인덱스 / 2 3. 왼쪽 자식 노드는 부모 노드 인덱스 * 2 4. 오른쪽 자식..

트리 자료 구조의 응용이다. 어떤 특정 문자들(소문자 알파벳, 대문자 알파벳 등)만을 다루는 상황에서 그 문자들로 이뤄진 문자열을 빠르게 저장하고 검색하기 위한 자료 구조이다. 특정 문자라고 한 이유가 뭘까? 해당 문자들을 하나씩 노드에 매칭하여 트라이에 저장하기 때문이다. 루트 노드는 NULL로 두고 그 다음 노드들 부터 저장한다. 여기서 각 노드는 각 문자와 매칭되어야 한다. 알파벳의 경우 a=0,b=1,..,z=25로 매칭되어 각 레벨의 자식 노드에 구성되고, 처음에 NULL 포인터로 선언하고 저장할 때 새롭게 객체를 생성해서 저장한다. 그러면 당연히 해당 단계(레벨)에서의 노드가 NULL 포인터가 아니면? 어떤 문자열이든 해당 단계에서 그 노드에 매칭되는 문자를 가진 문자열이 저장되어 있다고 이해..

기본적으로 그래프처럼 구현한다. 이 때 트리의 목적은 부모-자식 노드의 관계를 이용해 탐색 목적에 부합하는 자료구조이다. 이를 위해 단순한 에지리스트로 연결을 표현하기 보다 양방향 인접리스트로 구현하면 좋다. 인접리스트를 구하고 방식에 따라 다르지만 기본적으로 DFS와 BFS를 이용한 탐색이 이뤄진다. 레벨 별로 노드는 분류되고 인접한 두 노드에 대해 위 레벨 노드가 부모 노드, 아래 레벨 노드가 자식 노드로 명명된다. 그리고, 자식 노드가 없는 말단 노드는 자료 구조의 이름이 트리인 것을 생각해 보자. 제일 위 노드 루트 노드로부터 뻗어나온 마지막 말단 노드, 즉 리프 노드이다. 그리고 서브트리는 집합의 부분집합과 유사하게 생각하면 된다. 물론, 트리 형태의 부분이지만 말이다. 트리 형태가 없으면 당연..

모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다. 사이클이 포함되지 않아야 하는 그래프에서 사용할 수 있고, N개의 노드에 대해서 항상 N-1개의 노드를 사용한다. 그래프는 에지리스트로 구현된다. 그리고, 노드끼리 연결됨을 판단해야 하므로 유니온 파인드 알고리즘을 사용한다. 에지리스트를 가중치를 기준으로 정렬한다. 구현 방법 중 하나로는 에지 가중치를 기준으로 우선순위 큐로 구현한다. 사용한 노드가 N-1개가 될 때까지 반복하면서 에지를 pop해 선택하고, 두 노드가 연결되어 있는 지 find 함수로 판단하고 연결되지 않았으면 연결(union 함수)하고 사용한 노드로 개수를 센다. 그리고 사용된 에지들에 대해서 가중치의 합 또한 사용되므로 따로 변수에 합해 가면서 저장한다. 여..