투 포인터, 그리디

투 포인터(Two Pointer)

투 포인터(Two Pointer) 알고리즘은 리스트나 배열과 같은 순차 자료 구조에서 두 개의 포인터를 이용하여 원하는 구간을 탐색하는 알고리즘이다.

 

일반적으로, 리스트나 배열에서 연속된 구간을 탐색할 때, 시작 인덱스와 끝 인덱스를 정하여 반복문을 사용하여 구간을 탐색한다. 그러나 투 포인터 알고리즘은 시작 포인터와 끝 포인터 두 개의 포인터를 이용하여 구간을 탐색한다.

 

투 포인터 알고리즘은 두 개의 포인터를 이용하여 구간을 효율적으로 탐색할 수 있다. 시작 포인터와 끝 포인터를 이용하여 구간을 지정하고, 이 구간을 이동하면서 원하는 조건에 맞는 값을 찾아나갈 수 있다.

 

작동 방식

예를 들어, 오름차순으로 정렬된 정수 배열에서 두 수의 합이 주어진 값과 같은 원소의 인덱스를 찾는 문제를 생각해자. 이 경우, 시작 포인터와 끝 포인터를 이용하여 투 포인터 알고리즘을 적용할 수 있다.

 

1. 시작 포인터와 끝 포인터를 초기화한다. 시작 포인터는 배열의 첫 번째 인덱스를 가리키고, 끝 포인터는 배열의 마지막 인덱스를 가리킨다.
2. 시작 포인터와 끝 포인터가 가리키는 값의 합을 구한다.
3. 합이 주어진 값보다 작으면 시작 포인터를 오른쪽으로 이동한다. 합이 주어진 값보다 크면 끝 포인터를 왼쪽으로 이동한다.
4. 합이 주어진 값과 같으면, 해당 인덱스를 반환한다.
5. 시작 포인터가 끝 포인터보다 크거나 같아지면, 원하는 값이 없으므로 -1을 반환한다.

public static int[] twoSum(int[] nums, int target) {
    int start = 0;
    int end = nums.length - 1;

    while (start < end) {
        int sum = nums[start] + nums[end];
        if (sum == target) {
            return new int[]{start, end};
        } else if (sum < target) {
            start++;
        } else {
            end--;
        }
    }

    return new int[]{-1, -1};
}

 

다른 예시와 함께 다시 투포인터에 대해서 정리 헤보자. 정렬되지 않은 배열에서 p1과 p2를 같은 인덱스에서 시작하는 방식이다.

 

1. 배열에서 부분합이 9가 되는 구간을 찾고자 한다. 
2. target 이 부분합보다 작으면 p1의 값이 증가한다. 
3. target 이 부분합보다 크다면 p2의 값이 증가한다. 
4. p1과 p2를 증가하는 과정에서 target과 같다면 p1, p2값을 반환한다. 
5. 끝까지 발견하지 못한다면 -1을 반환한다. 

 

public static int[] forLoop(int[] arr, int target) {
    int[] result = {-1, -1};

    for (int i = 0; i < arr.length; i++) {
        int sum = arr[i];
        for (int j = i + 1; j < arr.length; j++) {
            if (sum == target) {
                result[0] = i;
                result[1] = j - 1;
                break;
            }
            sum += arr[j];
        }

        if (sum == target) {
            break;
        }
    }

    return result;
}

 

투포인터의 알고리즘 복잡도는 n + n 이기 때문에 O(2n)이다. 하지만 시간 복잡도에서 상수항은 무시되기 때문에 O(2n)과 O(n)은 동일한 시간 복잡도를 갖는다. 따라서, O(2n) 대신에 O(n)으로 표기하는 것이 일반적이다. 

 

이러한 현상이 일어나는 이유는 알고리즘의 시간 복잡도는 입력 크기에 따라 연산 횟수가 증가하는 비율을 나타내는데, 상수항은 입력 크기와 무관하게 일정한 값이기 때문에 시간 복잡도에 영향을 미치지 않는다. 

 

예를 들어, 만약 입력 크기 n에 대해서 알고리즘의 시간 복잡도가 2n^2 + 3n + 1 이라면, O(2n^2 + 3n + 1)은 O(n^2)로 간략화가 된다. 여기서 2는 상수항으로 무시되고, 가장 높은 차수인 n^2에 대한 항만을 남기기 때문이다. 

---

그리디(Greedy)

그리디 알고리즘(Greedy algorithm)은 최적해를 구하는 데 사용되는 근시안적인 방법이다. 그리디 알고리즘은 각 단계에서 최적이라고 생각되는 선택을 만들어나가는 알고리즘이다. 매 순간 가장 최선의 선택을 계속해서 하는 방식으로 문제를 해결한다.

https://velog.io/@timointhebush/%EA%B7%B8%EB%A6%AC%EB%94%94%ED%83%90%EC%9A%95-Greedy-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그리디 알고리즘은 아래와 같은 특징을 갖는다.

• 탐욕 선택 속성(Greedy choice property): 각 단계에서 가장 최적의 선택을 한다.
• 최적 부분 구조(Optimal substructure): 각 단계의 최적해가 전체 문제의 최적해를 이룬다.

그리디 알고리즘은 많은 문제에 대해 최적해를 구할 수 있지만, 반드시 모든 문제에서 최적해를 구할 수 있는 것은 아니다. 이는, 각 단계에서의 선택이 최적이지만 전체적으로는 최적이 아닐 수 있기 때문이다. 때문에 그리디 알고리즘이 사용될 수 있는 문제들은 일반적으로 특별한 조건을 갖추고 있다.

 

예를 들어, 거스름돈 문제를 생각해보자. 거스름돈 문제는 n원을 거슬러 줄 때 가장 적은 동전의 수를 구하는 문제이다. 이 문제는 그리디 알고리즘을 이용하여 풀 수 있는 문제로, 각 단계에서 가장 큰 동전을 선택하여 거스름돈을 줄여나가면 최소한의 동전 수로 거스름돈을 줄 수 있기 때문이다.