power line
-
[문제해결을 위한 창의적 알고리즘] 전깃줄 (고급, p249)알고리즘 2017. 4. 15. 21:06
이 문제도 풀이가 바로 떠오르지 않을 것 같은 문제이다. 문제에서는 교차하는 전깃줄을 없애는 방법으로 A(왼쪽) 전봇대 위치를 정렬하고난 후, B(오른쪽) 전봇대 위치의 숫자로 만들 수 있는 오름차순 순열의 최대 길이를 구하는 문제로 일단 변경시켰다. 그 다음 IDT (인덱스 트리)를 이용하여, B 전봇대의 값을 차례로 읽으면서 나보다 작은 값들이 몇개 있나를 업데이트 해 나간다. 모든 값을 읽은 다음 제일 윗 칸 즉, IDT 행렬의 첫번째 값이 오름 차순 순열을 만들 수 있는 최대 길이 값이 되고, 전체 입력 개수에서 최대 길이 값 만큼을 뺀 숫자가 결국 없애야 하는 전깃줄의 숫자가 된다는 풀이 내용이다. 풀이에서는 sort (정렬)을 위해 라이브러리를 사용하고 있으나, 여기서는 알고리즘을 배우는 사람..