[Algorithm] LIS (Longest Increasing Subsequence) : 가장 긴 증가 부분 수열 알고리즘 이해하기

LIS (Longest Increasing Subsequence) 알고리즘 이해하기

프로그래밍에서 가장 긴 증가 부분 수열(Longest Increasing Subsequence, LIS) 문제는 배열 데이터 분석, 최적화, 또는 게임 개발과 같은 다양한 분야에서 중요한 문제로 자주 등장합니다. 그렇다면, 주어진 배열에서 순서를 유지하며 가장 긴 증가하는 수열을 찾으려면 어떻게 해야 할까요?

LIS 알고리즘은 이런 문제를 해결하는 강력한 도구입니다. 특히, 배열 내 숫자들의 증가 패턴을 찾아내고, 이를 효율적으로 계산하는 방법을 제시합니다. 이 글에서는 LIS란 무엇인지, 동적 프로그래밍과 이진 탐색을 활용한 구현 방법, 그리고 실무적 활용 사례까지 자세히 다룹니다.

LIS 알고리즘의 개념

LIS란 무엇인가요?

LIS는 주어진 배열에서 순서를 유지하면서 증가하는 가장 긴 부분 수열을 의미합니다. 여기서 중요한 점은 배열의 순서를 유지해야 하며, 연속적일 필요는 없다는 것입니다. 즉, 숫자들이 배열에서 떨어져 있어도 순서만 맞다면 부분 수열로 인정됩니다.

예시

• 입력 배열: [10, 22, 9, 33, 21, 50, 41, 60]
• LIS: [10, 22, 33, 50, 60]
• LIS의 길이: 5

위의 예시에서 LIS는 [10, 22, 33, 50, 60]과 같이 배열 내에서 순서를 유지하며 길이가 가장 긴 증가 부분 수열입니다.

LIS 문제의 특징

• 배열은 정렬되어 있지 않으며, 임의의 숫자가 섞여 있을 수 있습니다.
• 증가 조건과 배열의 순서 조건을 만족해야 합니다.
• 최종 목표는 LIS의 길이를 구하거나 실제 수열을 구하는 것입니다.

LIS 알고리즘의 접근 방식

동적 프로그래밍 방식 (O(N²))

LIS 문제를 해결하는 가장 대표적인 방법은 동적 프로그래밍(Dynamic Programming, DP)입니다.
이 방법은 문제를 작은 부분으로 나누어 해결하고, 그 결과를 재활용하여 전체 문제를 해결합니다.

• 아이디어
  • 배열의 각 원소가 마지막인 LIS의 길이를 구한다고 가정합니다. 이를 위해 dp[i]라는 배열을 만들어 i번째 원소에서 끝나는 LIS의 최대 길이를 저장합니다.
• 점화식
  • dp[i] = max(dp[i], dp[j] + 1) (단, j < i이고 nums[j] < nums[i])
  • 이는 nums[j]가 현재 원소 nums[i]보다 작고 증가 조건을 만족하는 경우, LIS 길이를 갱신하는 식입니다.
• 구현 코드

def lis(nums):
    n = len(nums)
    dp = [1] * n  # 모든 원소의 LIS 길이를 1로 초기화
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:  # 증가 조건 확인
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)  # LIS의 최대 길이 반환

# 테스트
nums = [10, 22, 9, 33, 21, 50, 41, 60]
print(lis(nums))  # 결과: 5

위 코드는 2중 루프를 사용해 nums[i] 앞에 있는 모든 숫자를 확인하며 LIS 길이를 갱신합니다.

이진 탐색 활용 방식 (O(N log N))

동적 프로그래밍 방식은 직관적이지만, 데이터 크기가 커지면 성능이 떨어질 수 있습니다. 이를 개선하기 위해 이진 탐색(Binary Search)을 활용한 방법이 있습니다.

• 아이디어
  • LIS를 구성하는 배열(dp)을 유지합니다.
  • 현재 숫자가 dp의 마지막 값보다 크면 dp에 추가하고, 그렇지 않으면 이진 탐색으로 적절한 위치를 찾아 값을 교체합니다.
• 구현 코드

import bisect

def lis(nums):
    dp = []
    for num in nums:
        pos = bisect.bisect_left(dp, num)
        if pos == len(dp):
            dp.append(num)  # 새 숫자를 추가
        else:
            dp[pos] = num  # 기존 값을 교체
    return len(dp)  # LIS의 길이 반환

# 테스트
nums = [10, 22, 9, 33, 21, 50, 41, 60]
print(lis(nums))  # 결과: 5

• 이진 탐색 과정 시각화
  • 입력 배열: [10, 22, 9, 33, 21, 50, 41, 60]
  • dp의 변화 과정: [10] -> [10, 22] -> [9, 22] -> [9, 22, 33] -> [9, 22, 33, 50] -> [9, 22, 33, 50, 60]

