개요 플로이드-워셜(Floyd-Warshall)은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘으로, $O(N^3)$의 시간 복잡도를 가지고 있습니다. 다익스트라 알고리즘은 가중치가 음수인 경우에는 사용할 수 없다는 단점이 있지만, 플로이드-워셜은 사용할 수 있습니다. 음수 사이클이 있는 그래프의 경우 사용할 수 없습니다. 과...

문제 https://www.acmicpc.net/problem/28298 풀이 발상 자체는 떠올리기 쉬울 수 있으나, 주어진 배열을 $K \times K$ 크기로 쪼개어, 그 내부를 탐색하는 과정은 쉽지 않을 수 있습니다. 먼저 for (int r = 0; r < K; r++), for (int c = 0; c < K; c++) 반복...

개요 좌표 압축, 혹은 값 압축(Coordinate Compression)은 데이터 범위가 매우 클 때 효율적으로 처리할 수 있게 해주는 최적화 기법입니다. 이름만 들으면 뭔가 기하학적인 지식이 필요할 것 같지만, 절대 그렇지 않습니다! 좌표 압축은 알고리즘이라기 보단, 데이터를 다루는 하나의 방법론에 가깝습니다. 일반적인 코딩 테스트에서 ...

개요 사진 출처: https://david0506.tistory.com/62 볼록 껍질(Convex Hull)은 점들이 주어졌을 때 모든 점을 포함하는 볼록 다각형을 구성하는 알고리즘으로, 주로 특정 상황에서의 최소 다각형을 구하는데 사용되곤 합니다. 여기서 볼록 다각형이란, 모든 내각이 180도 이하로만 이루어진 다각형을 말합니다. 볼록 껍질...

문제 https://www.acmicpc.net/problem/1629 풀이 단순히 반복문을 돌려 거듭제곱을 한다면, 반복문이 최대 2,147,483,647번을 돌게 되어 시간 초과를 받게 됩니다. 다른 방식을 생각해야 하는데, 이때 사용되는 것이 분할 정복을 이용한 거듭제곱입니다. 거듭제곱을 수학적으로 분할해 본다면, 아래와 같은 식을 구성할...

문제 https://www.acmicpc.net/problem/16212 풀이 최대가 500,000이므로 $O(N^2)$의 시간 복잡도를 가지는 알고리즘은 사용할 수 없습니다. 하지만 대부분의 정렬 함수는 시간 복잡도가 $O(N \log N)$이므로, 함수만 사용하여 쉽게 해결할 수 있습니다. #include <algorithm> #...

소개 거의 1년 반동안 사용한 티스토리 블로그를 뒤로 하고, 이번에 새로 GitHub Pages에 정착하게 되었습니다. 예전에 한번 GitHub Pages를 사용해 본 적이 있었지만, 다른 블로그 대비 복잡한 환경 설정 등으로 인해 금방 포기했던 기억이 있습니다. 하지만 날이 갈수록 자유도가 높은 플랫폼으로 이사를 가고 싶다는 생각이 들었고, 이것이...