알고리즘/이론

세그먼트 트리에 대한 글은 이미 많습니다. 심지어 다들 구체적으로 설명해주고 계십니다. 그런데 세그먼트 트리를 단지 구간합 트리라고 알고 계시는 분들이 생각보다 많이 계신 이유로 오해를 정정하고자 포스팅해보겠습니다. 세그먼트 트리가 없다면? 세그먼트 트리(구간 트리)는 주어진 쿼리에 대해서 빠르게 응답하기 위한 자료구조입니다. 배열 A가 주어져있고 A의 start~end 구간까지의 합을 구하려고 합니다. for문으로 answer+=A[i]를 돌리면 되겠죠. 그런데 만약 이 구간내 값이 변동이 된다면 어떨까요?? 총 M번 반복한다고 가정했을때, 수정 연산(O(1))+ 합산 연산 = O(NM)의 시간복잡도가 발생합니다. 세그먼트 트리 도입 여기에 세그먼트 트리를 사용한다면 어떻게 변할까요?? 수정 연산 = ..

이진 트리 계층 구조인 트리의 자식이 left, right 둘로 이루어진 형태를 이진 트리라고 합니다. 이진 트리를 구성하고 dfs와 bfs로 탐색하는 예제를 작성하는 것이 이 포스팅의 목표입니다. 그림에서 초록 원들을 각각 노드라고 부릅니다. 각 노드들이 가지를 뻗듯이 연결되어 있으니(같은 이유로 트리라는 이름이 붙여졌습니다.) Node의 값과 연결된 노드들의 정보가 필요하겠죠. 즉 Node 클래스에는 다음과 같은 필드가 필요합니다. public class Node{ int value; Node left; Node right; ... } 생성자는 직접 만들어보세요. DFS DFS는 깊이 우선 탐색이라고 부릅니다. 트리에서의 깊이는 맨 위에 있는 노드(루트 노드)로 부터 특정 노드까지의 길이를 깊이라고 ..

신장 트리란 그래프 중 모든 정점이 간선으로 연결되어 있되, 간선간의 사이클이 없는 그래프 최소 비용 신장 트리 각 간선에 비용(가중치 합)이 있을때 최소화 하는 신장트리를 말함 크루스칼 알고리즘 1. 간선들을 가중치의 오름차순으로 정렬 2. 사이클을 형성하지 않는 간선 선택 3. 해당 간선을 현재의 집합에 추가 즉 간선을 중심으로 탐색을 합니다. 아래는 이해하기 쉽게 gif 이미지를 가져왔다. be간선을 연결하려고 하면 이는 사이클을 형성하기에 제외하는 것을 볼 수 있다. MST의 대표 알고리즘인 프림 알고리즘과 크루스칼 알고리즘을 비교하면 아래와 같다. 크루스 알고리즘 프림 알고리즘 간선을 기반으로 하는 알고리즘 정점을 기반으로 하는 알고리즘 전단계에서 만들어진 신장트리와는 상관없이 무조건 최저 간선..

그래프(Graph)의 종류 무방향 그래프 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. (A, B)는 (B, A) 동일 방향 그래프는 는 다름 간선에 방향성이 존재하는 그래프, A -> B로만 갈 수 있는 간선은 로 표시한다. 가중치 그래프 간선에 비용이나 가중치가 할당된 그래프로 ‘네트워크(Network)’ 라고도 한다. 그래프 표현 방법 인접 행렬먼저, 인접행렬(adjacency matrix) 방법이 있다. 인접 행렬은 그래프를 nxn의 행렬로 표현하는 방법이다. 인접 행렬 방법에서, i 번째행 j 번째 열을 Aij 라고 할 때 정점 i와 j 사이에 엣지가 있으면 1, 없으면 0으로 표시한다. 인접 리스..

개요 Dynamic Programming은 흔히 생각하는 동적 프로그래밍(ex 동적 할당)과는 거리가 있다. 따라서 동적 계획법이라고 번역하는 것이 맞다고 한다. 동적 계획법에서는 어떤 문제를 더 작은 문제들로 나누고 각 조각의 답을 계산하고, 이 답들로 원래 문제의 답을 계산한다. 다만 어떤 부분 문제가 여러번 계산이 될 가능성을 없애기 위해 각 문제의 답을 메모리에 저장해 둔다. 가장 대표적인 동적 프로그래밍을 이용가능한 예인 피보자치 수열로 설명한다. 보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다. function fib(n) if n = 0 return 0 else if n=1 return 1 else return fib(n-1) + fib(n-2) 이때, fib(5)를 구한다고 한다면..

