kjk9704   1년 전

2015년 5월 13일 마지막으로 왜 이 문제가 안 풀리는지 알 것 같군요.

이 문제는 그저 선분 교차 + 데이크스트라 1번만 하면 될 줄 알았는데 설마 세그먼트 트리가 필요할 줄은 전혀 몰랐습니다.

(에디토리얼에서는 안 적혀 있습니다.)

그래서 구현하는데 꽤 많은 애를 먹었고 이 문제보다 더 어렵다고 판단하여 루비 5로 측정했습니다.

다이아 1티어로 줄까 고민하다가 선분 교차 + 데이크스트라 + 세그먼트 트리 + 오프라인 쿼리가 동시에 나오는 문제가 다이아 구간에 존재하지 않으므로 루비 문제로 판단합니다.

어쨋거나 2025년 11월 10일, 10년 만에 이 문제가 풀렸습니다.

[2025-11-11 12:25]

세그먼트 트리 없이도 구현되는 것을 보고 아무래도 제가 Python 구현하는 과정에서 세그먼트 트리로 더 최적화를 했나 봅니다.

[2025-11-11 20:16]

에디토리얼이 이미 존재하고 제가 알고리즘 태그들을 만들면서 힌트가 존재하는 상태이며 세그먼트 트리가 강요되지 않아 이 문제는 루비 급이 아닌 것으로 판단, 다이아 1티어 혹은 2티어가 적당하나 저는 개인적으로 다이아 1티어로 내릴 생각입니다.

redcube231   1년 전

세그먼트 트리 기본만 할 줄 알아도 풀만한가요?

kjk9704   1년 전

퍼시스턴스, 키네틱, 비츠같은 특이한 것 말고 기초만 해도 나름 풀만합니다.

그 중 최소값을 구하는 세그먼트 트리를 구현하면 해결됩니다.

우선 각 테스트 케이스마다 1번의 다익스트라로 값들을 구하고 그 다음 세그먼트 트리로 각 쿼리들을 O(log K)로 호출하면 해결됩니다.

kjk9704   1년 전

추가 사항 : JS에서 어떠한 방법을 사용해도 언어 자체의 한계에 의해 메모리 초과 발생하는 문제가 있습니다.

그리고 GPT의 힘을 빌려서 C언어로 변환해본 결과 900줄 이상, 27000바이트 이상이라는 경악스러운 결과가 나와서 제가 너무 과소평가한 것으로 판단했습니다.

경악스러운 구현 난이도, 그리고 다른 사람들이 세그먼트 트리 힌트를 얻고 수많은 시도에도 실패한 것을 근거로 두어 루비 4로 격상합니다.(LCS 7 구현 난이도와 비슷한 것으로 판단합니다.)

하지만 루비 3까지는 아닙니다.

redcube231   1년 전

머리로는 풀었는데 시간복잡도가 O(TNNlogN) 맞나요? 뭔가 너무 큰 거 같은데

세그트리는 안 써도 될 거 같은데... 풀어보겠습니다

kjk9704   1년 전

각 작업마다 시간 복잡도가 다 다르게 나와서 하나로 정리하기는 힘듭니다.

다만, 최악의 경우(O(N^2 log N))를 제외한 보통의 경우는 도로-도로 교점 계산하는 과정에서 브루트 포스 사용할 때 O(N^2)입니다.

추가로 세그먼트 트리 없으면 전체 쿼리 처리할 때 O(QN^2)가 되고 세그먼트 트리 있으면 O(Q N log V)가 됩니다. 여기서 Q는 쿼리 개수, V는 전체 정점의 수입니다.

redcube231   1년 전

각 선분마다 이벤트 정리 후 세그트리를 쓰거나 하는 방법이 아닌가 보네요? 잘못 푼 거 같기도 하고....

kjk9704   1년 전

전체 시간 복잡도 계산했습니다.

O(E log N + QN log V)가 나옵니다.

여기서 O(E)는 O(N^2)와 유사하고 O(V)는 O(N)과 유사합니다.

즉, O(N^2 log N + QN log N)입니다.

추가 : 세그 없이도 가능한 풀이가 등장했네요.

이 문제는 세그 없이도 멀티 소스 다익스트라 한 번으로 해결 가능한 문제인 것으로 보입니다.

redcube231   1년 전

멀티 소스 데이크스트라에 QNlogV면 맞게 풀긴 한 거 같은데 아무튼 풀어보죠. 감사합니다.

까짓 거 해보죠

kjk9704   1년 전

원-선분 교점들을 직접 노드로 만들고 멀티 소스 다익스트라로 dist[node]에서 바로 읽는 방식으로 우회하면 세그먼트 트리 없이 가능합니다.

다만 세그먼트 트리 없어도 매우 길고 어려운 구현 난이도는 여전해서 루비 5 대신 루비 4 유지하기로 결정합니다.

(LCS 6 구현 난이도와 LCS 7 구현 난이도 중에서 LCS 7에 더 가깝습니다.)

redcube231   1년 전

교점들을 노드로 하니까 정점이 100만개인데 정점 개수를 N개로 줄여서 푸는 방법이 있나요?

kjk9704   1년 전

세그 없이 그냥 다익스트라로 풀려면 최악의 경우 정점이 100만개일 때 그 100만개로 계산해야 합니다.

만약 이것을 N개로 줄이는 방식을 채택할려면 세그먼트 트리로 O(log K) 호출하는 방식으로 푸는 방법이 있긴 합니다.

하지만 C/C++에서는 정점이 100만개여도 통과되는 방법이 있습니다.

redcube231   1년 전

아하

redcube231   1년 전

코드 읽어봤는데 세그먼트트리를 사용해서 어떤 걸 최적화한 건가요? 지금 제 코드보다 빠른 방법이 있나 생각해보는 중입니다

댓글을 작성하려면 로그인해야 합니다.