자료구조 & 알고리즘/알고리즘3 [3] 좌표 압축 (Coordinate-Compression) 좌표 압축은 PS에서 정말 많이 쓰이는 테크닉으로, 세그트리 같이 구간 쿼리를 해결하기 위해 많이 사용한다. 세그트리는 주어진 범위의 모든 영역을 Leaf node로 사용하기 때문에, 해당 범위가 커지면 좌표 압축이 필요하다. 결국 좌표 압축은, 해당 좌표를 0,1,2 ~ 의 값으로 치환하는 것인데, 그 자체는 매우 어렵고 이해가 되지 않는 개념은 아니다. for (int i = 0; i > comp[i]; v.push_back(comp[i]); } sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); for (int i = 0; i < n; i++) { comp[i] = lower_bound.. 2020. 9. 28. [2] Floyd-Warshall 알고리즘 플로이드 워셜 알고리즘은 그래프에서 "All-pair-shortest-path" - 정점들의 모든 쌍의 최단 경로의 길이를 구하는 알고리즘이다. 그래프 알고리즘 중 가장 단순한 알고리즘이라고 생각된다. Brute-Force랑 거의 같다고 볼 수 있기 때문이다. 알고리즘도 단순하다. pseudo-code를 보자. 다음과 같이 Floyd-Warshall은 for문 3개로 돌아간다. 의미를 해석하자면 i에서 j로 가는 길의 거리를 생각했을 때, i에서 j로 바로 가는게 빠른지 -> (d_ij) 아니면 k를 경유하여 가는게 빠른지를 비교해서 (d_ik + d_kj) 더 작은 길의 값이 지정이 되는 것이다. (min) 저장되는 그래프 D의 dij는 곧 i에서 j로 가는 최단 거리가 지정이 될 것이다. 2020. 4. 12. [1] 3-SUM algorithm 3-Sum algorithm은, 세 숫자의 합이 특정 조건을 만족하는 모든 경우의 수를 탐색하는 알고리즘이다. 2-Sum 알고리즘도 있다. 애는 Linear Time에 해결할 수 있고, 이는 Hash-table을 이용하여 문제를 해결한다. 2-Sum algorithm을 nlogn의 시간복잡도로 해결하는 방법으로 sliding-window 방식이 있는데, 3-Sum algorithm은 이 방식을 한번 더 감싼 것에 불과하다. 예시 문제를 보면서 이해해보자. 주어진 문제에선 용액의 특성값을 나타내는 N개의 정수가 순서대로 제공된다. 그 때, 세 특성값의 합이 0에 가장 가까운 조합을 찾는것이 목적이다. 그냥 단순히 Brute-force로 문제를 해결하게 되면, for문을 3개 돌려서 모든 조합에 대해서 정답.. 2020. 4. 11. 이전 1 다음
