부호 바꾸기 트릭 : 대소를 바꾼다.

 a>b라면, -a<-b입니다. 이것은 너무 당연한 이야기입니다. 그런데, 이러한 기법을 사용해서 구현이 쉬워진다면, 강력한 툴 중 하나가 되지 않을까요? 실제로, ps를 할 때, 구현을 할 때 굉장히 중요하게 다루어지는 트릭입니다. 예를 들자면, maximum cost min flow 문제를 min cost maximum flow 문제로 변환하는 것도, 부호를 바꿈으로서 할 수 있습니다. 오늘은 간단하지만, 매우 중요한 기법을 간단한 예제와, 문제 상황을 통해 적용해 보는 시간을 가지도록 하겠습니다.

 

 

---

 우선순위 큐는 말 그대로, 우선순위가 가장 높은 원소가 top에 있는 자료구조입니다. 그리고 부모보다 자식이 우선순위가 더 낮습니다. 삽입, 삭제를 해도, 그러한 특성은 유지가 됩니다. 왜 그러한지는 자료 구조 시간에 상세히 설명해 드리도록 하겠습니다.

 

 

먼저, priority_queue는 <queue>를 import 시키면 쓸 수 있습니다. n개의 수를 pq에 넣습니다. 저는 6, 2, 3, 1 순서대로 넣었습니다. 그리고, pq에서 차례대로 빼 보겠습니다.

 

 

 그러면 큰 순서대로 빠집니다. 기본적으로 priority_queue는 MAX HEAP이라고 할 수 있습니다. 즉, 원소가 클 수록 우선 순위가 높다고 생각할 수 있습니다. 그러면, 작은 순서대로 빠지게 하고 싶으면 어떻게 하면 좋을까요?

 

 

 6을 넣었습니다. 그 다음에 2를 넣었습니다. 그러면 어떻게 될까요?

 

 

 2는 6보다 작기 때문에, 우선 순위에서 뒤로 밀립니다. 이제, a>b이면 -a<-b라는 사실을 생각해 봅시다. 그러면 a를 입력받을 때, a 대신에 -a를 넣으면 어떻게 될까요?

 

 

 -6이 되는군요. 다음에 2를 넣을 때는 2 대신에 -2를 넣을 겁니다. 그런데 -2는 -6보다 큰가요?

 

 

 따라서 우선 순위 큐에는 다음과 같이 들어갈 겁니다. 그러면 -2가 -6보다 먼저 빠질 겁니다. 그런데, 우리는 실제 값에다가 -1을 곱한 값을 넣었어요. 따라서, pq에서 차례로 뺄 때, 뺀 값에다가 -1을 곱하면, 원래 값을 얻을 수 있게 됩니다. 이것을 코드로 그대로 구현해 보겠습니다.

 

 

먼저, 10번째 줄을 봅시다. a라는 값을 입력받으면 a 대신에 -a를 넣습니다. 예를 들어, [6, 2, 3, 1]을 입력받으면, pq에는 -6, -2, -3, -1 순으로 들어갈 겁니다. pq의 default는 큰 녀석의 우선 순위가 높습니다. 그러면 -1, -2, -3, -6 순으로 높을 거에요. 따라서, pq에서 계속 원소들을 뺀다면 -1, -2, -3, -6 순서대로 빠질 겁니다.

 

 

 이것은 실 값이 아닙니다. -1을 곱해서 넣었기 때문입니다. pq.top()에 -1을 곱한 값이 실제 값이 되므로, 실제로는 -pq.top()의 값을 출력해 주었습니다.

 

 

 -를 하나 붙여주었을 뿐인데, pq에서 오름차순으로 출력을 해 주었습니다. 마찬가지 기법으로 응용하신다면, int형의 sort의 default 동작은 오름차순입니다. 이것을 내림차순으로 정렬한다고 한다면, -를 붙인 다음에 돌리면 됩니다.

 

 

---

 알고리즘을 조금 하시다 보면, 최장 부분 증가 수열 문제는 많이 들어보실 겁니다. 줄여서 LIS 문제라고 합니다. 그러면 거꾸로 최장 부분 감소 수열도 있지 않을까요? 이를 LDS 문제라고 칭합니다.

 

 

 예를 들자면, [2, 7, 5, 6, 4]의 최장 부분 감소 수열의 길이는 3입니다. 이들은, [7, 5, 4]이거나 [7, 6, 4]입니다. LIS를 nlogn에 구하는 트릭을 배우셨다면 아시겠지만, 사실 깡으로 감소 수열의 길이를 구하는 건 귀찮습니다. LIS에 비해서요. 그러면 이것을 어떻게 해야 할까요? 배열 원소에 -1을 곱해 봅시다.

 

 

 -7 < -6 < -4인가요? [-7, -6, -4]는 최장 증가 수열 중 하나입니다. 수열 A의 부분 감소 수열 B를 b(1), ... , b(n)이라 했을 때, b(1)>b(2)>...>b(n)을 만족합니다. 그러면 -b(1)<-b(2)<...<-b(n)을 만족합니다. -1을 곱하면 부등호 방향이 바뀌기 때문입니다. 즉, -1을 곱했을 뿐인데, 최장 감소 부분 수열의 길이를 구하는 문제가, 최장 증가 부분 수열의 길이를 구하는 문제로 바뀌어 버렸습니다. 문제가 단순화가 된 셈입니다.