반응형 LIS2 [백준 3745] 오름세 문제 출처 : https://www.acmicpc.net/problem/3745 주식의 오름세를 찾는 문제 입니다. 점점 커지는 형태의 부분 수열을 찾는 문제로 LIS를 찾는 문제와 같습니다. LIS 라는 것만 알고 있다면 알고리즘을 이용하여 쉽게 문제를 해결 할 수 있습니다.코드 작성다른 함정이 없어 보이기 때문에 바로 문제를 해결해 보겠습니다. LIS를 해결할 때 속도도 빠르고 모듈을 사용하여 오류도 없을만한 이분탐색 bisect를 사용하겠습니다.입력 받기while True: try: N = int(input()) arr = map(int, input().split() except: break이 문제는 테스트 케이스의 개수가 존재하지 않습니다. 따라서 .. 2024. 11. 9. [백준 12015] 가장 긴 증가하는 부분 수열 2 문제 출처 : https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net LIS(Longest Inceasing Sequence)란? LIS는 Longest Increasing Subsequence의 약자로 최장 증가 수열 또는 최장 증가 부분수열이라고 합니다. LIS를 이해하기 위해서는 먼저 Increasing Subsequence 한글로 증가 부분수열을 알아야 합니다. 증가 부분수열을 말 그대로 증가하고 있는 부분 수열을 나타냅니다. 가령 [5, 1,.. 2023. 9. 20. 이전 1 다음 반응형
