IT's 2 EG

에라토스테네스의 체(Sieve of Eratosthenes) 고대 그리스의 수학자 에라토스테네스가 만들어 낸 비교적 작은 구간(10^8 이하)에서 소수를 빠르게 찾는 방법 입니다. 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체라고 부릅니다. 에라토스테네스의 체 소수 확인 과정 N개의 자연수를 모두 적습니다. 이 중 1을 제외한 2부터 진행을 합니다. 여기서 자기 자신을 제외한 자기자신의 배수를 제외시키면서 소수를 확인 합니다. 2의 경우 2를 소수로 지정하고, 2의 배수인 4, 6, 8, 10 등은 소수에서 제외합니다. 위와 같은 행위를 반복하여 소수를 찾습니다. 에라토스테네스의 체 예제 www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N..

유클리드 호제법이란? 2개 정수의 최대공약수를 구하는 방법 중 하나입니다. 2개의 정수 a, b (a>b) 에 대하여 a를 b로 나눈 나머지를 r이라 할때, a와 b의 최대공약수는 b와 r의 최대공약수와 같음을 활용합니다. 이 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수 입니다. 유클리드 호제법 구현 int a, b; int gcd(int a, int b) { if (b > a) swap(a, b); int r = a % b; if (r == 0) return b; else return gcd(b,r); } 유클리드 호제법 예제 www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄..

