• 개요 Bellman-Ford algorithm에 대해서 찾아보는데, 대부분 간단하게, 또 과정 위주로 설명되어 있고 왜 Bellman-Ford algorithm이 정당성을 가지는지, 또 왜 그러한 순서로 해도 문제가 발생하지 않는지에 대해 설명이 부족한 것 같아 직접 정리하기로 하였다. • Single Source Shortest Path problems(SSSP) SSSP는 그래프 이론에서 아주 중요하고 또 자주 출제되는 문제이다. non-negative weighted graph와 관련된 문제의 경우에 Dijkstra's algorithm이 풀이에 사용되는데, 이는 time complexity가 O(VlogE)이므로 일반적인 graph에서 다른 알고리즘보다 빠른 측면이 있기 때문이다. 그러나 Di..

보호되어 있는 글입니다.

Jordano이 Tistory 블로그는 더 이상 운영하지 않습니다. 다음 링크에서 블로그 활동을 지속합니다: This Tistory blog is no longer being maintained. You can continue following my blog at: 此 Tistory 博客已不再运营。请在以下链接继续关注我的博客：current blog link ChannelWebpage: csjihwanh.comContacte-mail: csjihwanh at gmail dot com

• Topological sort의 필요 directed acyclic graph(dag)의 경우 가끔씩 순서에 따라 linear한 정렬이 필요한 경우가 있다. 예를 들어 다음과 같은 상황을 가정해 보자. 수강할 강의를 선택하려고 한다. 매 학기 하나의 강의만 선택할 수 있고, 어떤 강의는 선수과목이 존재하여 선수강의를 수강하지 않았을 경우 수강할 수 없다. 이 경우 수강할 강의를 선택하는 방법을 제시하라. 위와 같은 상황을 graph로 나타내면 다음과 같을 것이다. 맨 처음 선택할 수 있는 과목은 A와 G 뿐이다. A를 수강한 다음이라야 비로소 B를 수강할 수 있고, D를 수강하려면 B와 G를 수강하여야 한다. F 과목을 수강하기 위해서는 F를 제외한 그래프 안의 모든 강의를 수강하여야 한다. 이런 문..

https://jordano-jackson.github.io/Plays/theGreatMoths/theGreatMoths.html 대나방 (The Great Moths) A가 등장한다. A는 우리 주변에서 흔하게 볼 수 있는 평범한 차림의 사람이다. 화려하지도 추레하지도 않다. A는 주변에는 무신경한 채 곧장 따뜻한 조명이 비추는 곳으로 다가가 문을 여는 시 jordano-jackson.github.io 본문은 위 사이트에서 확인할 수 있다. 작의 필자는 계층이동 가능성이 점점 낮아지고 있다고 본다. 이것은 사회구조적 문제 때문인 것처럼 보인다. 그러나 현대사회 개인들은 마르크스와 달리 원인을 클래스로 인한 사회모순에서 찾지 않는다. 그들은 원인을 자신에게서 찾으며 투쟁 대상을 무능력한 본인으로 설정한다..

• segment tree with lazy propagation algorithm의 필요성segment tree는 구간에 대한 query를 O(logN)에 수행할 수 있도록 한다. 한 index에 대한 update를 수행할 경우에 update의 time complexity는 역시 recursive call에 의해서 O(logN)에 수행된다. 만약 한 index가 아니라 구간 [L, R]에 대한 update를 수행할 경우 [L, R]에 속한 모든 index에 대하여 update를 해 주어야 하므로 O((R-L+1)logN), 일반적으로 쓰면 O(NlogN)의 긴 수행 시간이 필요하게 된다. 이를 해결하기 위해서는 일종의 optimization이 필요한데, 이것이 바로 lazy propagation이다. ..

• 문제 설명 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net KOI 2010 고등부 1번 문제이다. 푸는 방법은 두 가지가 있는데, two pointers로 푸는 방법과 binary search로 푸는 방법이 있다. two pointers로 풀면 time complexity는 O(N^2)으로 풀 수 있고, binary search로 풀면 O(N^2*logN)으로 풀 수 있다. 다만 two pointers로 풀기 위해서는 ..

2013년도 KOI 도대회 고등부 3번 문제이다. 간단한 segment tree 문제처럼 보였는데, TLE를 3번 받았다. 해법은 간단하다. 1행의 케이블의 번호를 1, 2, 3, 4, 5의 오름차순으로 정렬하고, 2행의 케이블의 번호를 이에 맞게 다시 부여해준다. 그러면 예제의 경우 2, 4, 1, 3, 5가 되는데, 교차는 한 기계에서 그 앞에 자신보다 큰 숫자가 있을 경우에 발생한다. 예제의 경우를 보자. 2의 경우 교차는 0이다. 4의 경우도 교차가 0이고, 1의 경우 앞에 2와 4가 있으므로 교차가 2번 발생하고, 3의 경우는 4로 인해서 한 번, 5는 발생하지 않는다. 따라서 교차횟수는 총 3회이다. 따라서 https://jordano-jackson.tistory.com/33에서 다루었던 BO..

https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 2012년도 정올 고등부 2번 문제다. segment tree와 좌표압축을 사용하면 된다. 실력을 기준으로 segment tree를 만들면 특정 실력의 선수를 확인할 때 O(logN)만에 최대 등수를 확인할 수 있다는 아이디어를 얻을 수 있다. 여기서 중요한 점은 앞에서부터 차례로 update를 해 주고 query를 처리하여서 i번째 선수까지만 tree에 반영이 될 수 있도록 하는 것이다. ..