dldyou

최단 경로 알고리즘(1) - floyd-warshall / dijkstra 이전 글과 달리 이번 글에서는 가중치가 음수인 간선에 대해서도 (가중치가 음수인 cycle이 생기는 그래프) 최단 경로를 구할 수 있는 알고리즘을 소개한다. Bellman Ford 첫 번째로 알아볼 벨만-포드 알고리즘이다. 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이며 간선의 가중치가 음수일 때도 경로를 구할 수 있다는 특징을 가지고 있다. 벨만-포드 는 아래와 같이 굴러간다. 모든 간선을 확인하면서 최단 경로를 갱신한다. 1.을 $V$번 반복한다. 만약 $V$번째에서도 최단 경로를 갱신하려 한다면 음수 사이클이 존재한다는 것이다. $V$번째에서도 갱신 시도가 있을 때 음수 사이클이 존재한다는 것의 이유는 $V..

[BOJ 2485번 가로수] 임의의 간격으로 배열 되어있는 가로수들이 모두 같은 간격이 되도록 가로수를 새로 심어야 하는 최소수를 구하는 문제이다. 1 3 7 13 위치에 있다면 1 3 5 7 9 11 13 과 같이 3그루를 심어주면 된다. 심는 가로수가 최소가 되려면 같은 간격이 되었을 때, 그 간격이 최대여야 한다. 즉, 최대공약수 를 구하는 문제이다. 모든 간격들의 최대공약수가 같은 간격이 되었을 때의 간격이 되는 것이고, 심어야 하는 가로수의 수는 간격들을 최대공약수로 나눈 값에 1을 빼준 값을 계속해서 더해가면 구할 수 있다. 그렇다면 최대공약수는 어떻게 구할까? 수학 시간에 최대공약수를 구하는 방법으로는 크게 서로소가 나올 때까지 공약수로 나누기 소인수 분해 후 공통인 것 중 지수가 작은 것 ..

