Dev_Diary

https://www.acmicpc.net/problem/2565최대 증가 부분 수열 (LIS) 문제입니다.연결된 전선의 목적 인덱스가 점차 증가하는 방향이어야 전선끼리 교차하지 않기 때문에 시작 인덱스를 기준으로 정렬한 뒤 목적 인덱스로 LIS 를 풀어주면 됩니다.import sysinput = sys.stdin.readlinedef solution(N, lines): # 라인 정리 lines = [l[1] for l in sorted(lines, key=lambda x:x[0])] # 증가하는 최대 부분 수열 길이 max_inc = [1 for _ in range(N)] # 순회 for l in range(1, N): # 자신보다 이전 전선이고 자신보다 작..

https://www.acmicpc.net/problem/11054LIS 알고리즘을 두 번 사용해 풀 수 있는 문제입니다.가장 긴 증가하는 부분 수열 이라는 이름의 알고리즘인데, 이는 DP 로 쉽게 구현할 수 있습니다. 이 알고리즘을 양 끝에서 구현해 만날 때 가장 크게 이어지는 부분을 찾아주면 풀 수 있습니다.import sysinput = sys.stdin.readlinedef solution(N, nums): # DP / 0 행은 증가 / 1 행은 감소 부분수열 memo = [[0 for _ in range(N)] for _ in range(2)] # 첫 번째 수는 무조건 바이토닉 수열 memo[0][0] = 1 memo[1][-1] = 1 # 순회 for i ..