간단한 문제 골라풀기... 퀵 소트를 한 번 써보고 싶단 생각에 정렬 파트 문제를 (쉬운걸로) 풀어보았다.
이 문제는 정렬을 할 수 있느냐를 묻는 문제이다.
이러한 문제는 사실 어떤 정렬을 써도 상관은 없을 것이다. 하지만, 퀵 소트나, 머지 소트정도는 사용해 주는 것이 나중의 응용을 위해서도 좋을 것이다.
퀵 소트 개념에 대해 설명하면 좋겠지만, 차후 시간이 나면 설명하도록 하겠다. 알고 있다는 가정하에, 혹은 어떤 정렬이든 사용한다는 가정하에, 문제를 풀도록 한다.
문제는 A, B의 배열들을 원소들끼리 곱해 가장 작은 값이 나오도록 하는 것이다.
그러려면, A의 가장 작은 값과 B의 가장 큰 값을 곱해주어야 한다. 그 말은 A의 가장 큰 값과 B의 가장 작은 값을 곱하는 것을 의미하기도 한다.
A와 B가 정렬된 [0, n-1] 크기의 배열이라고 한다면, A[0]*B[n-1] + ... + A[k]*B[n-1-k] + ... + A[n-1]*B[0] 와 같은 식이 필요하다는 것이다.
이를 반복문을 통해 구현하기만 하면 된다.
코드는 위에 두가지를 첨부한다. 첫 번째 코드는 c++의 algorithm 헤더에서 제공하는 sort를 사용하는 것이고, 두 번째 코드는 quick sort를 직접 구현한 것이다. 다른 정렬 함수를 통해 정렬 한 후, 같은 알고리즘으로 문제를 풀어도 괜찮다.
대부분의 경우 sort를 사용할 수 있으므로 sort 사용법을 숙지하고, 당연히 quick sort의 구현 방식이나 구현할 능력은 갖추고 있어야 할 것이다.
EmoticonEmoticon