Data Structure

그래프그래프의 정의그래프 G(V, E): 어떤 자료나 개념을 표현하는 정점(Vertex)들의 집합 V와 이들을 연결하는 간선(Edge)들의 집합 E로 구성된 자료 구조그래프는 정점들과 간선들로 정의되며, 정점의 위치 정보나 간선의 순서 등은 그래프의 정의에 포함되지 않는다.-> 같은 그래프라고 하더라도 여러 모양으로 그릴 수 있다그래프의 종류방향 그래프(directed graph, 유향 그래프): 각 간선이 '방향'이라는 속성을 갖는 그래프무향 그래프(undirected graph): 간선에 방향이 없는 그래프가중치 그래프(weighted graph): 각 간선에 가중치(weight)라 불리는 속성을 부여한 그래프ex) 두 도시사이의 거리, 두 물건 사이의 교환 비율, 두 사람 사이의 호감도 등의 다양한..

지금까지 포스팅 한 트리의 종류들 외에도 또 다른 형태의 독특한 트리로 '상호 배타적 집합(disjoint set)'을 표현할 때 사용하는 유니온 파인드(Union-Find) 자료구조가 있다. 이 트리는 지금까지 우리가 구현한 트리와 전혀 다른 용도이며, 전혀 다른 구조를 갖는다.상호 배타적 집합상호 배타적 집합(disjoint set)이란 같은 특성끼리 서로 모이는 집합이 여러 집합이 있는데, 각 집합에서는 공통 원소가 존재하지 않는 집합을 말한다. 그리고, 이렇게 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 구조를 자료 구조가 '유니온 파인드(Union-Find)' 자료구조이다.유니온 파인드 자료구조에는 다음과 같은 연산이 필요하다.초기화: n개의 원소가 각각의 집합에 ..

세그먼트 트리(Segment Tree)트리 자료구조에는 여러 가지가 있지만 그 중, 저장된 자료들을 적절히 전처리하여 그들에 대한 질의들을 빠르게 대답할 수 있도록 하는 트리를 '세그먼트 트리(Segment Tree)'라고 한다. 세그먼트 트리는 흔히 일차원 배열의 특정 구간에 대한 질문을 빠르게 대답하는 데 사용한다. 가장 간단하면서도 흔히 사용되는 예로 구간의 최소치를 구하는 문제인 '구간 최소 쿼리(RMQ, Range Minimum Query)'가 있다. 어떤 배열 A의 부분 구간의 최소치를 구하는 연산을 '여러 번'하고 싶다고 하자. 예를 들어 A = {1, 2, 1, 2, 3, 1, 2, 3, 4}라면 [2, 4] 구간의 최소치는 1이고, [6, 8] 구간의 최소치는 2이다. 이 연산은 구간이 ..

트리 기본 개념도입트리는 계층적 구조를 갖는 자료들을 표현하기 위한 자료 구조로, 현실 세계의 '계층 구조'를 추상화해 표현한다. 이러한 트리는 '특정한 조건'을 지키도록 구성하면, 배열이나 리스트를 사용하는 것보다 같은 작업을 더 빠르게 처리할 수 있기에 탐색형 자료 구조로 많이 쓰인다. 대표적인 예시로 '이진 검색 트리'가 있다. 이처럼 어떤 형태로 트리를 구성하느냐, 자료들을 어떻게 배치하느냐에 따라 다양한 형태의 트리가 있을 수 있으며, 이들을 이용해 다양한 문제를 빠르게 풀 수 있다.기초적인 정의와 용어트리의 구성 요소노드(node): 트리 내에 저장되는 데이터간선(edge): 노드와 노드 간의 연결 관계를 나타내는 선부모(parent) 노드: 두 노드 사이의 관계에서 상위 노드에 해당하는 노드..

큐와 스택, 덱은 일렬로 늘어선 자료들을 표현하는 자료 구조로, 여기에 자료를 넣고 꺼내는 연산을 지원한다. 이때 자료는 특정한 순서로 넣고 특정한 순서로만 꺼낼 수 있다. 사실 이러한 연산은 모두 배열이나 연결 리스트를 이용하면 쉽게 구현할 수 있는 것들이지만, 그럼에도 불구하고 큐와 스택, 덱을 사용하는 이유는 '추상화'를 통해 개발자 간 의사소통을 더 쉽게하고, 더 큰 그림을 보며 프로그램을 설계할 수 있도록 하기 위해서이다. 때문에 이들은 다른 알고리즘을 구현하는 도구로 유용하게 사용된다.큐큐(Queue)는 선입선출(FIFO, First In, First Out) 방식의 자료 구조이다. 즉, 먼저 들어온 데이터가 먼저 나가는 방식으로 처리된다. 큐는 주로 프로세스 관리, 메시지 처리 시스템, 네트..

일렬로 늘어선 같은 종류의 자료 여러 개를 저장하기 위한 가장 기초적인 자료 구조는 '배열(array)'이다. 이 포스팅에서는 배열과 같이 일렬로 늘어선 자료들을 저장하기 위한 자료 구조인 '동적 배열'과 '연결 리스트'에 대해 다룬다. 이 둘은 배열과 비슷하지만, 배열에서는 비효율적이거나 할 수 없는 작업들을 효율적으로 할 수 있도록 도와준다. 두 자료 구조는 서로 다른 특성을 갖고 있으며, 이 책에 나오는 다른 자료 구조들을 구현하기 위해서도 사용되는 중요한 재료이다.동적 배열배열의 문제점은 처음 배열을 선언할 때 배열의 크기를 지정해야 하며, 그 이상의 자료를 집어넣을 수 없다는 점이다. 이 문제를 해결하기 위해 고안된 것이 자료의 개수가 변함에 따라 크기가 변경되는 동적 배열(Dynamic Arr..