CS/Algorithm

CS/Algorithm
[Algorithm] The Bellman-Ford algorithm(벨만-포드 알고리즘)
• 개요 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..
→2021.08.24
CS/Algorithm
[Algorithm] 기수 정렬(Topological sort) (BOJ 2252, BOJ 1766)
• Topological sort의 필요 directed acyclic graph(dag)의 경우 가끔씩 순서에 따라 linear한 정렬이 필요한 경우가 있다. 예를 들어 다음과 같은 상황을 가정해 보자. 수강할 강의를 선택하려고 한다. 매 학기 하나의 강의만 선택할 수 있고, 어떤 강의는 선수과목이 존재하여 선수강의를 수강하지 않았을 경우 수강할 수 없다. 이 경우 수강할 강의를 선택하는 방법을 제시하라. 위와 같은 상황을 graph로 나타내면 다음과 같을 것이다. 맨 처음 선택할 수 있는 과목은 A와 G 뿐이다. A를 수강한 다음이라야 비로소 B를 수강할 수 있고, D를 수강하려면 B와 G를 수강하여야 한다. F 과목을 수강하기 위해서는 F를 제외한 그래프 안의 모든 강의를 수강하여야 한다. 이런 문..
→2021.08.09
CS/Algorithm
[Algorithm] Segment tree with Lazy propagation (BOJ 10999)
• 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이다...
→2021.08.06
CS/Algorithm
[Algorithm] 선분교차(Line-segment intersection) 판정 알고리즘
• Line-segment intersection 판별 알고리즘의 필요성 Line-segment의 교차 판정은 PS에서 흔히 다뤄지는 문제이다. 예컨대 네 점 이 주어졌다고 하자. 이 때 다음과 같은 두 선분을 생각할 수 있다. 이때 두 선분의 교차 관계를 판단하는 가장 직관적인 방법은 역시 slope를 구해서 일차 함수로 표현한 뒤 교점을 구하여 범위를 인식하는 방법이다. 위의 두 line-segment의 intersection을 일차 함수를 이용하여 파악해 보자. 위와 같은 두 선형 함수를 만들 수 있고, 두 함수의 교점을 쉽게 구할 수 있다. 구한 교점에 대하여 x값과 y값의 범위를 계산하면 선분의 교차 관계를 매우 직관적으로 얻을 수 있다. 다만 이 방법엔 문제가 있다. 다음 문제들을 떠올릴 수 ..
→2021.07.16

• 이전
• 1
• 다음