[Algo Smash] Week03 - BOJ1940, BOJ1253, PGS 178870

BOJ 1940번: 주몽

1) 접근 방법

첫째 줄의 재료의 개수(n)가 주어지고, 두 번째에 두 재료의 수를 합쳐서 만들어야 하는 수(m)가 주어진다. 즉, arr[n]에 있는 숫자들 중 2개의 덧셈이 m이 되는 개수를 찾으면 된다.

처음에 생각했던 방법은 단순하게 이중 for문을 사용해서 가능한 모든 조합의 수를 다 고려하는 방법이 떠올랐다. 하지만 이렇게 되면 시간 복잡도가 O(N*N)이고, N이 최대 15,000이기 때문에 시간 초과가 날 수 있다고 생각했다.

대신 두 개의 재료만 선택하면 되므로, 배열을 정렬한 뒤 양 끝에서 범위를 좁혀서 탐색하는 알고리즘을 선택했다.

1. 데이터를 오름차순으로 정렬
2. 포인터 이동 규칙:

• arr[start] + arr[end] == M: 조건 만족을 했으므로 result를 증가시키고, 양쪽 포인터를 모두 안쪽으로 이동
• arr[start] + arr[end] < M: 합이 작으므로 더 큰 값이 필요 -> start를 오른쪽으로 한 칸 이동
• arr[start] + arr[end] > M: 합이 크므로 더 작은 값이 필요 -> end를 왼쪽으로 한 칸 이동

2) 구현 코드

#include <iostream>
#include <algorithm>

using namespace std;


int main() {
    int n, m;
    cin >> n >> m;

    int arr[15001];

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

    // 배열 정렬하기 
    sort(arr, arr + n);

    // 정렬한 배열의 가장 앞, 가장 뒤부터 접근하면서 판단
    int start = 0;
    int end = n - 1;
    int result = 0;
    while (start < end) {
        // 두개의 재료 덧셈이 m과 같다면 result++; 
        if (arr[start] + arr[end] == m) {
            result++;
            start++;
            end--;
        }
        // m보다 작으니까 start index +1; 
        else if (arr[start] + arr[end] < m) {
            start++;
        }
        else {
            end--;
        }
    }

    cout << result << endl;

    return 0;
}

3) 시간 복잡도

sort()의 시간 복잡도 O(N logN)와 배열 한 번 훑는 시간 복잡도 O(N)를 더하면 된다.
따라서 최종 시간 복잡도는 O(N logN)이다.

---

BOJ 1253: 좋다

1) 접근 방법

N개의 원소가 저장된 배열에서 어떤 수가 다른 수 두 수의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”라고 한다.

두 수의 합이 특정 타겟과 같은지 확인하는 과정은 위에서 풀엇던 투 포인터 방식과 비슷하다고 생각했다. 따라서 isGOOD 함수를 따로 분리하여 여기에 1940번의 알고리즘을 사용하였다.

이전 문제와 다른 점은 타겟이 되는 수의 인덱스도 포함된다. 따라서, start나 end 같은 투 포인터가 타켓의 인덱스는 포함되지 않도록 하는 조건문을 추가하였다.

2) 구현 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[2000];

bool isGOOD(int targetIdx, int n) {
    int target = arr[targetIdx]; 
    int start = 0; 
    int end = n - 1;

    while (start < end) { 
        // 자기 자신은 포함될 수 없음 
        if (start == targetIdx) {
            start++; 
            continue; 
        }
        if (end == targetIdx) {
            end--; continue; 
        }

        int currentSum = arr[start] + arr[end];

        // 두 수의 합이 타겟과 같은지 확인
        if (currentSum == target) {
            return true; // GOOD이며 바로 true 반환
        }
        else if (currentSum < target) {
            start++;
        }
        else {
            end--;
        }
    }

    return false; // 끝까지 못 찾아내면 false 
}


int main() {
    int n; 
    cin >> n; 

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

    sort(arr, arr + n); 

    int result_count = 0;

    for (int i = 0; i < n; i++) {
        if (isGOOD(i, n)) {
            result_count++;
        }
    }

    cout << result_count << endl; 

    return 0;
}

3) 시간 복잡도

sort 함수의 시간 복잡도 O(N logN)와 for문을 통해 isGOOD함수를 실행하는 시간 복잡도가 O(NN)이기 때문에 최종 시간 복잡도는 O(NN)이다.

---

PGS178870: 연속된 부분 수열의 합

1) 접근 방법

처음에는 start_index, end_index, start_result, end_result 등 4개의 변수를 가지고 비교를 하면서 더 짧은 배열을 찾으려고 했는데, 그럴 필요가 없엇다..

대신, {0, (최대길이)}와 같이 2개의 원소를 가진 answer이라는 벡터를 하나 만들고, total==k인(total은 부분 수열의 합) 구간을 찾을 때마다 현재 길이와 비교해 더 짧은 경우에만 갱신하는 방식을 사용했다.

[조건문 규칙]

• total < k: 합이 부족하므로 ei를 증가한다.
• total > k: 합이 초과했으므로 si가 가리키는 값을 빼고 si를 증가시킨다.
• total == k: 더 짧은 수열인지 판단 후 갱신하고, si를 늘려 탐색을 계속한다.

포인터의 추적 결과를 다음과 같이 정리해 보았다.

2) 구현 코드

#include <vector>

using namespace std; 

vector<int> solution(vector<int> sequence, int k) {
    int si = 0, ei = 0;
    int total = sequence[0];

    // 배열을 [0, (최대길이)]로 초기화  
    vector<int> answer = { 0, (int)sequence.size() - 1 };

    while (ei < (int)sequence.size()) {
        if (total < k) {
            ei++;
            if (ei < (int)sequence.size()) total += sequence[ei];
        }
        else if (total > k) {
            total -= sequence[si];
            si++;
        }
        else {  // total == k
            // 더 짧은 수열이면 갱신
            if ((ei - si) < (answer[1] - answer[0])) {
                answer = { si, ei };
            }
            // 같은 합을 가진 더 짧은 수열이 있을 수 있으니 계속 탐색
            total -= sequence[si];
            si++;
        }
    }

    return answer;
}

3) 시간 복잡도

수열이 비내림차순으로 정렬되어 주어지기 때문에 si와 ei를 통해서 배열을 왼쪽에서 오른쪽으로 이동하면 되기 때문에 전체 시간복잡도는 O(N)이다.