💡문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.
예제입력
6
10 20 10 30 20 50예제출력
4
10 20 30 50📖내가 실패한 Code
import sys
'''
LIS 알고리즘 문제
파이썬엔 bisect라는 훌륭한 이진 탐색 라이브러리가 있지만 직접 구현
'''
class Node:
def __init__(self, data):
self.curr = data
self.parent = None
def binary_search(arr, target):
left = 0
right = len(arr) - 1
mid = 0
while left <= right:
mid = (left + right)//2
if arr[mid].curr == target.curr:
break
elif arr[mid].curr > target.curr:
right = mid - 1
else:
left = mid + 1
target.parent = arr[mid]
arr[mid] = target
return arr
def lis_algorithm(number, arr):
if number == 1:
return arr[0]
lis_arr = [Node(arr[0])]
for num in arr[1:]:
new_node = Node(num)
if lis_arr[-1].curr < new_node.curr:
lis_arr.append(new_node)
else:
lis_arr = binary_search(lis_arr, new_node)
for num in range(len(lis_arr)):
while lis_arr[num].parent:
lis_arr[num] = lis_arr[num].parent
lis_arr[num] = lis_arr[num].curr
return lis_arr
def main():
number = int(sys.stdin.readline())
sequence = list(map(int, sys.stdin.readline().split()))
lis_sequence = lis_algorithm(number, sequence)
print(len(lis_sequence))
print(" ".join(map(str, lis_sequence)))
if __name__ == '__main__':
main()📖내가 작성한 Code
import sys
'''
LIS 알고리즘 문제
파이썬엔 bisect라는 훌륭한 이진 탐색 라이브러리가 있지만 직접 구현
'''
class Node:
def __init__(self, data):
self.curr = data
self.parent = None
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid].curr >= target.curr:
right = mid - 1
else:
left = mid + 1
return left
def insert_lis(arr, target):
location = binary_search(arr, target)
if location > 0:
target.parent = arr[location - 1]
arr[location] = target
return arr
def lis_algorithm(arr):
lis_arr = []
for val in arr:
new_node = Node(val)
if not lis_arr or lis_arr[-1].curr < val:
if lis_arr:
new_node.parent = lis_arr[-1]
lis_arr.append(new_node)
else:
lis_arr = insert_lis(lis_arr, new_node)
lis_sequence = []
node = lis_arr[-1]
while node is not None:
lis_sequence.append(node.curr)
node = node.parent
lis_sequence.reverse()
return lis_sequence
def main():
speed_input = sys.stdin.readline
number = int(speed_input())
sequence = list(map(int, speed_input().split()))
lis_seq = lis_algorithm(sequence)
print(len(lis_seq))
print(" ".join(map(str, lis_seq)))
if __name__ == '__main__':
main()
✍️풀이과정
이런 문제를 풀 때, 문제 분석이 중요하다.
먼저,
- 길이만 출력 vs 수열도 출력
- N 크기 확인
- N 5자리 이하일 경우 O(N^2) DP도 가능할 수 있음.
- N이 6자리 이상이면 O(N*log N) 알고리즘 필수.
여기서는, 실제 LIS 수열을 출력해야하기 때문에,
자료 구조 정의 or 별도의 배열 만들기
하지만,
설계부터 잘못했었음. 이진 탐색 구현도 이상하였고, 부모찾기 로직 자체도 잘못 만들었다.
- 모든 배열의 부모만 찾으면 되는 줄 알앗는데 애초에 잘못된 생각
- 그래서 들어온거에 부모 연결 안하고 이진 탐색 한 이후 바로 위의 부모값만 연결
따라서,
- 최종 LIS의 마지막 노드를 시작점으로, 역추적 하기
- 부모들을 계속 갱신 시키기
로, 다시 로직을 잡고 풀었더니 통과. 이진 탐색 구현이 생각보다 힘들었다는게 충격.
🧠 코드 리뷰
-
에지 케이스 처리:
예를 들어, N=1이 들어오면 어떻게 되나? → 잘 동작하기는 하지만, 혹시라도 “parent 인덱스 -1 접근” 문제가 생길 수 있는지(현재는 if location > 0으로 거르므로 문제 없음). -
클래스 대신 리스트 사용: Python에서 클래스 인스턴스는 리스트 인덱스나 별도의 배열을 사용하는 것보다 메모리와 속도 면에서 비효율적일 수 있습니다. 대신, parent 정보를 별도의 리스트로 관리하여 성능을 향상시킵니다.
-
불필요한 함수 제거: insert_lis 함수를 간소화하여 불필요한 리스트 반환을 피하고, 더 명확하게 역할을 분리하면 좋습니다.
-
bisect 모듈 활용: Python의 bisect 모듈은 이분 탐색을 쉽게 구현할 수 있게 도와줍니다. 특히, bisect_left와 bisect_right 함수를 활용하면 lower_bound와 upper_bound를 쉽게 구현할 수 있습니다.
🛠️AI 개선 코드
import sys
import bisect
def find_lis_with_bisect(sequence):
lis = []
parent = [-1] * len(sequence)
idx_list = []
for i, num in enumerate(sequence):
pos = bisect.bisect_left([x[0] for x in lis], num)
if pos == len(lis):
if lis:
parent[i] = lis[-1][1]
lis.append((num, i))
idx_list.append(i)
else:
lis[pos] = (num, i)
idx_list[pos] = i
parent[i] = lis[pos-1][1] if pos > 0 else -1
# 복원 과정
lis_sequence = []
k = idx_list[-1]
while k != -1:
lis_sequence.append(sequence[k])
k = parent[k]
lis_sequence.reverse()
return len(lis_sequence), lis_sequence
def main():
input = sys.stdin.readline
N = int(input())
sequence = list(map(int, input().split()))
length, lis_seq = find_lis_with_bisect(sequence)
print(length)
print(' '.join(map(str, lis_seq)))
if __name__ == "__main__":
main()
💻결과
🖱️참고 링크
