기록공간

에라토스테네스의 체란? 에라토스테네스의 체는 소수를 찾는 방법 중 하나이다. 고대 그리스 수학자 에라토스테네스가 발견했다. 원리 위 그림과 같이 동작하는데, 정리를 해보면 다음과 같다. 2의 배수부터 시작한다고 했을때 2 * 2부터 구하려는 범위(여기서는 120)까지 2의 배수가 있으면 걸러낸다. 작업1 을 n^2 > m (m : 소수를 구하려는 범위)을 만족하는 n의 배수까지 반복한다. (여기서는 120이기 때문에 11^2 > 120을 만족하므로 n은 11이다) 그리고 걸러내지 않은 나머지 값들이 소수가 된다. 구현 구현 코드는 다음과 같다. void Eratos(int m) { // 만약 m이 1보다 작거나 같으면 함수 종료 if(m

유클리드 알고리즘이란? 유클리드 알고리즘은 주어진 두 수 사이에 존재하는 최대공약수(gcd)를 구하는 알고리즘이다. 원리 유클리드 알고리즘은 다음과 같은 원리로 동작한다. 임의의 두 자연수 a, b가 주어진다. (둘 중 큰 값이 b라고 가정한다.) a와 b를 나눈 나머지를 구한다. 이 결과값을 n이라고 한다. (n = a % b) n이 0일때 a가 최대공약수(gcd)가 된다. 만약 n이 0이 아닌 경우, b에 n값을(b = n), a에 b값을(a = b) 넣고 2부터 반복한다. 구현 두가지 방법으로 구현이 가능하다. 반복문을 이용한 구현 int gcd(int a, int b) { int n; // b에 큰 값을 위치시키기 위한 조건문 if(a > b) { int temp = a; a = b; b = te..

구간 합(Prefix Sum)이란? 만약 N개의 정수형 배열이 있다고 가정했을 때, 부분 합은 0 ~ (N - 1)까지의 합을 의미하는 것이고, 구간 합은 a ~ b (0

개요 허프만 코딩(Huffman coding)은 텍스트 압축을 위해 널리 사용되는 방법으로, 원본 데이터에서 자주 출현하는 문자는 적은 비트의 코드로 변환하여 표현하고 출현 빈도가 낮은 문자는 많은 비트의 코드로 변환하여 표현함으로써 전체 데이터를 표현하는데 필요한 비트 수를 줄이는 방식이다. (마치 UTF-8과 비슷하게 동작한다) 이러한 압축 과정에서 가장 중요한 부분이 각 문자를 표현하기 위한 허프만 트리(Huffman tree)를 구성하는 것인데, 예를 통해 그 과정을 이해해 보자. 원리 다음의 텍스트를 허프만 코딩을 통해 압축해 보려고 한다. AAAAAAABBCCCDEEEEFFFFFFG 우선 원본 데이터에 포함된 각 문자에 대한 출현 빈도수를 구하여 내림차순으로 정렬한다. A(7개) F(6개) E..

개요 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(short path)탐색 알고리즘이다. 보통 인공위성 GPS 소프트웨어 등에 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 하지만 주의할 점이 있는데 음의 간선은 포함할 수 없다는 점이다. 물론 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라 알고리즘은 현실 세계에 사용하기에 매우 적합한 알고리즘 중 하나이다. 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리는 여러 개로 이루어져 있기 때문이다. 그렇기 때문에 작은 문제가 큰 문제의 부분 집합에 속해 있다고 볼 수 있다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 ..

백트래킹(backtracking)은 한정 조건을 가진 문제를 풀려는 전략이다. 문제가 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다. 이런 문제는 변수 집합으로 이루어지는데, 한정 조건을 구성하기 위해서 각각의 변수들은 값이 있어야 한다. 백트래킹은 모든 조합을 시도해서 문제의 해를 찾는다. 이것이 가지는 장점은 많은 부분의 조합을 배제(가지치기)하는 것이다. 이로 인해 풀이 시간이 단축된다. 예를 통해서 백트래킹을 알아 보도록 하자. 가장 쉽게 접할 수 있는 예시로는 4-Queens Problem이 있다. N-Queens Problem은 크기가 N * N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 만들기 위해서..

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 처음 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 시간 복잡도는 3중 반복문으로 O(n^3)이다. 코드는 다음과 같다. 이외로 간단하다. for(int k = 0; k d[i][k] + d[k][j]) d[i][j] = d[i][k] + d[k][j]; } } } 선행 조건으로 배열에는 두 정점 간..

크러스컬 알고리즘은 그리디 알고리즘을 이용하여 가중치가 존재하는 그래프를 최소의 비용으로 연결하는 최적의 해답을 구하는 알고리즘이다. MST(최소 비용 신장 트리)가 최소 비용의 간선으로 구성되어 있고, 사이클을 포함하지 않은 조건에서 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다. 크러스컬 알고리즘의 동작 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. -> 가장 낮은 가중치를 먼저 선택한다. -> 사이클을 형성하는 간선을 제외한다. 해당 간선을 현재의 MST의 집합에 추가한다. 동작과정을 그림으로 표현하면 다음과 같다. 사이클 생성 여부를 항상 체크하는 것이 중요하다. 추가할 새로운 간선의 양끝 정점이 이미 MS..