개발자 퉁이리

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 이번에는 LIS의 길이만 출력하는 것이 아닌 LIS 수열도 출력해야 하는 문제였다. ⊙ 문제 풀이 #include #include #include using namespace std; int n,temp,index,l..

https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 가장 긴 증가하는 부분 수열: O(n log n) ⊙ 문제 접근 과정 https://tooo1.tistory.com/131 코드와 문제 접근 과정 동일 ⊙ 문제 풀이 #include #include #include using namespace std; int a; vector arr; int ma..

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 가장 긴 증가하는 부분 수열: O(n log n) ⊙ 문제 접근 과정 LIS 문제이다. 시간 복잡도 O(N log N)으로 풀었다. LIS가 무엇인지, O(N^2)의 풀이법을 보고 싶다면 tooo1.tistory.com/121 크기 값을 입력 받는다. 벡터 값을 입력받는데 조건문을 활용하여 입력받는다. O(N log N)으로 풀 수 있게 한..

www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 LIS 문제... 블로그에서 2번째로 다룬다. 생각보다 꽤 중요한 알고리즘으로 느껴졌고 이번 기회에 집중해서 파봤다. 전에 DP 문제를 풀 때 tooo1.tistory.com/121 풀었었는데 이번에도 DP 문제에서 또다시 나왔다. D..

www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 배치하는 문제를 만났을 때, 가장 중요한 포인트는 기준이다. 기준을 잡고 풀이를 하면 훨씬 편하다. 그렇다면 이 문제에서는 기준을 어떻게 잡는 것이 좋을까? 정답은 오름차순으로 정렬하라고 하였으니 오름차순으로 가장 길게 정렬된 부분을 기준으로 하자 만약 LIS(최장 부분 증가수열)을 알고 있다면 문제를 더 편하게 풀 수..