Segment Tree 구간 트리(Segment Tree)는 저장된 자료의 특정 구간 질의를 빠르게 대답하기 위해 저장된 자료를 전처리한 트리를 말한다. 흔히 구간 트리는 일차원 배열의 특정 구간 질의를 빠르게 대답하는데 사용된다. 예를 들어 [1, 7, 5, 3, 2] 라는 일차원 배열이 있을 때 [1, 2] 구간의 최소치를 찾는 연산을 해야 한다. 이를 연산하는 간단한 방법은 구간의 시작부터 끝까지 순회하면서 최소치를 찾으면 되며 시간 복잡도는 O(N)이 된다. 반면 구간 트리를 한 번 만들어두면 위 연산을 O(log N)으로 할 수 있다. 구간 트리의 핵심 아이디어는 배열 구간에 대한 이진 트리를 만드는 것이다. 구간 트리의 노드는 구간을 표현한다. 루트 노드는 항상 배열의 전체 구간 [0, n-1..
최단 경로 최단 경로 문제(shortest path problem)는 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로를 찾는 문제로, 그래프 관련 문제 중에서 최단 경로 문제가 많다. 최단 경로 문제를 해결하기 위해서는 그래프가 어떤 그래프인지 파악하고, 그에 맞는 최단 경로 알고리즘을 적용해야한다. 최단 경로 알고리즘은 최단 경로를 구성하는 정점들의 목록을 구해 주는 것이 아닌 최단 경로의 길이를 찾아줄 뿐이라는 점에 유의해야한다. 실제 경로를 계산하기 위해서는 BFS에서 그랬듯이 탐색 과정에서 별도의 정보를 저장하고, 이것으로부터 실제 경로를 찾아내야한다. 가중치가 없는 그래프에서는 BFS로 최단 경로를 구할 수 있다. 여기서의 최단 경로는 경로의 길이가 가장 짧은 경로를 말한다. 가중치가 있는..
Binary Search Tree (BST) 데이터 탐색 알고리즘으로 이진 탐색 알고리즘이 있다. 탐색 범위를 반으로 줄이면서 탐색하는 알고리즘이다. 정렬된 배열에서 이진 탐색 알고리즘을 적용해 O(log N)의 시간복잡도로 탐색할 수 있지만 배열의 원소를 추가, 삭제하는데 O(N)의 시간복잡도가 든다는 단점이 있다. 이를 극복하기 위해 BST를 사용한다. 균형 잡힌 BST(BBST)라면 탐색, 삽입, 삭제의 시간 복잡도를 O(log N)으로 만들 수 있다. BST는 이진 트리에 속하며 이진 탐색을 목적으로 하는 트리다. BST의 모든 노드는 아래의 규칙을 갖는다. 각 노드의 왼쪽 서브 트리에는 해당 노드의 원소보다 작은 원소를 가진 노드들이, 오른쪽 서브 트리에는 해당 노드의 원소보다 큰 원소를 가진 ..
트리 트리는 계층 구조를 표현하는 자료구조이다. 트리는 다양한 목적으로 사용되어 다양한 종류의 트리들이 등장했다. 현실 세계 계층 구조 표현 이진 검색 트리 힙 세그먼트 트리 유니온-파인드 트라이 등등 트리 용어 node(노드) : 트리 구성 요소 edge(간선) : 노드와 노드를 연결한 선 parent : 두 노드가 간선으로 연결되었을 때 상위 노드 child : 두 노드가 간선으로 연결되었을 때 하위 노드 sibling : 같은 부모를 가지는 자식 노드들 ancestor : 부모 노드와 그 부모 노드의 상위 노드들 descendant : 자식 노드와 그 자식 노드의 하위 노드들 root : 부모가 없는 최상위 노드 leaf : 자식이 없는 노드 Internal : 리프 노드가 아닌 노드 depth :..
신장 트리 (Spanning Tree) n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리, 즉 그래프의 모든 정점을 가장 적은 개수의 간선으로 연결한 그래프 최소 신장 트리 (Minimum Spanning Tree) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 신장 트리, 최소 신장 트리를 만드는 대표적인 알고리즘에는 Prim 또는 Kruskal 알고리즘이 있다. 보통 최소 신장 트리를 줄여서 MST라고 부른다. Kruskal 알고리즘 1. 최초, 모든 간선을 가중치 순으로 오름차순 정렬 1-1. 간선 리스트를 만든다. 1-2. 만든 간선 리스트를 가중치 순으로 오름차순 정렬한다. 2. 간선을 하나씩 확인해 해당 간선이 사이클을 발생시키는지 확인 (초기..
LinkedList LinkedList는 리스트의 한 종류이다. 노드들이 물리적인 메모리 주소상으로 연속되어 있지 않지만 노드가 다음 노드로 갈 수 있는 포인터를 가짐으로써 노드들이 논리적으로 연속되어 있다. 연결 리스트에서 하나의 원소를 노드라고 한다. 노드는 데이터 필드와 링크 필드로 나뉘는데 데이터 필드는 리스트에 저장될 원소의 값을 저장하며 링크 필드는 다음 노드의 참조값을 저장한다. 연결리스트의 가장 큰 장점은 원소의 삽입, 삭제의 시간복잡도가 O(1)이다. 때문에 원소의 삽입, 삭제가 빈번하면 연결 리스트 사용을 고려할만하다. 단점은 특정 위치의 원소를 찾아가는 시간 복잡도가 O(N)이다. 배열(배열 기반 리스트)와 달리 랜덤 엑세스가 안되기 때문이다. 연결 리스트의 종류 연결 리스트는 총 세..
List 리스트는 데이터를 일렬로 저장하는 선형 자료구조이다. 리스트는 배열 기반 리스트(동적 배열)와 연결 리스트로 나뉜다. 배열 기반 리스트 : 노드들이 물리적인 메모리 주소상으로 연속되어 있다. 연결 리스트 : 노드들이 물리적인 메모리 주소상으로 연속되어 있지 않지만, 노드 안에는 다음 노드로 갈 수 있는 포인터가 있다. 또한 리스트로 비선형 자료구조를 표현할 수 있다. 연결 리스트로 트리 구현, 배열로 그래프 구현, 배열로 이진 트리 구현 등이 그 예시이다. 배열 기반 리스트 배열의 가장 큰 문제점은 한번 할당받은 후 배열의 크기가 변하지 않는다는 점이다. 이를 극복하기 위해 배열 기반 리스트를 사용한다. 배열 기반 리스트는 배열에 노드를 저장하며 배열 크기를 조절하는 resize 연산을 추가했다..
브루트포스 문제를 풀 때 순열, 조합 등으로 원소 인덱스를 뽑는 과정이 필요하다. 그러면 인덱스가 이차원(x,y)일 경우 어떻게 선택할 수 있을까? 아래의 방법으로 쉽게 선택할 수 있다. 1. 4X3의 배열일경우 (0,0)은 0으로 (3,4)는 11로 표현할 수 있다. 즉 이차원 인덱스(x,y)를 하나의 정수로 표현할 수 있다. 이 정수로부터 컬럼 크기로 나눈 값이 row, 컬럼 크기로 나머지 연산을 한 값이 col이 된다. 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net import java.util.*; im..
