반응형 Computer Science/자료구조10 세그먼트 트리(Segment Tree) 이번에 배워볼 자료구조는 세그먼트 트리(Segement Tree)이다. 최근 코딩 테스트에서 세그먼트 트리를 알고 있다면 조금 더 쉽게 해결할 수 있는 문제들이 나오고 있어서 한번 다뤄보려 한다. 세그먼트 트리는 이해하고 구현하는데 난이도가 상당히 있으며, 아직까지는 굳이 몰라도 된다고 생각하기 때문에 보다가 이해가 안 된다면 과감하게 버리는 것을 추천한다. 세그먼트 트리는 트라이처럼 트리를 활용한 자료구조이다. 세그먼트 트리를 이해하기 위해 사용되는 구간 합 구하기라는 대표적인 문제가 있다. 이 문제를 통해 세그먼트 트리를 이해해 보자. 구간 합 구하기 문제는 N 개의 숫자가 나열돼있을 때 a~b 구간 데이터들의 합을 구하는 문제이다. 구간 합을 구하는 방법은 대표적으로 3가지가 존재한다. 첫 번째는 .. 2021. 6. 30. 트라이(Trie) 이번에 배워볼 자료구조는 트라이(Trie) 자료구조이다. 요즘 코딩 테스트에서 트라이를 이용하여 푸는 문제들이 자주 등장하여 한번 짚고 넘어가려 한다. 트라이를 공부하기 전에 트라이가 왜 필요한지 알아보자. 현재 "abbce", "acd", "bfgaa", abbga", "acde"의 문자열을 포함하는 리스트가 존재한다고 하자. 만약 "bfgaa"라는 문자열이 리스트 내에 존재 유무를 파악하기 위해선 우리는 리스트에 들어있는 문자열들을 비교해봐야 한다. 리스트 내에 찾고자 하는 문자열이 존재하지 않는 최악의 경우 모든 문자열을 비교해야 하기 때문에 O(리스트에 들어있는 모든 문자열의 총 길이) 만큼의 시간 복잡도가 들게 된다. 이는 문자열 간의 불필요한 비교를 계속 진행하기 때문에 상당히 비효율적인 방법.. 2021. 6. 30. 맵(Map) & 셋(Set) JAVA에는 해싱을 활용한 자료구조로 대표적으로 Map, Set, 2개가 존재한다. 이 자료구조들은 이전에 배웠던 자료구조와는 다르게 특수한 형태의 자료구조이며, 굉장히 유용하게 쓰이기 때문에 알아놓으면 좋을 것이다. Map은 키(Key)와 값(Value)의 쌍으로 이루어진 데이터의 집합이다. 순서가 유지되지 않으며, 키는 중복을 허용하지 않고, 값은 중복을 허용한다. JAVA의 Map 인터페이스를 구현한 클래스는 굉장히 많지만 대표적으로 HashMap, HashTable, TreeMap, LinkedHashMap 4가지가 있다. Hashtable HashMap보다는 느리지만 동기화가 지원된다. 키와 값으로 null이 허용되지 않는다. HashMap 중복을 허용하지 않고 순서를 보장하지 않는다. .. 2021. 6. 30. 해싱 : Hashing 대부분의 탐색 방법들은 탐색 키를 저장된 키값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근한다. 이에 반해 해싱은 키값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근하는 방법이다. 키값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(Hash Table), 해시 테이블을 이용한 탐색을 해싱(Hashing)이라 한다. 기존의 탐색 방법들은 정렬의 유무에 따라 O(N), O(log N)이 있었다. 해싱은 이론적으로 O(1)의 시간 안에 탐색이 가능한 방법이다. 해싱은 배열을 사용하여 자료를 저장한다. 배열은 단점도 있지만 원하는 항목이 저장된 위치를 알고 있다면 매우 빠르게 자료를 삽입하거나 꺼낼 수 있는 장점이 있는 자료구조이다. 그렇다면 배열의 .. 2021. 6. 30. 그래프(Graph) 그래프(Graph)는 연결되어 있는 객체 간의 관계를 표현할 수 있는 트리(Tree)와 같이 비선형 구조를 가지는 자료구조이다. 대표적인 예로는 지도가 있다. 그래프는 정점(Vertex)과 간선(Edge)들의 집합으로 구성된다. 수학적으로는 G = (V, E)로 표시한다. 정점(Vertex)는 여러 가지 특성을 가질 수 있는 객체를 의미하고, 간선(Edge)는 이러한 정점들 간의 관계를 의미한다. 정점은 노드라고도 불리며, 간선은 링크라고도 불린다. 그래프는 간선의 종류에 따라 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 구분된다. 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈수 있음을 나타내며 정점 A, B를 연결한 간서은 (A, B)로 표현한다. .. 2021. 6. 30. 우선순위 큐(Priority Queue) 이번에 공부할 자료구조는 우선순위 큐이다. 우선순위 큐는 데이터들이 우선순위를 가지며, 우선순위가 높은 데이터가 먼저 출력된다. 또한, 스택이나 큐도 우선순위 큐를 사용하여 얼마든지 구현할 수 있다. 우선순위 큐는 배열, 연결 리스트 등의 여러 가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 트리에서 언급한 힙(Heap)이다. 힙은 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료 구조이다. 힙은 일종의 반정렬 상태를 유지한다. 이를 활용하여 우선순위 큐를 구현한다. 힙은 삽입, 삭제 연산이 O(log n)의 시간 복잡도를 가질 만큼 훌륭하다. 힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조이다. 간단히 말하면 부모 노드의 키값이 자식 .. 2021. 6. 30. 트리(Tree) 이전까지 공부했던 스택, 큐, 덱은 선형 자료구조라고 말한다. 트리는 선형 자료구조가 아닌 계층적인 구조를 가지는 자료구조이다. 트리는 한 개 이상의 노드로 이루어진 유한 집합이다. 이들 중 하나인 루트(Root)라는 노드를 기준으로 계층적인 구조를 유지하면서 아래로 뻗어나가는 자료구조이다. 트리의 종류에는 여러 가지가 존재하지만 이번에는 자식 노드의 개수가 최대 2개인 이진 트리를 다뤄보겠다. 이진 트리의 정의는 다음과 같다. 공집합이거나 루트와 왼쪽 서버 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진트리여야 한다. 이진 트리는 형태에 따라 다음과 같이 분류할 수 있다. 포화 이진 트리 : 트리의 각 레벨에 노드가 꽉 차 있는 이진 트리 완전.. 2021. 6. 30. 덱(Deque) 덱(Deque)은 double-ended queue의 줄임말로서 큐의 전단(Front)과 후단(Rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 스택(Stack)과 큐(Queue), 2개의 자료구조를 덱(Deque)을 활용하여 구현 및 사용할 수 있다. 전단 삽입(add_front), 삭제(delete_front), 후단 삽입(add_rear), 삭제(delete_rear) 총 4 가지 기본 연산을 가지고 있다. 덱(Deque)은 큐(Queue)를 업그레이드한 자료구조로써 JAVA에선 큐(Queue)처럼 간단하게 라이브러리를 추가하여 별다른 구현 없이 생성할 수 있다. import java.util.Deque; import java.util.LinkedList; Deque "덱 이름" = new .. 2021. 6. 29. 큐(Queue) : FIFO 큐(Queue)는 선입 선출(FIFO : First-In First-Out)의 형식으로 입출력이 일어나는 자료구조이다. 앞서 설명한 스택(Stack)은 동일한 위치에서 삽입, 삭제 연산이 수행되는 반면, 큐(Queue)는 삽입, 삭제 연산이 서로 다른 위치에서 수행된다. 삽입이 일어나는 곳을 후단(Rear)이라고 하고, 삭제가 일어나는 곳을 전단(Front)이라고 한다. 스택(Stack)처럼 삽입(Enqueue), 삭제(Dequeue) 2가지 기본 연산을 가지고 있다. JAVA에선 간단하게 라이브러리를 추가하여 별다른 구현 없이 사용할 수 있으나 일반적으로 LinkedList로 생성한다. import java.util.Queue; import java.util.LinkedList; Queue "큐 이름".. 2021. 6. 29. 이전 1 2 다음 반응형
