IT's 2 EG

www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 더보기 #include #include #include #include #include #include using namespace std; typedef pair node; int V, E; //V: 정점의 개수, E: 간선의 개수 int sp; bool visited[20001]; int dist[20001]; vector graph[20001]; priority_queuePQ; ..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 더보기 #include #include #include using namespace std; queue Que; int visit[100001] = { 0, }; int dist[100001] = { 0, }; int main(int argc, char* argv[]) { int n, k; //형의 위치, 동생의 위치 scanf("%d %d", &n, &k); Que.push(n..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 더보기 #include #include #include using namespace std; int n, m; // 정점, 간선 int v; // 탐색을 시작할 정점의 번호 int s, e; //시작점, 끝점 int matrix[1002][1002]; int visit[1002]; queue Q; int check[1002]; // DFS 함수 void dfs..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 더보기 #include #include #include #include using namespace std; int n, m; //미로의 행(n), 열(m)의 수 int map[101][101]; //미로 map int result[101][101]; //탐색 결과 queue Q; // 이동 경로에 대한 좌표값(상, 하, 우, 좌) int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 }..

에라토스테네스의 체(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)의 시간복잡도를 가지게 되었습니다. 다익스트라 알고리즘 계산 과정 다음은 예제 그래프를 통해 다익스트라 알고리즘이 시작점에서 다른 모든점까지의 최단경로를 구하는 방식입니다. 빨간색 노드는 현재 위치의 노드를 의미하며, 파란색 노드는 우선순위 큐에 존재하는 노드,..