Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 증가 부분과 감소 부분이 서로 다른 두 배열에서 나오는 가장 긴 바이토닉 수열 찾기

문제 소개

두 개의 배열이 주어졌을 때, 가장 긴 바이토닉(bitonic) 수열을 찾는 것이 목표입니다. 이때 반드시 지켜야 할 조건은 다음과 같습니다.

  • 증가하는 부분은 반드시 첫 번째 배열(A)의 부분 수열(subsequence)이어야 합니다.
  • 감소하는 부분은 반드시 두 번째 배열(B)의 부분 수열이어야 합니다.

예를 들어 입력이 A = [2, 6, 3, 5, 4, 6], B = [9, 7, 5, 8, 4, 3]이라면 출력은 [2, 3, 4, 6, 9, 7, 5, 4, 3]이 됩니다. 이 수열은 2 → 3 → 4 → 6까지 배열 A에서 추출한 원소들로 증가한 뒤, 9 → 7 → 5 → 4 → 3으로 배열 B에서 추출한 원소들로 감소하는 형태입니다.

알고리즘 접근 방식

핵심 아이디어는 각 배열에 대해 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)을 구한 뒤 이를 연결하는 것입니다. 두 번째 배열 B를 미리 뒤집으면 'B의 최장 감소 부분 수열' 문제가 '뒤집힌 B의 최장 증가 부분 수열' 문제로 변환되기 때문입니다. 효율성을 위해 이진 탐색을 활용한 O(n log n) LIS 알고리즘을 사용합니다.

구체적인 해결 단계는 다음과 같습니다.

  1. index_ceiling() 함수 정의: arr, T, left, right, key를 매개변수로 받는 이진 탐색 함수로, key보다 크거나 같은 값이 처음 나타나는 위치(천장 인덱스)를 찾습니다.
    • right - left > 1인 동안 반복합니다.
    • mid := left + (right - left) // 2로 중간 지점을 계산합니다.
    • arr[T[mid]] >= key이면 right := mid, 그렇지 않으면 left := mid로 갱신합니다.
    • 반복이 끝나면 right를 반환합니다.
  2. long_inc_seq() 함수 정의: 배열 A를 받아 최장 증가 부분 수열을 계산합니다.
    • n := 배열 A의 크기
    • tails_idx := 크기 n의 배열, 0으로 초기화 (각 길이별 LIS 마지막 원소의 인덱스 저장)
    • prev_idx := 크기 n의 배열, -1로 초기화 (경로 복원용 이전 인덱스 저장)
    • length := 1로 초기화
    • i를 1부터 n-1까지 순회하면서:
      • A[i] < A[tails_idx[0]]이면 tails_idx[0] := i로 갱신 (더 작은 시작값 발견)
      • A[i] > A[tails_idx[length - 1]]이면 prev_idx[i] := tails_idx[length - 1], tails_idx[length] := i, length를 1 증가 (LIS 확장)
      • 그 외의 경우 index_ceiling()으로 적절한 위치 pos를 찾아 prev_idx[i] := tails_idx[pos - 1], tails_idx[pos] := i로 갱신
    • 마지막으로 i := tails_idx[length - 1]부터 시작해 prev_idx를 따라 거슬러 올라가며 각 원소를 answer 리스트에 추가해 실제 수열을 복원합니다.
  3. 메인 로직(long_bitonic):
    • n1 := A의 크기, n2 := B의 크기를 구합니다.
    • long_inc_seq(A)를 호출해 A의 최장 증가 부분 수열을 answer에 저장합니다.
    • answer를 뒤집어 올바른 순서로 복원합니다.
    • B를 뒤집은 상태에서 long_inc_seq(B)를 호출하면, 원래 B의 최장 감소 부분 수열이 얻어집니다.
    • answer를 반환합니다.

구현 예제

다음 구현을 통해 더 잘 이해할 수 있습니다.

answer = []
def index_ceiling(arr,T, left,right, key):
    while (right - left > 1):
        mid = left + (right - left) // 2;
        if (arr[T[mid]] >= key):
            right = mid
        else:
            left = mid
    return right
def long_inc_seq(A):
    n = len(A)
    tails_idx = [0]*(n)
    prev_idx = [-1]*(n)
    length = 1
    for i in range(1, n):
        if (A[i] < A[tails_idx[0]]):
            tails_idx[0] = i
        elif (A[i] > A[tails_idx[length - 1]]):
            prev_idx[i] = tails_idx[length - 1]
            tails_idx[length] = i
            length += 1
        else:
            pos = index_ceiling(A, tails_idx, -1, length - 1, A[i])
            prev_idx[i] = tails_idx[pos - 1]
            tails_idx[pos] = i
    i = tails_idx[length - 1]
    while(i >= 0):
        answer.append(A[i])
        i = prev_idx[i]
def long_bitonic(A,B):
    n1 = len(A)
    n2 = len(B)
    global answer
    long_inc_seq(A)
    answer = answer[::-1]
    B = B[::-1]
    long_inc_seq(B)
A = [2, 6, 3, 5, 4, 6]
B = [9, 7, 5, 8, 4, 3]
long_bitonic(A,B)
print(answer)

입력

[2, 6, 3, 5, 4, 6], [9, 7, 5, 8, 4, 3]

출력

[2, 3, 4, 6, 9, 7, 5, 4, 3]

복잡도 분석

두 배열 각각에 대해 이진 탐색 기반 LIS 알고리즘을 한 번씩 적용하므로 전체 시간 복잡도는 O(n log n)입니다. 여기서 n은 각 배열의 길이입니다. 공간 복잡도는 LIS 꼬리 인덱스 배열(tails_idx)과 경로 복원 배열(prev_idx)을 위해 O(n)이 필요합니다.