전체 글
-
[DS] Binary Search Tree:: 이진 탐색 트리개발자 ON/Data Structures 2020. 12. 29. 17:32
Terminology - 트리: 다음 셋 중 어떤 하나의 조건이라도 만족하는 Undirected Graph 를 트리라 칭한다. 1. 사이클을 가지지 않는 그래프 2. N개의 노드와 N-1개의 엣지를 가지는 그래프 3. 두 개의 노드가 오직 하나만의 엣지로 연결된 그래프 - 루트노드 (Root Node): 트리의 최상단에 위치한 노드로 사실 상 어떠한 노드도 루트 노드가 될 수 있다. (아래 그림 참조) - 부모 노드/자식 노드 (Parent Node/ Child Node): 한 노드를 기준으로 한 단계 상위에 있는 노드를 부모 노드, 한단계 하위에 있는 노드를 자식 노드라고 칭한다. *루트 노드는 주로 자기 자신을 부모 노드로 가진다. (구현에 따라 다름) - 리프 노드 (Leaf Node): 최하위에 ..
-
[DS] Union Find::서로소 집합 자료구조개발자 ON/Data Structures 2020. 12. 29. 15:42
Union Find 자료구조란? 하나 혹은 더 많은 서로소 집합(disjoint sets)들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. *서로소 집합이란 공통 원소가 없는 집합을 칭한다. 기본연산 - Find(_item_) : 원소가 속한 집단의 "대표" 원소를 반환하는 연산으로 두 원소가 같은 집단에 속해있는지 확인하기 위해 사용된다. - Union(_item1_, _item2_) : 두 개의 집합을 하나의 집합으로 합치는 연산. 활용 알고리즘 - Kruskal's Minimum Spanning Tree - Grid Percolation - Network Connectivity - Least Common Ancestors in Tree 등 시간 복잡도 Construction O(n..
-
[DS] Priority Queue / Heap개발자 ON/Data Structures 2020. 12. 22. 20:31
Prioriry Queue란? : 일반 Queue와 비슷하지만 각 원소들이 우선순위(priority)를 가지는 ADT(Abstract Data Type)이다. FIFO(First-In-First-Out)이 아니라 우선순위에 따라 원소들이 제거된다. 최우선순위의 원소를 제거하는 것을 poll()이라고 한다. Heap이란? : Priority Queue의 자료구조로 Heap Invariant를 만족하는 트리를 뜻한다. Priority Queue의 구현 자료구조 중 하나일 뿐 모든 Priority Queue가 Heap은 아님을 기억하자. *Heap Invariant: 모든 노드에 대해서 A가 B의 Parent Node라면 A의 값이 B보다 작거나 크다. 값이 큰 경우를 Max Heap이라고 하고 작은 경우를 ..
-
[DS] Stack/Queue개발자 ON/Data Structures 2020. 12. 22. 15:10
Stack이란? : 제한적으로 접근할 수 있는 나열구조로 목록의 한쪽 끝에서만 접근이 가능하다. 한쪽 끝으로 밀어넣는 것을 Push(), 그리고 한쪽 끝에 있는 원소를 빼는 것을 Pop()이라고 하며 LIFO (Last-In-First-Out) 구조를 가진다. 일반적으로 블록을 쌓는 것을 생각하면 간단하다. 기본 두 연산자 외에 Peek()이라는 함수를 통해 가장 끝에 있는 원소를 제거가 아닌 확인만 하는 함수도 있다. 스택은 활용도가 특히 높은 자료구조 중 하나인데 컴퓨터 구동에 기반이 되는 메모리 관리에도 스택이 사용되며 각종 알고리즘에서도 많이 활용된다. 모두가 아는 Stack Overflow의 Stack도 이 스택이다. 예시: DFS DFS란 Depth First Search의 약자로, 그래프에서..
-
[DS] Linked Lists개발자 ON/Data Structures 2020. 12. 22. 13:10
Linked Lists란? : 순차적인 노드들의 리스트로 각 노드는 데이터와 다음 노드에 대한 정보를 가지고 있다. 그렇기에 Array가 연속적인 메모리 블록이라고 했을때, Linked List는 비연속적으로 메모리 블록들이 연결되어 있다고 볼 수 있다. 구성 요소들은 다음과 같다. Node: 데이터와 포인터의 집합 Pointer: 다음 노드로의 참조값 Head: Linked List의 첫번째 노드 Tail: Linked List의 마지막 노드 Singly Linked Lists : 순방향으로만 연결된 Linked List 장점: 더 적은 메모리 사용 및 쉬운 구현 단점: 지나간 노드로 다시 갈 수 없음 (헤드노드에서 다음 노드로는 갈 수 있지만 다시 헤드노드로는 돌아갈 수 없음) Doubly Linke..
-
[DS] Array개발자 ON/Data Structures 2020. 12. 22. 11:54
Array는 가장 기본이 되는 자료구조로 Static Array와 Dynamic Array로 나눌 수 있습니다. Static Array : n개의 원소를 지닌 고정된 크기의 컨테이너로 [0, n-1]까지 인덱스화 되어 있다. 일반적으로 우리가 흔히 아는 메모리의 일정 부분을 할당한다고 보면 된다. *인덱스화가 되어 있다는 말은 인덱스라는 숫자로 컨테이너의 각 슬롯에 접근할 수 있다는 뜻이다. 컴퓨터에서 이루어지는 계산, 모니터출력, 게임등 모든 행위는 연산이며, 이러한 연산을 위해서는 메모리와 CPU가 필요하다. 그렇기 때문에 메모리를 할당받는 Array 자료구조는 기초가 되는 자료구조라고 할 수 있다. Dynamic Array : Static Array가 n으로 고정된 크기의 컨테이너였다면, Dynam..
-
[DS] 자료형을 들어가기 전에.개발자 ON/Data Structures 2020. 12. 22. 10:45
자료구조란? "효율적인" 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 이는 빠르고 강력한 알고리즘 설계의 기본이 되며 적합한 자료구조는 데이터의 효율적 관리는 물론 코드 자체의 품질을 올리는 요소가 되기도 한다. Abstract Data Types (ADT) ADT는 자료구조의 추상화로 어떻게 구현할건지나 어떤 프로그래밍 언어로 작성할지에 대한 디테일을 제외한 자료구조가 따라야 하는 개념, 혹은 인터페이스를 뜻한다. 비교하자면 다음 표와 같다. ADT Data Structure 자동차 승용차, 골프카트, 트럭 List Dynamic Array, Linked List Queue Linked List based Queue, Stack based Queue Map Tree Map, Ha..
-
[방법론] Divide and Conquer :: 분할정복개발자 ON/Algorithm 2020. 10. 21. 21:42
정의 분할정복 (Divide and Conquer)이란 가장 기초적인 알고리즘 중 하나로 하나의 문제를 작은 여러개의 문제로 쪼갠 후 재귀적으로 각 문제를 해결한 후 이를 다시 합쳐 원래 문제를 해결하는 방법을 뜻한다. 문제는 주로 2개 이상의 하위 문제로 나뉘어 진다. (일반적으로 아는 병합정렬처럼 문제를 무조건적으로 2개로 나누지는 않는다.) 분할 정복 알고리즘의 수행시간은 주로 점화식을 푸는 것과 연결되는데 이는 분할정복이 재귀적으로 하위 문제를 호출하기 때문이다. 실제로 우리가 접하는 많은 문제는 이미 다항식 시간내에 해결할 수 있는 P 문제이며 바로 떠올릴 수 있는 무작정 다 해보는 Brute-Force 알고리즘이 이미 "효율적"일 수 있다. 분할정복은 주로 그러한 문제들에 대해서 더 작은 다항..