반응형 Longest Incremental Subsequence3 [C/C++] 백준 #2631 줄세우기(가장 긴 증가하는 부분수열) 이번 문제는 동적계획법을 이용해서 풀어도 되겠지만, 기본적으로 가장 긴 증가하는 부분수열(LIS; Longest Incremental Subsequence)의 풀이법을 이용하셔서 푸시는 것이 좋습니다. 일반적인 동적계획법으로 풀 경우에는 알고리즘 시간복잡도가 \(O(N^2)\)이지만, 가장 긴 증가하는 부분수열 풀이법을 이용하시면 \(O(N \log N)\) 시간복잡도로 풀 수 있습니다. https://www.acmicpc.net/problem/2631 이 문제를 가장 긴 증가하는 부분수열 문제라는 것을 인지하는 것이 관건입니다.문제에서 예로 든 3 7 5 2 6 1 4 를 생각해보죠. 문제에서는 위치를 옮기는 4개의 숫자에 대해서 이야기를 했는데요. 쉽게 접근할 수 있는 방법은 이미 순서가 올바.. 2024. 5. 10. [C/C++] 백준 #2565 전깃줄(가장 긴 증가하는 부분수열) 이번 문제는 백준내에서도 아주 자주 나오는 가장 긴 증가하는 부분수열(LIS; Longest Incremental Sub-sequence) 문제입니다. 전깃줄이 꼬이지 않게 배열하기 위해서 몇개의 전깃줄을 없애야 하는 문제입니다. https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 그동안 제가 작성했던 가장 긴 증가하는 부분 수열 문제들을 모아두면 다음과 같습니다. https://sdev.tistory.com/1384 https://sdev.tistory.. 2023. 7. 19. [C/C++] 백준 #2352 반도체 설계(가장 긴 증가하는 부분수열) 가장 긴 증가하는 부분수열 문제는 백준 사이트에서 자주 접할 수 있는 문제입니다. 이 알고리즘을 잘 이해하면, 풀 수 있는 문제들이 많이 있습니다. 증가하는 부분수열 중 하나를 출력하라면 조금 골치가 아프겠지만, 현재 이 알고리즘을 이용해서 부분수열도 출력할 수 있습니다. https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 반도체에서 서로 라인이 겹치지 않도록 설계하는 것은 중요한 문제입니다. 실제로는 다층기판을 이용하기 때문에.. 2023. 4. 27. 이전 1 다음 728x90
