본문 바로가기

독학사/자료구조

독학사/자료구조 2022. 5. 13. [자료구조] 힙 | Heap 공유된 코드 - Color Scripter colorscripter.com 힙, 힙트리는 부모 노드가 자식 노드보다 우선순위가 높은 값을 가지고있음이 보장되는 힙구조로 이루어진 트리형태의 자료구조입니다. 이 정의를 가지고 귀납적으로 생각해보면, 루트노드에 담겨있는 값이 항상 우선순위가 가장 높은 값임을 알 수 있습니다. 또, 균형 이진트리 형태를 항상 유지하므로, 값의 삭제 및 삽입을 항상 O(logN)시간복잡도 내에 할 수 있음이 보장됩니다. 이러한 힙트리의 특성을 활용해, 다익스트라(Dijkstra), 힙 정렬(Heap Sort)등을 수행할 수 있습니다. 위 링크는 힙트리를 개인적으로 구현한 소스코드입니다.
[자료구조] 세그먼트 트리 | Segment Tree
독학사/자료구조 2022. 4. 24. [자료구조] 세그먼트 트리 | Segment Tree 세그먼트 트리(Segment Tree)란? 세그먼트 트리는 어떤 구간에 대한 정보(특정 구간에서의 최대/최솟값, 평균, 합 등)를 각각의 노드가 저장하고 있다는 특성을 이용해, O(logN)의 시간복잡도로 구할 수 있게 해주는 자료 구조입니다. 구현의 편의를 위해, 완전 이진트리 형태로 구현하였습니다. 먼저, 전체적인 구조는 아래와 같습니다. 주어진 노드(BaseNodes)의 개수 $N$에 대해 $N < X$를 만족하는 가장 가까운$2^N$값 X에 대해, 세그먼트 트리의 루트노드는 구간 [0,X]까지의 BaseNodes의 세그먼트 값(합)을 의미합니다. 또한, 이 BaseNode의 자식들은 각각 구간[0,X//2),[X//2,X)의 합을 저장하고 있습니다. 이러한 세그먼트 트리의 특성을 잘 이용하면, 우..
[자료구조] 희소 행렬 | Sparse Matrix
독학사/자료구조 2022. 4. 19. [자료구조] 희소 행렬 | Sparse Matrix 희소행렬, Sparse Matrix는 대부분의 값이 0으로 이루어진 행렬을 뜻합니다. 2차원 배열로 희소 행렬을 구현하는 경우, 간단하게 연산을 구현할 수 있지만, 대부분의 공간이 0으로 채워져있어 공간의 낭비가 심합니다. 때문에, 이를 0이 아닌 값으로 채워진 곳의 위치 (행,열,값) 만을 저장하는 방식으로 변형하면, 메모리 공간을 절약할 수 있게 됩니다. 다만, 이로인해 각종 행렬 연산들의 구현이 복잡해지게됩니다.
[자료구조] 연결 리스트를 이용한 큐 / 스택의 구현 | Linked Queue & Stack
독학사/자료구조 2022. 4. 19. [자료구조] 연결 리스트를 이용한 큐 / 스택의 구현 | Linked Queue & Stack 앞서 설명한 링크드 리스트를 이용해, 큐와 스택을 그대로 구현할 수 있습니다. 연결 큐의 구현은 다음과 같습니다. 링크드 리스트의 맨 앞에 위치한 노드를 Front, 맨 뒤에 위치한 노드를 Rear라고 했을 때, Dequeue는 기존 Front의 다음에 있는 노드를 새로운 Front로, Enqueue는 기존 Rear 다음에 새로 추가된 노드를 Rear로 변경하는 방식으로 구현합니다. 연결 스택의 구현은 다음과 같습니다. 링크드 리스트의 맨 앞에 위치한 노드를 Top, 맨 뒤에 위치한 노드를 Bottom라고 했을 때, Pop은 기존 Top의 다음에 있는 노드를 새로운 Top으로, Push는 새로 추가된 노드를 Top으로 변경하고, 포인터를 기존 Top과 연결하는 방식으로 구현합니다.
[자료구조] 연결 리스트 | Linked List
독학사/자료구조 2022. 4. 19. [자료구조] 연결 리스트 | Linked List 연결 리스트는 값을 저장하고 있는 노드가 데이터와 포인터를 가지고 연결되는 방식으로 데이터를 저장하는 자료구조입니다. 1. 단일[Singly] 연결 리스트 # 포인터 공간이 1개 2. 이중[Doubly] 연결 리스트 # 포인터 공간이 2개 3. 원형[Circular] 연결 리스트 # 처음 노드와 끝 노드가 연결됨 단일 연결 리스트는 각 노드가 다음 노드의 위치를 포인터값으로 가지는 형태입니다. 이중 연결 리스트는 각 노드가 이전 노드와 다음 노드의 위치를 포인터값으로 가지는 형태입니다. 원형 연결 리스트는 일반적인 연결 리스트에서, 끝 노드가 다음 노드의 위치를 포인터값으로 가지는 형태입니다. 링크드리스트에서의 노드의 삽입과 삭제는 다음과 같습니다. 삽입의 경우, 기존 노드(Prev Node)의 포인터를..
[자료구조] 스택, 큐,덱 | Stack, Queue, Deque
독학사/자료구조 2022. 4. 18. [자료구조] 스택, 큐,덱 | Stack, Queue, Deque 스택은 "쌓다"라는 의미처럼, 가장 나중에 들어온 값이 가장 먼저 나가는(LIFO,Last In First Out) 형태의 자료구조입니다. 삽입[Push] 위치 : 스택의 끝(맨 뒤) 삭제[Pop] 위치 : 스택의 끝(맨 끝) 스택의 활용 1. 응용 프로그램의 Undo(되돌리기) 기능 2. 웹사이트의 뒤로가기 기능 3. 재귀 함수의 구현 큐는 가장 먼저 들어온 데이터가 가장 먼저 나가는(FIFO,First In First Out) 형태의 자료구조입니다. 삽입[Enqueue] 위치: 큐의 끝(맨 뒤) 삭제[Dequeue] 위치: 큐의 시작(맨 앞) 큐의 활용 1. 프로세스 처리 2. 대기열 처리 3. 너비 우선 탐색의 구현 원형 큐[Circular Queue] 큐는 아래와 같이 Front, Rear라는 변..
[자료구조] 배열 | Array
독학사/자료구조 2022. 4. 18. [자료구조] 배열 | Array 배열은 가장 기본적인 자료구조입니다. 동일한 자료형의 유한한 집합을 말하며, 배열의 각 요소는 0부터 시작하는, 인덱스[index]를 통해 나타냅니다. 배열은 크게 동적배열과 정적배열 [dynamic Array/ static Array]로 구분할 수 있으며, 정적 배열은 반드시 컴파일 시기에 크기를 지정해주어야 하나, 동작 배열은 크기의 변경이 가능합니다. 1차원부터 2,3,... n차원 배열을 구현할 수 있으며, (각 차원별 길이의 곱 * 자료형 크기)만큼의 byte를 필요로 합니다. C언어에서의 배열 선언은 다음과 같습니다. #정적배열 선언 // 자료형 배열이름[크기]; int array[5]; // 길이 5칸짜리 int형 배열을 선언 (20bytes) int array[5] = {0,} // 0으로..
728x90

티스토리툴바