Algorithm - 최대 선 연결하기(LIS 응용)
알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [최대 선 연결하기(LIS 응용)] 왼쪽의 번호와 오른쪽의 번호가 있는 그림에서 같은 번호끼리 선으로 연결하려고 한다. 왼쪽 번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열되어 있다. 오른쪽의 번호 정보가 위에서부터 아래로 주어질 때, 선이 서로 겹치지 않고 최대 몇 개의 선을 연결할 수 있을지 구하는 프로그램을 작성하시오. 위의 그림은 오른쪽 번호 정보가 4, 1, 2, 3, 9, 7, 5, 6, 10, 8로 입력되어 있을 때, 선이 서로 겹치지 않고 연결할 수 있는 선의 최대 값(6개)을 구한 경우이다. *입력 설명 첫 번째 줄에는 자연수 N(..
2022. 2. 3.
Algorithm - 최대 부분 증가수열(LIS : Longest Increasing Subsequence)
알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [최대 부분 증가수열(LIS)] N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하시오. (단, 원수열의 원소 순서는 그대로 유지해야 함) 예를 들어, 주어진 수열의 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이고 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다. *입력 설명 첫 번째 줄에 입력되는 데이터의 수인 자연수 N(2 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N..
2022. 2. 3.
