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

구현 2019. 10. 19. 23:49

 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을 곱했을 뿐인데, 최장 감소 부분 수열의 길이를 구하는 문제가, 최장 증가 부분 수열의 길이를 구하는 문제로 바뀌어 버렸습니다. 문제가 단순화가 된 셈입니다.