dldyou

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

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

1차 예선 때 글을 바로 안 써놓아서 문제가 잘 기억나지 않아 문제가 나오고 나서 후기를 작성할까 고민하다가 나중에는 더 작성하지 않을 것 같아서 그냥 작성하게 되었다..1차 예선1. 증강현실 배달 안경#bruteforce아마 $A$개를 담을 수 있는 상자와 $B$개를 담을 수 있는 상자로 $N$개를 1개도 빠짐없이 모두 담으려고 할 때 상자를 최대로 사용하는 문제였던 것 같다. 가능한 모든 경우를 탐색해주기만 하면 되는 문제였다.#include using namespace std;int n, m, k;void solve() { int a, b; cin >> n >> a >> b; if (a > b) swap(a, b); int cnt = 0; while (1) { ..

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