문제 바로가기
문제:
민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 정해진 순서대로 보여줄 것이다. 준민이는 앞의 카드부터 임의의 개수만큼 골라서 민균이에게 제시하게 되는데, 제시한 카드의 수열이 순증가가 아니면 민균이에게 바보라고 놀림받게 된다. 예를 들어 민균이가 보여준 카드가 {4, 9, 10, 9} 일 때 준민이가 {4, 9}를 골랐다면 놀림을 받지 않겠지만, {4, 10, 9}이나 {9, 9}를 제시하면 놀림받게 될 것이다. 생각보다 바보가 아닌 준민이는 한번도 민균이에게 놀림을 받지 않았다. 이에 분노한 민균이는 하나의 조건을 더 추가했다. 이제 준민이가 제시해야하는 수열은 순증가여야 할 뿐만 아니라, 원소의 개수가 제일 많은 수열이여야 한다. 예를 들어 민균이가 보여준 카드가 {8, 9, 1, 2 ,10}일 때 준민이가 {8, 9, 10} 또는 {1, 2, 10}을 골랐다면 놀림을 받지 않겠지만, {8, 9}나 {1, 2}를 제시하면 놀림받게 될 것이다. 당황한 준민이는 일단 제시할 수 있는 수열의 원소의 최대 개수를 구해보기로 하였다. 예를 들어 {8, 9, 1, 2, 10}에서의 원소의 최대 개수는 3이 될 것이다. 도저히 못 풀겠어서 고민하던 준민이는 똑똑하기로 소문난 당신을 찾아가 이 문제를 의뢰하였다! 불쌍하고 딱한 준민이를 위해 이 문제를 해결하는 프로그램을 작성해보자.
입력:
첫 번째 줄에는 민균이가 제시한 카드의 개수 N (1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 민균이가 제시한 카드 N개에 들어있는 정수가 공백(빈 칸)으로 구분되어 주어진다. 각 정수는 1 이상 100,000,000 이하의 자연수이다.
출력:
준민이가 제시할 수 있는 수열의 원소의 최대 개수를 출력한다.
풀이1:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
T = int(sys.stdin.readline()) # T: 입력으로 주어지는 수열의 길이
lst = list(map(int,sys.stdin.readline().split(" "))) # lst: 입력으로 주어지는 수열
dp = [1 for i in range(T+1)] # dp 리스트 초기화. 각 원소는 해당 인덱스까지의 증가하는 부분 수열의 최대 길이를 나타냄
# 최장 증가 수열(LIS) 구하기
for i in range(T):
for j in range(i):
if lst[i] > lst[j]: # lst[i]가 lst[j]보다 크다면, lst[i]를 포함하는 LIS를 만들 수 있음
dp[i] = max(dp[i], dp[j] + 1) # dp[i]의 값을 갱신하여 i까지의 LIS의 최대 길이를 구함
print(max(dp)) # 모든 원소를 순회하며 가장 큰 dp 값이 최장 증가 수열의 길이가 됨LIS 알고리즘 기본 형태이다 . 근데 이 코드는 빅오가 O(N^2) 이다 N = 1000 이여서 가능하다. 좀더 크면 이분탐색으로 해야한다.
풀이2.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] >= target: # 중간값이 타겟보다 크거나 같으면 오른쪽 범위를 줄임
right = mid - 1
else: # 중간값이 타겟보다 작으면 왼쪽 범위를 줄임
left = mid + 1
return left
lis = [] # 최장 증가 수열 리스트
for num in lst: # 입력으로 주어진 수열을 순회하며
idx = binary_search(lis, num) # 현재 숫자를 삽입할 인덱스를 이진 탐색으로 찾음
if idx == len(lis): # 인덱스가 lis의 길이와 같다면 해당 숫자를 lis에 추가
lis.append(num)
else: # 인덱스가 lis의 길이보다 작다면 해당 인덱스에 숫자를 바꿔줌
lis[idx] = num
print(len(lis)) 예를들어
8 9 1 2 10처음에 8 이들어간다.
그다음은 9 인데 9 는 8보다 큰 숫자이므로 8,9 가된다.
그다음이 문제인다
그 다음은 1이다. 1은 8,9 에서 이분탐색으로 찾으면 0 이나온다.
그럼 lst[0] 을 1로 바꿔주면 lst = [1,9] 가 된다.
lst = [1,9] 그리고 2가 들어오면 2도 9랑 바꿔줘야한다. 그럼 lst[1] = 2가 된다.
마지막으로 10 이들어오면
lst = [1,9] 안에 어느 숫자 보다 크다.
즉 len(lst) == 2 와 return 받은 idx == 2 이므로 뒤에 추가해주면 된다.
간단하게 말하면 lst 안에 있는 숫자보다 큰 경우에는 append를 해주면 되고,
그렇지 않을경우 lst에서 위치를 찾아 숫자를 교체해주면 된다.
댓글