알고리즘 이론

LIS 알고리즘 및 이진(이분) 탐색

행수쌤 2023. 3. 4. 13:51
728x90
반응형

LIS(Longest Increasing Subsequence)

주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 알고리즘
LIS 알고리즘은 일반적으로 동적 계획법(Dynamic Programming)을 이용하여 O(n^2)의 시간복잡도로 구할 수 있습니다. 각 인덱스에서 끝나는 LIS의 길이를 저장하는 DP 테이블을 만들고, 이전 인덱스들을 순회하며 현재 인덱스의 값보다 작은 값 중에서 가장 긴 LIS를 찾아 현재 인덱스의 DP 테이블 값을 갱신해나가는 방식입니다.

 

동적계획법을 이용한 LIS

public static int lis(int[] arr) {
    int n = arr.length;
    int[] dp = new int[n];  //해당 인덱스의 숫자까지 증가한 숫자의 개수 저장
    Arrays.fill(dp, 1); // 모든 dp 값을 1로 초기화

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);  //가장 큰 값의 +1을 입력
            }
        }
    }

    int maxLis = 0;
    for (int i = 0; i < n; i++) {
        maxLis = Math.max(maxLis, dp[i]);
    }
    return maxLis;
}

이 코드에서는 배열 dp를 만들어 이전 원소들과 비교하며 LIS의 길이를 저장합니다. 각 dp[i] 값은 i번째 원소를 마지막 원소로 하는 LIS의 길이를 의미합니다. 이전 원소들과 비교하며 arr[i]보다 작은 값이 있다면, 해당 원소를 마지막 원소로 하는 LIS의 길이에 1을 더한 값과 dp[i]를 비교하여 더 큰 값을 선택합니다. 마지막으로 dp 배열에서 최대값을 찾아 반환합니다.

 

이진 탐색(Binary Search)

이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 찾는 탐색 알고리즘입니다. 배열의 중간에 위치한 값을 기준으로 탐색 대상을 반으로 나누어 찾는 값이 왼쪽에 있는지 오른쪽에 있는지를 결정하고, 반복적으로 탐색 대상을 반으로 줄여가면서 원하는 값을 찾아냅니다.
이진 탐색 알고리즘의 시간 복잡도는 O(log n)으로, 배열의 크기가 커질수록 비교 횟수가 적어져서 탐색 속도가 빨라집니다.
아래는 이진 탐색의 동작 예시입니다. 배열 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]에서 6을 찾아보겠습니다.
  1. 탐색 대상의 중간 값을 선택합니다. 배열의 중간은 5번째 인덱스(인덱스 0부터 시작)의 값 5입니다.
  2. 찾고자 하는 값 6이 5보다 크므로, 오른쪽 부분 배열 [6, 7, 8, 9, 10]을 탐색 대상으로 선택합니다.
  3. 탐색 대상의 중간 값을 선택합니다. 배열의 중간은 8번째 인덱스(인덱스 0부터 시작)의 값 9입니다.
  4. 찾고자 하는 값 6이 9보다 작으므로, 왼쪽 부분 배열 [6, 7, 8]을 탐색 대상으로 선택합니다.
  5. 탐색 대상의 중간 값을 선택합니다. 배열의 중간은 7번째 인덱스(인덱스 0부터 시작)의 값 7입니다.
  6. 찾고자 하는 값 6이 7보다 작으므로, 왼쪽 부분 배열 [6]을 탐색 대상으로 선택합니다.
  7. 탐색 대상의 중간 값을 선택합니다. 배열의 중간은 6번째 인덱스(인덱스 0부터 시작)의 값 6입니다.
  8. 찾고자 하는 값 6과 일치하므로, 6을 찾았습니다.

public static int binarySearch(int[] arr, int target) {
    int left = 0;  //탐색 부분의 왼쪽 끝
    int right = arr.length - 1;  //탐색 부분의 오른쪽 끝

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid; // 탐색 성공, 중간 값 인덱스 반환
        } else if (arr[mid] < target) {
            left = mid + 1; // 탐색 대상을 오른쪽 부분 배열로 축소
        } else {
            right = mid - 1; // 탐색 대상을 왼쪽 부분 배열로 축소
        }
    }

    return -1; // 탐색 실패, -1 반환
}

이진 탐색을 수행하는 함수 binarySearch는 정렬된 배열 arr과 찾고자 하는 값 target을 인자로 받습니다. 변수 left와 right는 각각 배열의 가장 왼쪽 인덱스와 가장 오른쪽 인덱스를 가리키며, mid는 탐색 대상의 중간 인덱스를 나타냅니다.

탐색 대상이 될 배열의 범위를 나타내는 left와 right를 각각 0과 arr.length - 1로 초기화합니다. 그리고 반복문을 실행하는데, left가 right보다 작거나 같은 동안(즉, 아직 탐색 대상이 있는 동안) 반복합니다.

반복문 내부에서는 중간 인덱스 mid를 계산하고, 이를 기준으로 arr[mid]가 target과 같은지 비교합니다. 만약 같다면, mid를 반환하면서 탐색을 종료합니다. 만약 arr[mid]가 target보다 작다면, 탐색 대상을 오른쪽 부분 배열로 축소합니다. 그리고 arr[mid]가 target보다 크다면, 탐색 대상을 왼쪽 부분 배열로 축소합니다.

반복문을 다 돌았는데도 원하는 값을 찾지 못했다면, 탐색 실패를 알리기 위해 -1을 반환합니다.

 

이진탐색을 이용한 LIS

이진 탐색(Binary Search)을 이용하면 O(n log n)의 시간복잡도로 LIS를 구할 수도 있습니다. 이 경우, 주어진 수열을 순회하면서 LIS의 끝을 저장하는 배열을 만들고, 각 숫자를 순회하며 이진 탐색을 이용하여 새로운 LIS를 만들거나 기존의 LIS를 갱신합니다. 이 방법은 구현이 좀 더 복잡하지만, 성능이 더 우수합니다.

import java.util.Arrays;

public class LIS {
    public static void main(String[] args) {
        int[] arr = {3, 2, 6, 4, 5, 1};
        int[] lis = new int[arr.length];
        int len = 0;
        
        for (int n : arr) {
            int idx = Arrays.binarySearch(lis, 0, len, n);
            //존재하는 위치(해당 없음) 또는 넣어야 되는 위치 판단
            if (idx < 0) {
                idx = -(idx + 1);  //넣어야 되는 인덱스 계산
            }
            lis[idx] = n;	//자기 인덱스 자리에 있던 숫자를 지우고 들어감
            if (idx == len) {
                len++;  //넣어야 되는 수가 가장 큰 수여서 마지막에 들어가면 len++
            }
        }
        
        System.out.println(len); // 출력: 3
    }
}

위 코드에서는 배열 arr의 LIS를 구합니다. lis 배열은 현재까지 만들어진 LIS를 저장하며, len 변수는 현재까지 구한 LIS의 길이를 저장합니다. 배열 arr을 순회하며, 각 숫자를 lis 배열에 삽입합니다. 이진 탐색을 이용하여 새로운 LIS를 만들거나 기존의 LIS를 갱신합니다. 삽입할 위치 idx가 lis 배열의 끝을 가리키면 len 변수를 증가시킵니다. 마지막으로 len 변수에 저장된 값이 LIS의 길이가 됩니다.

728x90
반응형