방앗간 개발자

문제 출처:https://www.acmicpc.net/problem/2568

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, <그림 1>과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 최소 개수의 전깃줄을 구하는 프로그램을 작성하시오.

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500,000 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. 

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다. 둘째 줄부터 한 줄에 하나씩 없애야 하는 전깃줄의 A전봇대에 연결되는 위치의 번호를 오름차순으로 출력한다. 만약 답이 두 가지 이상이라면 그 중 하나를 출력한다.

바로 전 게시글에서 이어지는 문제입니다.

이번에도 없애야 하는 전깃줄의 최소 개수를 출력하는데 플러스로 없애야 하는 전봇대의 위치까지 알아내야 합니다.

일단 전 게시글에서 알려준 방법으로 없애야 하는 전봇대의 최소 길이부터 구해봅시다.

LIS의 길이를 구하는 방법을 모른다면 (1365번: 꼬인 전깃줄) 를 보고 오시면 됩니다.

예시는 위 그림에 있는 수열[ 4, 2, 6, 7, 9, 1, 3, 10 ]을 그대로 쓰겠습니다. 

위 수열에 LIS알고리즘을 사용한다면 [ 3, 6, 7, 9, 10 ] 의 결과가 나옵니다 이 수열의 길이가 LIS의 길이가 됩니다. 

단 이 수열이 LIS을 구성하는 수열은 아닙니다 딱 보더라도 제일 앞에 있는 3은 원본 수열에서 뒤쪽에 있는 수입니다. 

따라서 LIS의 요소까지 구하려면 추가적인 연산을 해주어야 하는데 이제부터 그 방법을 설명 하겠습니다.

일단 기존에 하던대로 LIS알고리즘을 수행합니다 단 수행하면서 입력되는 수가 LIS배열의 몇 번째 칸에 들어가는지 기록 

할 배열이 하나 더 필요합니다. 그림으로 표현하면 아래와 같습니다.

이 구해진 Record배열의 제일 뒤부터 순차적인 내림차순 즉 Record 배열의 제일 마지막이 5 이므로 5, 4, 3, 2, 1순으로 

원본 배열의 인덱스에 맞춰 데이터를 추가해주면 LIS 의 요소를 구할 수 있습니다. 

최종적인 수열 [ 2, 6, 7, 9, 10 ] 이 LIS 요소까지 구성하는 수열이 됩니다.

문제의 정답은 LIS를 만들기 위해 없애야 하는 전봇대를 구하는 것 입니다. 

따라서 원본 수열에서 최종적으로 구해진 LIS의 요소들을 전부 빼고 남은 숫자들이 없애야 하는 전봇대가 됩니다.

전체 코드입니다.

문제 출처:https://www.acmicpc.net/problem/1365

공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.

문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.

임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.

유스타운 시의 시장 임한수를 도와 잘라내야 할 전선의 최소 개수를 구하는 프로그램을 작성하시오.

첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타낸다.

전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는 지를 첫째 줄에 출력한다.

이런 문제를 처음 풀어본다면 대체 어떻게 접근해야 하는지 감이 안잡힐 수도 있지만  

몇가지 예시를 들어 문제를 풀어보면 한 가지 패턴을 찾을 수 있습니다. 

입력: 7    3    1    2    0    6    8    9    4    10 

이런 전선 입력이 주어졌다면 여기서 꼬이지 않고 전선을 잘라내는 방법은 

7    3    1    2    0    6    8    9    4    10

빨간색으로 칠한 전선을 잘라내는 것 입니다. 전선을 잘라내고 남아있는 전선(1, 2, 6, 8, 9, 10)을 보면 한 가지 패턴이 있는데 

바로 '증가하는 수열' 이라는 겁니다.

따라서 이 문제는 어떤 임의의 수열이 주어졌을 때, 이 수열에서 몇 개의 수를 제거하여 만들 수 있는 부분수열 중 오름차순으

로 정렬된 가장 긴 수열을 찾는 최장 증가 부분 수열(LIS : Longest Increasing Subsequence)알고리즘을 이용하여 푸는 문제

입니다.

이 LIS알고리즘은 O(n^2)과 O(n log n)의 시간이 걸리는 알고리즘이 각각 있지만 이 문제에선 최대 입력이 100,000이므로 

O(n^2)의 알고리즘을 사용하면 시간초과에 걸립니다. 따라서 저는 O(n log n)의 알고리즘을 소개하고 문제를 풀겠습니다.

O(n log n)의 알고리즘에선 이진탐색을 약간 변형한 알고리즘인 Lower bound를 사용하게 됩니다. 

입력값은 위에 예시로 든 수열을 그대로 사용하겠습니다.

입력: 7    3    1    2    0    6    8    9    4    10

1. 벡터를 하나 만들어 줍니다.

2. 수열을 처음부터 검사하는데 현재 검사하는 수를 A라고 했을때 벡터의 마지막 요소를 비교하여 

    - A 가 벡터의 마지막 요소보다 크면 벡터의 마지막에 추가해준다.

   - A 가 벡터의 마지막 요소보다 작으면 Lower bound하여 나온 index위치의 값과 교환해준다.

3. 최종적으로 만들어진 벡터의 길이 N이 최장 증가 수열의 길이가 된다.

그림으로 하나하나 표현하면 아래와 같습니다.

이렇게 최종적으로 만들어진 수열(0, 2, 4, 8, 9, 10)의 길이가 LIS의 길이가 됩니다.

문제의 정답인 잘라야 하는 전선의 수는 주어진 (n - LIS의 길이)를 하면 나오게 됩니다.

단 이 문제에서는 LIS의 요소를 요구하지는 않았는데 위에서 구해진 수열이 LIS를 나타내는건 아닙니다.

직접 눈으로 확인해봐도 수열 7    3    1    2    0    6    8    9    4    10 의 최장 증가 수열은 

1    2    6    8    9    10 이지만 LIS알고리즘을 통하여 구해진 수열은 0    2    4    8    9    10 입니다.

따라서 LIS의 요소까지 구하려면 추가적인 작업을 해야하지만 그 방법은 다음 문제에서 알아 보도록 하겠습니다.

전체 코드입니다.