이 방법은 O(N log N)의 시간 복잡도를 가지며, 대규모 데이터에서도 효율적으로 동작합니다.

LIS 알고리즘의 응용

LIS 실제 구성

LIS의 길이뿐만 아니라 실제 수열을 구하려면 각 원소가 어디에서 왔는지 추적할 수 있도록 역추적(Backtracking)을 사용해야 합니다.
이는 추가적인 배열에 이전 위치를 기록하여, 최종 결과를 재구성하는 방식입니다.

활용 사례

1. 데이터 분석: 시간 순서에 따른 데이터 패턴 분석
2. 게임 개발: 캐릭터 성장 경로 최적화
3. 생물정보학: DNA 서열에서 특정 증가 패턴 분석

게임 개발에서 LIS 알고리즘 사용 예제: 캐릭터 성장 시스템 최적화

게임 개발에서는 플레이어가 성장하는 과정에서 다양한 아이템, 레벨, 또는 퀘스트가 순차적으로 진행되도록 설계합니다. 이 과정에서 "가장 긴 성장 경로"를 찾아 플레이어 경험을 최적화하는 데 LIS 알고리즘을 사용할 수 있습니다.

예제: RPG 게임의 장비 레벨링

플레이어가 다양한 아이템을 얻는 상황을 가정해 봅시다.
각 아이템은 고유한 레벨 요구 조건이 있으며, 플레이어가 얻을 수 있는 가장 긴 레벨 증가 경로를 찾아야 합니다.

• 입력 데이터: 아이템의 레벨 요구 조건
  • 예: [15, 20, 10, 25, 30, 22, 35]
• 문제 정의:
  • 가장 긴 증가하는 장비 획득 경로를 찾아 플레이어가 최대한 많은 아이템을 얻도록 최적화합니다.

구현 코드

import bisect

# 아이템 레벨 요구 조건
item_levels = [15, 20, 10, 25, 30, 22, 35]

def find_longest_path(levels):
    dp = []  # LIS를 구성할 배열
    for level in levels:
        pos = bisect.bisect_left(dp, level)
        if pos == len(dp):
            dp.append(level)  # 새로운 증가 수열 추가
        else:
            dp[pos] = level  # 기존 수열 교체
    return len(dp), dp

# 결과 실행
length, optimal_path = find_longest_path(item_levels)
print("최대 획득 가능 아이템 수:", length)
print("LIS를 구성하는 최적 경로:", optimal_path)

출력 결과

최대 획득 가능 아이템 수: 4
LIS를 구성하는 최적 경로: [10, 22, 30, 35]

게임 내 활용

1. 아이템 성장 루트 설계
   • 위 결과에서 [10, 22, 30, 35]는 플레이어가 순서대로 획득할 수 있는 최적의 아이템 성장 경로입니다.
   • 이를 통해 게임 디자이너는 플레이어가 자연스럽게 도달할 수 있는 성장 경로를 제안할 수 있습니다.
2. 퀘스트 레벨링 최적화
   • 퀘스트 간 요구 레벨이 증가하도록 설계하면서도 플레이어가 무리 없이 진행할 수 있는 루트를 제공할 수 있습니다.

응용 확장

LIS 알고리즘은 단순히 길이를 구하는 것뿐만 아니라 실제 경로를 추적할 수 있어 퀘스트 디자인, 스킬 트리 경로 추천, 장비 업그레이드 루트 최적화와 같은 다양한 게임 시스템에 응용할 수 있습니다.

이는 게임 플레이어의 사용자 경험에 대한 최적의 루트를 설계하는 데 강력한 도구가 될 수 있습니다.

시간 복잡도 비교

방법시간 복잡도특징

동적 프로그래밍	O(N²)	구현이 간단하며 작은 데이터에 적합
이진 탐색 활용	O(N log N)	대규모 데이터에서도 빠르게 동작

마무리: LIS 알고리즘 요약과 한 걸음 더 나아가기

LIS(Longest Increasing Subsequence) 알고리즘은 주어진 배열에서 순서를 유지하며 가장 긴 증가하는 부분 수열을 찾아내는 효율적인 방법입니다. LIS의 구현 방식 중, 동적 프로그래밍(O(N²)) 방식은 구현이 쉽고 이해하기 직관적이며, 이진 탐색(O(N log N)) 방식은 성능이 중요한 대규모 데이터에 적합합니다.

입문 단계에서는 동적 프로그래밍 방식을 연습하고, 성능이 중요한 경우에는 이진 탐색 활용 방식을 도전해 보시는 것을 추천드립니다.

이 알고리즘은 단순히 알고리즘 문제를 해결하는 것에 그치지 않고, 데이터 분석, 게임 개발, 최적화 문제와 같은 다양한 실무 영역에도 활용될 수 있습니다. 입문 단계에서는 간단한 코드 구현부터 시작하고, 점차 문제의 변형과 응용 사례에 도전해 보세요.