[BOJ 11689번 GCD(n, k) = 1] 문제는 간단하다. 자연수 $n$이 주어졌을 때, $GCD(n, k)=1$ 을 만족하는 자연수 $1\leq k\leq n$ 의 개수를 구하면 되는 문제이다. 그냥 단순히 $O(N)$ 으로 반복문을 전부 돌려보며 카운팅을 하면 안되냐 할 수 있겠지만 $n$ 의 제한을 보면 $1\leq n\leq 10^{12}$ 이다. 만약 이 방식으로 제출했다면 채점 현황에 시간초과 가 찍혀 있을 것이다. 이 문제를 해결하기 위해서는 오일러 피(Euler's phi) 함수를 알아야 한다. 이 함수는 정의 자체가 $n$이 양의 정수일 때, $\phi{(n)}$은 $n$과 서로소인 1부터 $n$까지의 정수의 개수와 같다. 문제의 정의와 완전히 일치하는 것이다! $\phi{..

[BOJ 11401번 이항 계수 3] $\binom{n}{k}$ % 1,000,000,007 을 구하는 문제이다. 결론적으로 이 문제는 모듈러의 성질, 페르마의 소정리와 분할 정복을 이용해 해결 가능하다. 본문에 나오는 $p$는 소수 (1,000,000,007) 임을 인지하자. 우선 페르마의 소정리는 아래와 같다. $p$가 소수이면, 모든 정수 $a$에 대해 $a^p \equiv a\ (mod\ p)$ $p$가 소수이고 $a$가 $p$의 배수가 아니면, $a^{p-1} \equiv 1\ (mod\ p)$ 그런데 이 정리가 왜 필요하냐를 묻는다면 모듈러 산술의 정의를 보자. 위키 모듈러 산술은 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다. 그리고 다시 돌아와서 우리가 고등학교 때 ..

Spannig Tree 그래프 내의 모든 정점을 포함하는 트리 위의 정의에 따라 $N$개의 정점을 가지고 있는 그래프를 $N-1$개의 간선으로 연결하였다면 이는 트리의 형태가 되며 Spanning Tree 의 정의를 만족한다. Minimum Spanning Tree Spanning Tree 중 사용한 간선들의 가중치의 합이 최소인 트리 Spanning Tree 와 MST 는 하나의 그래프에 여러 개가 존재할 수 있다. 이러한 MST 를 구하는 알고리즘에는 2가지 방식이 있다. Prim 과 Kruskal 알고리즘이다. Prim 정점을 선택하며 진행되는 알고리즘이며, 하나의 집합에 계속해서 포함시키는 방식으로 진행된다. 시작 정점을 집합$(S)$에 포함시킨다. $S$에서 인접한 정점들 중에서 갈 수 있는 모..

이분탐색 말 그대로 두개로 나누어서 탐색하는 방식이다. 정확히는 정렬된 데이터에서 절반인 지점을 찍어 찾는 데이터가 맞는지 확인하는 과정을 계속해서 거쳐서 원하는 데이터를 찾는 방식이다. Up Down 게임 Up Down 게임을 생각하면 이해가 좀 더 쉬울 것이다. 상대방이 1부터 100사이의 수 중에 하나를 선택하고 우리는 턴마다 숫자를 물어봐서 선택한 수와 (동일한지 / 큰지 / 작은지)를 알 수 있다. 여기서 1, 2, 3, 4, ... 이렇게 차례대로 부른다면 언젠가는 맞겠지만 우리는 이 턴을 최대한 줄이고 싶다. 운이 좋으면 한 번에 맞출 수도 있겠지만 여러번의 게임을 진행했을 때를 고려하자. 이 게임을 어떻게 플레이할지는 모두 알 것이다. 50을 찍고 Up 이면 51과 100의 절반인 75, ..

이 글에서는 최단 경로를 구하는 알고리즘으로 무엇이 있는지, 대강 어떤 원리로 굴러가는지만 소개한다. Floyd-Warshall 첫 번째 주자는 플로이드-워셜이다. 가장 구현이 간단하며 모든 정점에서 모든 정점까지의 최단 경로를 구할 수 있다는 특징이 있다. 기본적인 원리는 a->b로 가는 거리와 a->?->b로 거쳐가는 거리 중 무엇이 더 짧은지 갱신하는 것이다. 대략적인 구현은 INF(나올 수 없는 큰 수)값으로 초기화를 해주고나서 주어진 간선들을 배열에 넣어주고 나서 아래의 반복문을 돌려주면 된다. // i->j 가 짧은지 i->k->j가 짧은지를 비교하여 갱신한다. for (int k = 1; k

교내 대회의 운영진으로 참여하게 되어 문제를 제작해볼 수 있는 기회를 가졌다. 평소에 문제를 만들어보고 싶은 의향이 컸지만 제작 과정이 어떻게 되는지 접할 기회는 없었다. 이 글은 스스로의 문제를 만들어보고 싶지만 어떻게 만드는지 몰라서 생각만으로 그치는 사람들을 위한 글이다. 기본적으로 C++로 문제를 제작하는 과정을 다룬다. 문제를 제작하는 과정은 크게 다음과 같이 이루어졌다. 소재 선택 (알고리즘 선택) 지문 작성 (컨셉 없이, 딱 문제 상황에 대해서만) 풀이 작성 Polygon에서 제작 진행 그런데 꼭 위의 상황처럼만은 이루어지지 않는다는 점을 알리고 싶다. 우선 지문을 작성해놓고 풀이를 알지 못해 넘기는 문제도 있었고, 의도하고 만든 문제들도 있었기에 상황에 따라 진행을 하면 된다. 1 / 2 ..

velog에서 보기 Inversion Counting 배열 $A$가 주어졌을때, $i\lt j$이면서 $A[i]\gt A[j]$를 만족할 때를 Inversion이라고 부른다. Inversion Counting 은 이 Inversion의 개수를 세는 문제이다. 단순하게 생각해보면 이중 반복문을 통해 $O(N^2)$의 시간복잡도로 이 문제를 해결할 수 있을 것이다. void getInversion { for (int i = 0; i A[j]) { cout