유니온 파인드란? 이름 그대로 Union 연산과 Find 연산을 지원하는 자료구조입니다. 상호 배타적(중복되지 않은) 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는데 사용합니다. 유니온 파인드 연산 일반적으로 트리 형태의 자료구조로 표현하며 아래 3가지 연산을 사용합니다. - 초기화: N개의 원소가 각각 자기자신을 루토 노드로 설정합니다. - UNION 연산: 두 원소 a, b가 주어질때, 로트 노드를 동일하게 설정하여 이들이 속한 두 집합을 합칩니다. - FIND 연산: 원소 a에 대한 로트 노드를 재귀함수로 탐색을 합니다. 유니온 파인드 구현 아래와 같이 초기화, UNION, FIND 함수를 구현할 수 있습니다. const int MAX_SIZE = 1000000; int root[MAX..

세그먼트 트리란? 세그먼트 트리는 각 노드에 특정 구간의 대표값을 저장함으로써, 특정 구간에 대한 질문을 빠르게 답하는데 사용합니다. 세그먼트 트리는 완전 이진트리의 형태를 가지며 각 노드의 자식 노드는 부모 노드의 구간을 이등분한 두 개의 구간 중 한쪽 구간에 대한 정보를 가지게 됩니다. 이를 통해 세그먼트 트리를 활용한 연산은 최고 O(logN)의 시간복잡도를 가지게 됩니다. 세그먼트 트리 생성 방법 세그먼트 트리를 활용한 대표적인 문제는 특정 구간의 합을 구하는 것입니다. 아래는 0부터 9까지 N이 10인 배열에 대한 구간합을 세그먼트 트리로 구성하는 방법입니다. 1번 최상단 노드는 0부터 9까지의 구간합을 반환하도록 설정합니다. 자식노드인 2번과 3번 노드에는 1번 노드의 범위에 절반씩 분할하여 ..

플로이드-워셜 알고리즘 이란? 플로이드-워셜 알고리즘은 다이나믹 프로그래밍 접근 방식으로 그래프 상의 모든 두 정점에 대한 경로의 최단거리를 구합니다. 다익스트라 알고리즘과 달리 음수 가중치를 가지는 경로가 포함되어 있어도 최단거리를 구할 수 있습니다. 시간 복잡도는 O(V^3)을 가지며, 특정 경로 안에 무수히 많은 경로가 있을때, 중간 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 개념을 사용합니다. 플로이드-워셜 계산 과정 다음은 예제 그래프를 통해 플로이드-워셜 알고리즘을 통해 서로 다른 두 정점의 최단거리를 구하는 방식입니다. 최초 예제 그래프의 인접한 두 정점간의 거리를 아래와 같이 이차원 배열 형태로 정의합니다. 이후, 각 정점을 중간노드로 경유해가는 과정에서 최소값을..

다익스트라 알고리즘 이란? 다익스트라 알고리즘은 그리디한 방식을 통해 한 점에서 다른 모든점까지의 최단 경로를 구하는 알고리즘입니다. 다만 경로의 길이가 음수인 경우는 최단 경로를 구할 수 없습니다. 경로의 길이가 음수인 경우 최단거리를 구하는 알고리즘은 벨만 포드(Bellman-Ford) 알고리즘이 있습니다. 처음 고안된 다익스트라 알고리즘은 O(V^2)의 시간복잡도를 가졌습니다. 이후 우선순위 큐를 이용한 개선된 알고리즘을 통해 O(ElogV)의 시간복잡도를 가지게 되었습니다. 다익스트라 알고리즘 계산 과정 다음은 예제 그래프를 통해 다익스트라 알고리즘이 시작점에서 다른 모든점까지의 최단경로를 구하는 방식입니다. 빨간색 노드는 현재 위치의 노드를 의미하며, 파란색 노드는 우선순위 큐에 존재하는 노드,..

1. 이진탐색(Binary Search) 1.1. 이진탐색 이란? 'Up and Down'이라는 게임이 있습니다. 사회자는 일정 범위의 수 'x'를 생각한다. 참가자가 어떤숫자 'a'를 말했을때, 'a'가 'x' 보다 작으면 사회자는 'Up'이라고 말하며 'a'가 'x'보다 크면 'Down'이라고 말을 합니다. 그렇다면 가장 빠르게 'x'를 찾는 방법은 무엇일까요? 이에 대한 해답은 해당 범위의 중간값을 말하면서 'x'의 범위를 좁혀나가는 방법입니다. 이러한 방법으로 탐색을 해 나가는 것을 이진탐색이라고 합니다. 이진 탐색을 위해서는 우선 정렬이 되어있어야 한다는 조건이 있지만, 매우 큰 범위내에서 빠르게 찾고싶은 데이터를 찾을 수 있는 장점이 있습니다. 결과적으로 이진탐색은 O(logN) 라는 시간복잡..

너비 우선 탐색(BFS) 이란? 너비 우선 탐색 (BFS, Breadth First Search)은 DFS와 함께 대표적인 그래프 탐색 방법 중 하나입니다. BFS 알고리즘은 현재의 위치에서 방문할 수 있는 모든 정점을 방문한 뒤 다음 단계로 넘어가는 방식입니다. 일반적으로 BFS 알고리즘을 구현할 때 큐를 이용합니다. 너비 우선 탐색(BFS) 방법 아래는 BFS를 설명하기 위해 작성한 간단한 그래프입니다. 원안의 1,2,3.. 등을 정점(Vertex)라 하고, 정점과 정점을 잇는 선을 간선(Edge)이라고 합니다. 우선 시작점을 1로 정하고 BFS 알고리즘을 바탕으로 탐색을 해보겠습니다. 시작점인 1번 정점을 큐에 넣고 해당 위치에 방문을 했다고 표시합니다. 1번 정점과 연결된 2번, 3번 정점을 큐에..

깊이 우선 탐색(DFS) 이란? 깊이 우선 탐색 (DFS, Depth First Search)은 BFS와 함께 대표적인 그래프 탐색 방법 중 하나입니다. 일반적으로 DFS 알고리즘을 구현할 때 스택을 이용하고, 유사하게 재귀함수를 이용하여 구현하기도 합니다. DFS 알고리즘은 스택을 이용해서 갈 수 있는만큼 최대한 이동을 하며, 만약 갈 수 없다면 이전 정점으로 돌아갑니다. 깊이 우선 탐색(DFS) 방법 아래는 DFS를 설명하기 위해 작성한 간단한 그래프입니다. 여기서 원으로 둘라싸인 1, 2, 3 .. 등은 정점(Vertex)라 하고, 정점과 정점을 잇는 선을 간선(Edge)이라고 합니다. 우선 시작점을 1로 정하고 DFS 알고리즘을 바탕으로 탐색을 진행해 보겠습니다. 출발점인 1을 스택에 입력하고, ..