LIS

https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 풀이 사용한 알고리즘 : 이진 탐색, LIS(Longest Increasing Subsequence) 풀이 전략 1. 첫 번째 입력한 수를 비어있는 result 리스트에 추가한다. 2. i 번째 입력한 수가 result의 맨 끝값보다 크면 result 리스트에 추가한다. 3. i 번째 입력한 수가 result의 맨 끝값보다 작으면 result 내부를 이진탐색하여, 해당 수보다 크거나..

https://www.acmicpc.net/problem/2550 2550번: 전구 첫 번째 줄에는 가장 많은 전구가 켜지게 하는 스위치의 수를 출력한다. 두 번째 줄에는 눌러야 하는 스위치의 번호를 오름차순(번호가 커지는 순서)으로 빈칸을 사이에 두고 하나의 줄에 출력 www.acmicpc.net 풀이 사용한 알고리즘 : LIS 풀이 전략 import sys input=sys.stdin.readline N=int(input()) switch=list(map(int,input().split())) bulb=list(map(int,input().split())) arr=[] for i in switch: arr.append(bulb.index(i)) length=[0]*N preNode=[] for i i..

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 사용한 알고리즘 : LIS (Longest Increasing Subsequence) 원소가 N개인 배열에서 일부 원소를 골라내서 만든 부분수열 중 오름차순을 만족하며, 그 길이가 최대인 수열을 LIS라고 한다. 풀이과정 1. 입력값을 저장할 arr, 특정 인덱스에서 내림차순의 LIS 값을 저장할 length 리스트를 정의한다. 2. 0~N-1 인덱스를 돌며 특정 인덱스에서 해당 ..