문제 https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 문제 풀이 본론부터 말하면 해당 문제는 LIS 알고리즘을 활용하는 문제이다. 왜 그렇게 생각했느냐에 대해서 얘기해볼까 한다. 우리의 목표는 A와 B를 연결하는 전깃줄이 교차하지 않게 하면서, 최소한의 전깃줄을 제거해야 한다. 그러면 전깃줄이 교차하는 경우는 무엇일까? A의 1번은 B의 8번과 연결되어 있고, A의 2번은 B의 2번과 연결되어 있다. A의 1번 전깃줄을 연결한 상태에서 A의..
문제 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 풀이 가장 긴 증가하는 부분 수열 문제는 알고리즘의 명칭이 있을 정도로 유명한 문제이다. DP를 이용해서 그 수열의 길이를 구한 문제는 풀어본 적이 있지만, 수열의 길이와 그 수열을 구해야 하는 문제는 따져줘야할것이 많기 때문에 DP로 풀면 안 될 거 같은 느낌이 왔다. 기존의 LIS 문제는 N의 크기가 크지 않아서 N^2 알고리즘으로 DP 배열을 계속 업..
문제 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제 풀이 문제는 정말 간단하다. 주어진 순서에서 최소한의 변경을 통해 오름차순으로 정렬하는 문제이다. 접근방법에 대해서 정말 많은 고민을 했었다. 최소한의 변경을 위해서는 기존 배열에서 최대한 고정시켜야 하는 부분을 길게 해야 한다고 이해했다. 그렇다면 고정시키는 번호를 어떻게 정할까? 문제 보기에서만 봐도 움직이는 번호들은 정해져 있는것을 보면 유추할 수 있다. 3 7 5 2 6 1 4 -> 1..