반응형 LIS4 [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. [C/C++] 백준 #1965 상자넣기(가장 긴 증가하는 부분수열) 이번 문제는 가장 긴 증가하는 부분수열을 찾는 문제입니다. 문제의 알고리즘 힌트에는 동적 프로그래밍을 이용하라고 되어 있지만, 동적 계획법을 이용하는 경우에는 \(O(N^2)\) 알고리즘으로 풀어야 합니다. 그에 비해 약간의 정책을 이용해서 풀면 \(O(N \log N)\) 알고리즘으로 풀 수 있습니다. 가장 긴 증가하는 부분수열이라는 것은, 부분수열중에 단순 증가하는 수열을 찾는 것입니다. 예를 들어서, 1 6 2 5 7 3 5 6 이란 수열이 있습니다. 부분수열은 순서를 지키면서, 이 수열에서 몇개의 수를 뽑아내는 것을 말합니다. 예를 들어서 1 6 2 5 도 이 수열의 부분수열이고, 1 2 7 6도 이 수열의 부분수열이 됩니다. 그런데, 증가하는 부분수열은 앞의 숫자보다 뒤의 숫자가 큰 경우를 의미.. 2022. 12. 10. [C/C++] 백준 #1365 꼬인 전깃줄(가장 긴 증가하는 부분수열) 백준 알고리즘 사이트에서 많이 나오는 문제 중 하나가 가장 긴 증가하는 부분수열(LIS; Longest Incremental Subsequence)입니다. https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 수열에 있는 수들 중 일부(연속되지 않아도 상관이 없습니다.)를 선택해서 그 순서가 증가하는 수열이면 증가하는 부분 수열입니다. 여기서 문제는 그 증가하는 부분 수열의 길이가 가장 긴 경우가 얼마인지입니다. 가장 일반적인 해법은 .. 2020. 2. 4. 이전 1 다음 728x90