해시 테이블 해시 테이블은 원소의 값에 의해 결정되는 자료구조이다. 즉, 저장된 자료와의 비교를 통해 자리를 찾지 않고 단 한번의 계산으로 자리를 찾는다. 해시 함수 임의의 원소를 해시 테이블에 저장하려면 먼저 해당 원소의 해시값을 계산한다. 해시값은 해시 함수에 의해 계산된다. 해시 함수는 키값을 입력으로 받아 해시 테이블 상의 주소를 리턴하며 다음의 두 가지 성질을 가지도록 만들어야 한다. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. 계산이 간단해야 한다. 1) 나누기 방법 나누기 방법은 원소를 해쉬 테이블의 크기로 나누어 나머지의 값을 테이블의 주소로 사용하여 저장하는 방법이다. 위의 예제는 해쉬 테이블의 크기가 13 일때 해쉬함수에 25, 13, 16, 5 ,7 의 입력값이 주어진 경우..

개요 K-D 트리 (K-Dimensional Tree라고도 함)는 각 노드의 데이터가 공간의 K 차원 포인트인 이진 검색 트리다. 즉, K 차원 공간의 점을 구성하기위한 공간 분할 구조이다. K-D 트리의 비 잎 노드(non-leaf node)는 공간을 두 부분으로 나눈다. 루트는 x- 정렬 된 평면을 가질 것이고, 루트의 자식들은 모두 y- 정렬 된 평면을 가질 것이고, 루트의 손자들은 모두 x- 정렬 된 평면들을 가질 것이며, 루트의 증손자들은 모두 y- 정렬 된 평면들을 가질 것이다. 그래서 이해가능한 적당한 이미지를 찾기 힘들었다. 보통은 위의 2차원의 kdtree 이미지들이 많이 보이지만 이를 일반 트리처럼 표현하면 아래처럼 된다. 아래 좌표랑 위의 그래프랑 비교해보면 쉬울듯하다. 삽입 다른 검..

개요 B-Tree는 데이터베이스나 파일 시스템에서 주로 사용되는 자료구조이다. 디스크 액세스하는 수를 줄이기 위해 나온 자료구조이다. 대부분의 트리연산들은 O(h) (h는 트리의 높이)인데 B-트리는 노드에 가능한 최대로 값을 넣어서 높이의 수를 줄인다. 특성 루트를 제외한 모든 노드는 적어도 k-1개의 키를 포함해야한다. 최대로 2t-1의 키를 가질 수 있다. 각 노드는 일련의 키와 여러 개의 자식 (자식 노드)을 가질 수 있다. 여기서 자식의 수는 0 또는 해당 키의 총 수에 1을 더한 값이 될 수 있다. 노드 [x]를 생각해보자. node [x]가 잎 노드 인 경우는 자식을 가지지 다 이것이 내부 노드인 경우 전체 자식 수는 n [x] + 1이다. 여기서 n [x]는 해당 키의 총 수이다. 제약 조..

개요 일반 이진 탐색 트리의 경우 균형이 맞지 않을 수 있다. 이를 해결하기 위한 알고리즘이 레드 블랙 트리이다. 특징 이진 탐색 트리의 특징에 더해서 레드 블랙 트리만의 특징들이 있다. 노드는 레드 혹은 블랙 중의 하나이다. 루트 노드는 블랙이다. 모든 널 포인터는 블랙이다. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다) 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다. 삽입 이진 탐색 트리와 같이 삽입 연산을 진행하고, 색을 빨간색으로 지정한다. 이후 레드 블랙 트리의 특징을 유지하기 위해서 회전 연산을 해야하는 경우들이 있다...

개요 이진 트리는 비선형 자료 구조에 속하며 부모 노드에 붙는 자식 노드가 최대 2인 구조이다. 각 노드마다 값이 존재하고 한 노드의 왼쪽 서브트리에는 자신보다 작은 값들만 위치하며, 한 노드의 오른쪽 서브트리에는 자신보다 큰 값들만 위치한다는 특징이 있다. 삽입 이진 트리에서 삽입 연산은 현재 노드의 값과 새로 들어올 노드의 값을 비교한다. 현재가 더 크면 새로 들어올 노드는 현재 노드의 왼쪽 서브 트리에 놓게 된다. 이때 현재 노드의 왼쪽 자식 값이 null이면 새로 들어올 노드를 현재 노드의 왼쪽 자식에 삽입하고 null이 아니면 왼쪽 자식 노드에서 위의 연산을 반복하여 자리를 찾아간다. 반대로 현재가 작은 경우에는 오른쪽 서브 트리에 놓게 되며 위와 비슷한 과정을 거치며 자리를 찾아서 삽입해준다...