[BOJ알고리즘, C++]#3273_두 수의 합, 퀵 정렬, 투 포인터

 

#1. 문제

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

---

 

#2. 풀이

 

1. 퀵 정렬

https://webddevys.tistory.com/307#%236.%20%ED%80%B5%20%EC%A0%95%EB%A0%AC-1

[알고리즘]#3_정렬 알고리즘

 

[정의] : 퀵 정렬 알고리즘은 분할-정복 기반의 정렬 알고리즘입니다. 퀵 정렬은 피벗 원소를 기준으로 왼쪽은 이보다 작은 원소들, 오른쪽은 큰 원소들로 분할하는 작업을 더 이상 분할할 수 없는 크기까지 재귀적으로 수행하여, 최종적으로 하나의 정렬된 배열을 얻습니다. 

[성능] : 퀵 정렬 알고리즘의 평균 시간 복잡도는 O(n log n)으로, 이미 정렬된 상태이거나 역순으로 정렬된 상태에서 피벗 원소를 오른쪽 끝에 위치한 원소로 선택할 경우, O(n²) 시간 복잡도를 갖습니다. 이를 방지하기 위해, median-of-three 최적화를 활용할 수 있습니다.

 

2. 투 포인터

https://webddevys.tistory.com/351

[알고리즘]#7_투 포인터

 

[정의] : 투 포인터 알고리즘은 두 개의 포인터를 활용해 원하는 조건을 만족하는 부분을 찾는 알고리즘입니다. 일반적으로, 투 포인터 알고리즘은 정렬된 배열에서 활용됩니다.

 

3. 정렬하고 투 포인터 알고리즘을 통해 조건을 만족하는 쌍을 찾는다!

1. 먼저, 주어진 배열에 대해 퀵 정렬을 수행합니다.
2. 그리고, 두 개의 포인터를 각각 배열의 첫 번째 위치와 마지막 위치로 초기화하고, 투 포인터 알고리즘을 수행하며 조건을 만족하는 쌍을 찾습니다!

 

---

 

#3. 코드

 

1. sort 함수 활용 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int x;
    cin >> x;

    sort(arr.begin(), arr.end());

    int start = 0;
    int end = n - 1;
    int cnt = 0;

    while (start < end) {
        int sum = arr[start] + arr[end];
        if (sum == x) {
            cnt++;
            start++;
            end--;
        } else if (sum < x) {
            start++;
        } else {
            end--;
        }
    }

    cout << cnt;

    return 0;
}

 

2. 퀵 정렬 활용 코드

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int n, x;
vector<int> v;

int MedianOfThree(vector<int>& arr, int l, int r)
{
    int m = l + (r-l)/2;
    
    if(arr[l] > arr[m])
        swap(arr[l], arr[m]);

    if(arr[l] > arr[r])
        swap(arr[l], arr[r]);

    if(arr[m] > arr[r])
        swap(arr[m], arr[r]);

    return m;
}

int Partition(vector<int>& arr, int l, int r)
{
    int pivIdx = MedianOfThree(arr, l, r);
    swap(arr[pivIdx], arr[r]);

    int piv = arr[r];
    int i = l-1;

    for(int j=l; j<r; ++j)
    {
        if(arr[j] <= piv)
        {
            ++i;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i+1], arr[r]);

    return i+1;
}

void QuickSort(vector<int>& arr, int l, int r)
{
    if(l < r)
    {
        int piv = Partition(arr, l, r);

        QuickSort(arr, l, piv-1);
        QuickSort(arr, piv+1, r);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    v.resize(n);

    for(int i=0; i<n; ++i)
    {
        cin >> v[i];
    }

    cin >> x;

    // #1. 퀵 정렬
    QuickSort(v, 0, n-1);

    // #2. 투 포인터
    int left = 0;
    int right = n-1;
    int ans = 0;

    while(left <= right)
    {
        // #1. x와 같을 경우
        if(v[left] + v[right] == x)
        {
            ans++;
            left++;
            right--;
        }
        // #2. x보다 작을 경우, left(시작점)을 오른쪽으로 1칸 이동
        else if(v[left] + v[right] < x)
        {
            left++;
        }
        // #3. x보다 클 경우, right(끝)을 왼쪽으로 1칸 이동
        else{
            right--;
        }
    }

    cout << ans;

    return 0;
}

 

---