[최적화 및 문제풀이] 두 개의 정렬된 배열에서 공통 원소 찾는 문제

정렬된 두 배열에서 공통 원소를 찾는 문제문제를 해결하기 위해 Brute Force 방식부터 시작하여, 이진 탐색을 이용한 방법으로 개선, 최종적으로 Two-Pointer 접근법을 통해 BCR (Best Conceivable Runtime)인 O(N)에 도달하는 과정을 단계별로 설명하겠습니다.

 

 

목차

 

 

두 개의 정렬된 배열에서 공통 원소 찾는 문제

문제: 정렬된 배열 두 개가 주어졌을 때 공통으로 들어 있는 원소를 출력하세요. 두 배열의 길이는 같고 하나의 배열 안에서 동일한 원소는 하나만 존재한다.

A, B 배열

 

Brute Force 접근법 (O(N^2))

Brute Force 방식은 두 배열의 모든 원소를 비교하여 공통 원소를 찾는 방법입니다. 시간 복잡도는 O(N^2) 이며, 매우 비효율적입니다.

    public static List<Integer> findCommonElements(int[] A, int[] B) {
        List<Integer> commonElements = new ArrayList<>();

        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                if (A[i] == B[j]) {
                    commonElements.add(A[i]);
                }
            }
        }

        return commonElements;
    }

 

지금까지 우리는 O(N^2) 알고리즘을 생각했고, 이보다 나은 알고리즘을 찾고 싶습니다. 두 배열이 모두 정렬되어 있고 중복이 없다면, 두 배열을 한 번씩만 탐색하여 교차점(공통 원소)을 찾는 것이 최선입니다. 이 경우의 BCR은 O(N) 입니다.

 

BCR (Best Conceivable Runtime)이란?

BCR (Best Conceivable Runtime)은 주어진 문제에서 이론적으로 가능한 최선의 수행 시간을 의미합니다. 이는 문제의 구조나 입력 데이터의 특성에 의해 결정되며, 더 이상 최적화가 불가능한 시간 복잡도를 나타냅니다. BCR은 알고리즘 설계와 분석에서 중요한 기준점으로 사용됩니다. 개발자는 BCR을 바탕으로 자신이 설계한 알고리즘이 최적에 가까운지를 평가할 수 있습니다.

 

현재 알고리즘의 수행 시간이 O(N * N) 인데, 이를 개선하면 O(N) 또는 O(N * log N)으로 개선할 수 있습니다. 탐색하는 부분에 의해 두 번째 O(N)이 나왔는데, 배열이 정렬되어 있기 때문에 이진 탐색(O(log N))을 이용하여 개선할 수 있습니다.

 

이진 탐색을 이용한 최적화 (O(N log N))

Brute Force의 비효율성을 줄이기 위해, 이진 탐색(Binary Search)을 활용하여 성능을 개선할 수 있습니다. 배열 A의 각 원소에 대해 배열 B에서 이진 탐색을 수행하여 공통 원소를 찾는 방법입니다. 이 방법의 시간 복잡도는 O(N log N) 입니다.

    public static List<Integer> findCommonElements(int[] A, int[] B) {
        List<Integer> commonElements = new ArrayList<>();

        for (int i = 0; i < A.length; i++) {
            if (Arrays.binarySearch(B, A[i]) >= 0) {
                commonElements.add(A[i]);
            }
        }

        return commonElements;
    }

 

이진 탐색을 통한 최적화의 원리

• 이진 탐색은 정렬된 배열에서 특정 원소를 빠르게 찾기 위한 방법으로, 시간 복잡도가 O(log N) 입니다.
• 배열 A의 각 원소에 대해 배열 B에서 이진 탐색을 수행하여 공통 원소를 찾습니다.
• 이 방법은 O(N^2)에서 O(N log N)으로 성능을 크게 향상시킵니다.

 

