Let IT Begin

* Python을 기준으로 합니다 힙 (Heap) - 개념 힙 : 특정 조건을 만족하면서 항상 완전 이진 트리 형태를 가지는 자료구조 힙의 조건 최대힙 : parent 노드가 항상 child 노드 보다 크거나 같다는 조건을 만족하는 힙 최소힙 : parent 노드가 항상 child 노드 보다 작거나 같다는 조건을 만족하는 힙 - 해당 힙 구조를 기반으로 최대/최소값 탐색을 $O(1)$ 내에 처리 가능 이때 힙은 단순히 위의 조건들만을 만족할 뿐, 정렬된 상태는 아님 - 구조적으로는 이진 탐색 트리와 유사하기 때문에 대부분의 연산은 $O(\log n)$ 내에 끝남 - BUT, 힙은 상/하 관계를 보장하고 이진 탐색 트리는 좌/우 관계를 보장한다는 차이가 있음 사용 예시 : 우선순위 큐, 힙 정렬, 다익스트..

* Python을 기준으로 합니다 트라이 (Trie) - 개념 트라이 : 문자열 탐색을 위한 트리 형태의 자료구조 어떠한 문자열 내에서 특정 단어를 검색한다고 하자 - 직관적으로 문자별 단순 비교를 사용하는 경우 $O(n^{2})$의 time complexity를 가짐 - 대신 트라이 구조를 적용하면 $O(n)$ 내에 탐색이 가능함 이때 트라이는 일반적으로 사용되는 이진 트리 형식이 아닌 다진 트리($m$-ary Tree) 형태를 가짐 장점 - 트라이를 구성하면 완전히 일치하는 문자열이 아니라 일부를 생략하더라도 탐색이 가능함 - 문자별로 트리가 만들어지기 때문에 자동적으로 정렬되는 효과가 있음 단점 - 문자의 수가 늘어날수록 메모리를 많이 사용함 - 구현 1. 노드 정의 트라이는 이진 트리가 아니라, ..

* Python을 기준으로 합니다 트리 (Tree) - 개념 트리 : 계층형 구조를 가지는 자료구조로써 순환 (Cycle)이 존재하지 않는 그래프 트리는 재귀적인 특성을 가지는 자기 참조 자료구조임 - 즉, 트리의 모든 노드는 자기 자신을 root로 하는 다른 서브 트리로 대표될 수 있음 트리의 한 노드가 가질 수 있는 child의 수에는 제한이 없지만, 일반적으로 최대 2개의 child 만을 가지는 이진 트리를 자주 활용함 이진 트리 (Binary Tree) 모든 노드가 최대 2개의 child만을 가지고, 왼쪽과 오른쪽의 child가 구별 가능한 트리 이진 트리의 종류 정 이진 트리 : 모든 노드가 0 or 2개의 child를 가지는 트리 완전 이진 트리 : 마지막 level을 제외한 트리의 각 lev..

* Python을 기준으로 합니다 그래프 (Graph) - 개념 그래프 : 노드(Node)와 각 노드를 연결하는 간선(Edge)으로 구성된 비선형 자료구조 서로 연결되어 있는 객체를 다루는 경우 유용 일반적으로 그래프는 연결 조건에 제약이 없지만, 특정한 제약 조건을 가지는 경우 가중치를 통해 표현함 주요 용어 인접 (Adjacent) : 간선으로 연결된 두 노드를 adjacent 하다고 함 차수 (Degree) : 노드에 연결된 간선의 수 경로 (Path) : 간선을 따라 이동하는 경로 - 이때 경로를 구성하는 간선의 수를 경로 길이 (path length)라고 함 그래프의 종류 방향성에 따라 방향 그래프 (Directed Graph) : 두 노드를 연결하는 간선에 방향성이 존재하는 그래프 - 하나의 ..

* Python을 기준으로 합니다 해시 테이블 (Hash Table) - 개념 해시 테이블 : 키와 값을 매핑해 데이터 양에 상관없이 빠른 탐색을 가능하는 자료구조 Python에서는 일반적으로 dictionary 자료형으로 해시 테이블을 활용함 해시 테이블의 탐색은 $O(1)$의 time complexity를 가진다는 장점이 있음 - 키 자체가 해시 함수에 의해 값이 있는 index가 되기 때문 따라서 특정 값을 기준으로 조회를 여러번 해야 하거나, 특정 값과 매핑되는 값의 관계를 활용하는 경우 사용 - BUT, 완전 탐색이나 정렬, 최대/최소 등이 필요한 경우는 배열이 더 유용함 Time Complexity $O(1)$ : 조회, 값 할당, 키 가져오기 `new_dict.keys()`, 딕셔너리 초기화..

* Python을 기준으로 합니다 큐 (Queue), 덱 (Deque) - 개념 큐 : FIFO (First In First Out) 형태의 자료구조 처리해야 하는 작업들을 큐에 쌓음으로써 쉽게 처리할 수 있음 스택과 마찬가지로 삽입과 삭제를 핵심적인 연산으로 가짐 - 배열에서 `append()`나 `pop(0)`를 통해 삽입/삭제를 수행할 수 있지만, `pop(0)`는 $O(n)$을 소모함 - 따라서 큐는 연결 리스트를 통해 구현하는 것이 좋음 큐의 주요 연산 `enqueue()` : 큐의 맨 마지막에 새로운 요소를 추가 `dequeue()` : 큐의 첫 번째 요소를 pop() `isEmpty()` : 큐가 비어있으면 `True` 아니면 `False` 원형 큐 (Circular Queue) 선형 큐(L..