L.O.K

12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net ◎ 문제 풀이 [PS] BOJ12015 가장 긴 증가하는 부분수열2 ( LIS ) with JAVA 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net ◎ 문제풀이 DP는 lordofkangs.tistory.com (위 문제와 풀이는 똑같다. ..

https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net ◎ 문제풀이 선이 겹치지 않도록 회로를 구성할 때, 회로가 가질 수 있는 최대 선의 개수를 구하는 문제이다. 1 부터 4까지 선을 하나씩 추가하며 최적의 회로를 만들어 가면 된다. ( Greedy ) 회로에 Start Point 순서대로 선을 하나씩 추가하려고 한다. '현재' 회로의 End Point 중 가장 큰 EndPoint가 추가하려는 선의 End Point보다 작으면 선..

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net ◎ 문제풀이 DP는 수열에서 나올 수 있는 부분수열의 모든 경우에서 조건에 맞는 경우를 구하는 문제이다. 이때, 부분수열의 조건이 '가장 길고'(Longest) '증가하는'(Incresing) 부분수열(Subsequence)를 구하는 문제라면, LIS( Longest Increasing Subsequence) 알고리즘 풀이라 생각하면 된다. 처음에 이중for문을 만들어서 접근하였는데, 시간초과가 발생했다. 수열의 크기가 최대 1,000,000이므로 이중for으로 ..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ◎ 문제풀이 DP는 수열에서 나올 수 있는 부분수열의 모든 경우에서 조건에 맞는 경우를 구하는 문제이다. 이때, 부분수열의 조건이 '가장 길고'(Longest) '증가하는'(Incresing) 부분수열(Subsequence)를 구하는 문제라면, LIS( Longest Increasing Subsequence) 알고리즘 ..