11개의 댓글이 있습니다.
-
-
wookayin -
풀이의 표현력이 안습이군요.. 좀 더 이해하기 쉽게 적어봤습니다. 정답 스포일러가 있으므로 열어보세요.
문제를 단순화하면 '1 2 3 4 5' 와 '3 1 4 2 5' 을 매칭되는 대로 그을 때 교차점의 개수를 세는 것이죠? A[] = {3, 1, 4, 2, 5} 로 가정하겠습니다. (여기서 A를 순열이라고 표현했습니다)
앞에서부터 차례대로 보면서, 각 A[i] 에 대해,
A1..i-1 중 A[i] 보다 큰 것의 개수를 센 뒤 이들을 모두 합하면 답이 됩니다 (왜그런지는 그림 그리면서 생각해보세요)예를 들자면
- [3] : 0
- 3 [1] : 1 (1보다 큰 것 이전에 한개)
- 3 1 [4] : 0 (4보다 큰 것 이전에 없음)
- 3 1 4 [2] : 2 (2보다 큰 것 3, 4 두개)
- 3 1 4 2 [5] : 0 (5보다 큰 것 없음)
이니까 답이 0+1+0+2+0 = 3 이 됩니다.
그러면 이 개수를 어떻게 세냐 하면, binary indexed tree 라는 자료구조를 사용한다는 것입니다. 이 자료구조의 연산은
- add(x) : x를 집합에 추가
- count(x) : 이미 집합에 들어있는 것 중 x 보다 큰 것의 개수
이며, O(log n)에 구현할 수 있습니다. 이 부분이 궁금하면 다시 코멘트 주세요~
10년 전 link
-
-
-
Being -
"프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략" (구종만, 2012) 제 24장에 구간 트리와 BIT에 대한 설명과 연습 문제가 있습니다 :)
10년 전 link
-
-
-
hyunhwan -
그럴때는 BIT를 고안한 Fenwick이 쓴 논문을 한번 읽어보시는 것도 좋은 방법입니다.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8917
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
canuyes
일전에 풀리지 않는 문제에 대한 해답을 구하기 위해 이곳에 글을 올렸던 적이 있습니다. 그때 너무 명쾌하게 한줄의 조언으로 해결 되었던 기억 덕분에 한번 더 질문 올려봅니다.
문제는 KOI 2013 고등부 3번 문제입니다.
##문제
문제링크
##주최측 풀이
이 문제는,
먼저 기계의 식별 번호들을 단순화 시켜 순열(permutation)을 만든다.
예제에 나온 데이터로 예를 들자면,
윗 줄에 132 392 311 351 231이 나와 있고,
아래 줄에 392 351 132 311 231이 나와 있는데,
윗줄의 132는 아랫줄의 3번째, 윗줄의 392는
아랫줄의 1번째 ... 와 같은 순서로 단순화시킬 수 있다.
예제로 나온 데이터에서의 순열은 3 1 4 2 5가 된다.
그다음 순열의 첫 번째부터 순서대로 보면서,
이전 순열에서 현재 순열 값보다 큰 값이 나온 경우가 교차했다는 의미이므로,
이전 순열에서 자기보다 큰 값이 나온 횟수를 세야한다.
이 과정에서 binary indexed tree를 구성하면
O(nlogn) 시간에 이 횟수를 구할 수 있다.
그 다음 현재의 순열 값을 binary indexed tree에 누적시킨다.
이 과정 역시 O(nlogn) 시간에 할 수 있다.
순열의 마지막까지 이 횟수들을 더해가면,
O(nlogn)간 복잡도로 해를 구할 수 있다.
이 방법으로 해결할 경우 만점을 받도록 test case가 구성되어 있다.
제가 푼 방법으로는 답을 얻어냈는데,
주최측에서 올린 풀이가 전혀 이해가 되지 않네요.
아래의 풀이를 이해하고싶습니다.
10년 전