이진 탐색(O(log N)을 해시테이블을 이용하여 탐색 시간 O(1)으로 줄여서 O(N * log N) 시간 복잡도를 O(N) 시간복잡도를 가지는 알고리즘은 변환할 수 있습니다. 

해시테이블을 이용한 최적화 (O(N))

배열 B의 원소들을 해시 테이블(HashMap)에 저장한 뒤, 배열 A의 원소들을 빠르게 검색하여 공통 원소를 찾는 방법입니다. 이 방법의 시간 복잡도는 O(N) 입니다.

    public static List<Integer> findCommonElements(int[] A, int[] B) {
        List<Integer> commonElements = new ArrayList<>();
        HashMap<Integer, Boolean> map = new HashMap<>();

        for (int i = 0; i < B.length; i++) {
            map.put(B[i], true);
        }

        for (int i = 0; i < A.length; i++) {
            if (map.containsKey(A[i])) {
                commonElements.add(A[i]);
            }
        }

        return commonElements;
    }

 

해시테이블을 통한 최적화의 원리

• 해시 테이블(HashMap) 생성:
  HashMap<Integer, Boolean> 타입의 map을 생성하여, 배열 B의 원소를 키(key)로 저장합니다. 값(value)은 단순히 존재를 표시하기 위해 true로 설정했습니다.
• 배열 B의 원소를 해시 테이블에 저장:
  for 루프를 사용하여 배열 B의 모든 원소를 map에 저장합니다.
• 배열 A의 원소를 검색:
  배열 A의 원소를 하나씩 탐색하면서, map에서 해당 원소가 존재하는지 확인합니다. 공통 원소가 발견되면, 그 값을 commonElements 리스트에 추가합니다.

배열 A의 원소를 검색하는 데 O(1) 의 시간 복잡도를 가진 해시 테이블을 사용하므로, 배열 A를 순회하는 데 O(N) 의 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(N) 입니다.

 

더 개선할 수 있을까?

우리는 BCR에 의해 O(N)보다 더 빠를 수 없다는 것을 알고 있고, 해시테이블을 이용한 알고리즘은 O(N) 공간에서 동작하고 있습니다. 이제 공간 복잡도를 개선할 수 있는지 생각해볼 수 있습니다.

 

O(N) 공간보다 더 적은 공간을 사용하겠다는 말은 해시테이블을 사용하지 않아야 한다는 이야기입니다. 또한 공간 복잡도를 개선하기 위해 시간 복잡도를 손해보지 않아야 합니다. 지금까지 추가 공간을 사용하지 않는 알고리즘 중에 최선의 알고리즘은 이진 탐색을 이용한 알고리즘이었습니다. 이진 탐색을 이용한 알고리즘부터 최적화를 다시 생각해보겠습니다.

    public static List<Integer> findCommonElements(int[] A, int[] B) {
        List<Integer> commonElements = new ArrayList<>();

        for (int i = 0; i < A.length; i++) {
            if (Arrays.binarySearch(B, A[i]) >= 0) {
                commonElements.add(A[i]);
            }
        }

        return commonElements;
    }

• A[0]를 B에서 이진 탐색한다. (찾지 못함)
• A[1]를 B에서 이진 탐색한다. (찾지 못함)
• A[2]를 B에서 이진 탐색한다. (B[1]에서 찾음)
• ...
• A[6]를 B에서 이진 탐색한다. (찾지 못함) 

A 배열의 아이템이 B 배열에 존재하는지 찾을 때, B 배열에서 이진 탐색을 하는 것에 주목할 필요가 있습니다. 이를 개선하기 위한 실마리를 찾기 위해, 이전에 문제를 풀 때 사용하지 않은 배열이 정렬되어 있다는 조건에 주목해야 합니다.

 

문제에는 배열이 정렬되어 있다는 조건이 명시되어 있는데, 이를 어떻게 이용할 수 있을까요?

A[0] = 13을 B 배열에서 찾기 위해, B[0] = 17 다음을 확인해볼 필요가 없습니다. B 배열은 정렬되어 있기 때문에 B[1]은 17보다 큰 수임을 알 수 있습니다. A[0]가 B 배열에 있는지 확인하는 것은 B[0]에서 종료할 수 있습니다.

이와 같은 방법을 통해 B 배열을 선형 탐색(linear search)하는 것으로 이진 탐색과 같은 효과를 낼 수 있습니다.

 

Two-Pointer 기법 (O(N))

두 배열이 이미 정렬되어 있다는 특성을 이용하면 Two-Pointer 기법을 통해 더 효율적인 알고리즘을 설계할 수 있습니다. 이 방법은 O(1) 공간 복잡도, 그리고 O(N) 의 시간 복잡도를 가지게 됩니다.

알고리즘 도식화

1. A[0]을 B에서 선형 탐색한다. B[0]에서 시작(노란 화살표), B[0]에서 종료(파란 화살표)한다. (찾지 못함)
2. A[1]을 B에서 선형 탐색한다. B[0]에서 시작(노란 화살표), B[1]에서 종료(파란 화살표)한다. (찾지 못함)
3. A[2]을 B에서 선형 탐색한다. B[1]에서 시작(노란 화살표), B[1]에서 종료(파란 화살표)한다. (찾음)
4. A[3]을 B에서 선형 탐색한다. B[2]에서 시작(노란 화살표), B[3]에서 종료(파란 화살표)한다. (찾음)
5. A[4]을 B에서 선형 탐색한다. B[4]에서 시작(노란 화살표), B[4]에서 종료(파란 화살표)한다. (찾지 못함)
6. ...

    public static List<Integer> findCommonElements(int[] A, int[] B) {
        List<Integer> commonElements = new ArrayList<>();

        int i = 0, j = 0;

        while (i < A.length && j < B.length) {
            if (A[i] == B[j]) {
                commonElements.add(A[i]);
                i++;
                j++;
            } else if (A[i] < B[j]) {
                i++;
            } else {
                j++;
            }
        }

        return commonElements;
    }

 

Two-Pointer 접근법의 원리

• 포인터 두 개를 사용하여 각 배열의 처음부터 시작합니다.
• 두 포인터가 가리키는 값이 같으면 공통 원소로 간주하고, 두 포인터를 모두 다음 원소로 이동시킵니다.
• 두 값이 다르면, 더 작은 값을 가리키는 포인터를 증가시킵니다.
• 이 방법은 각 배열을 한 번만 탐색하므로 O(N) 시간 복잡도를 가집니다.

 

정렬된 두 배열에서 공통 원소를 찾는 문제를 Brute Force 방식에서 시작하여, 이진 탐색을 통한 O(N log N) 개선, 해시테이블을 통한 O(N), 그리고 최종적으로 공간 복잡도까지 고려한 Two-Pointer 기법을 이용해 O(N) 으로 최적화하는 과정을 살펴보았습니다.