그리디 알고리즘이란? 그리디 알고리즘은 해답에 포함될 원소들을 차례로 선택하는 과정을 거치게 되는데, 각 단계에서는 전체적인 상황을 종합적으로 판단하고, 고려하여 결정하는 것이아니라 현 시점의 정보를 바탕으로 가장 이익이 되는 원소들을 선택하는 방법이라고 할 수 있다. 복잡한 과정을 거치지 않고, 상황을 종합적으로 판단하는게 아니기 때문에 매우 빠른 알고리즘이라고 할 수 있다. 이러한 그리디 알고리즘은 최적화 문제를 해결하기 위한 방법이다. 2878번: 캔디캔디 문제 오늘 사탕 M개를 가득 담은 박스가 택배로 택희네 집에 도착했다. 택희는 이 사탕을 N명의 친구들에게 나누어 주려고 한다. 택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 받고 싶은 개수만큼 사탕을 받지 못한다면, 그 친구는..
알고리즘
신장 트리란 그래프 중 모든 정점이 간선으로 연결되어 있되, 간선간의 사이클이 없는 그래프 최소 비용 신장 트리 각 간선에 비용(가중치 합)이 있을때 최소화 하는 신장트리를 말함 크루스칼 알고리즘 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이 아니면 왼쪽 자식 노드에서 위의 연산을 반복하여 자리를 찾아간다. 반대로 현재가 작은 경우에는 오른쪽 서브 트리에 놓게 되며 위와 비슷한 과정을 거치며 자리를 찾아서 삽입해준다...
기수 정렬 기수 정렬은 배열 안의 데이터가 모두 n자릿수 이하의 자연수인 경우 사용 가능한 정렬이다. 일의 자릿수로 크기 비교후 정렬하고 다음은 십의 자리, 백의 자리,...해서 n자릿수까지 크기를 비교하는 독특한 정렬이다. 시간 복잡도는 O(dn)으로 빠른 편이다. 다만 테이블이 따로 필요하다는 단점이 있다. 기수 정렬이 어떤 순서로 동작하는지는 아래의 영상에 나와있다. https://youtu.be/nu4gDuFabIM import java.io.*; import java.util.*; class Radix { static void countSort(int arr[], int n, int exp) { int output[] = new int[n]; int i; int count[] = new int[..
