CodeDrive

문제:

N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은 번호의 스위치와 전구는 전선으로 서로 연결되어 있다.

하나의 스위치를 누르면 그 스위치와 연결된 전구에 불이 들어오게 된다. 두 개 이상의 스위치를 같이 누르는 경우, 전선이 서로 만나면 만난 전선에 연결된 전구들의 불은 켜지지 않는다.

위 그림에서 1번과 4번의 스위치를 같이 누르면 1번과 4번의 전구에는 불이 켜지지만, 1번과 2번의 스위치를 같이 누르면 1번과 2번 전구의 불은 켜지지 않는다. 1번과 3번 그리고 5번 스위치를 같이 누르면 전선이 만나는 1번과 5번 전구는 켜지지 않지만 3번 전구는 켜지게 된다.

여러분이 할 일은 가장 많은 전구가 켜지도록 스위치를 누르는 것이다. 위 그림에서는 3번과 4번 그리고 5번 스위치를 누르는 경우와 1번과 3번 그리고 4번을 누르는 경우에 세 개의 전구가 켜지게 되고, 이 두 가지 경우가 가장 많은 전구가 켜지는 경우이다.

스위치의 번호순서와 전구의 번호순서가 주어질 때, 어떤 스위치를 누르면 가장 많은 전구가 켜지는지를 알아내는 프로그램을 작성하시오.

입력:

첫 번째 줄에는 스위치의 수(전구의 수)를 나타내는 정수 N (1 ≤ N ≤ 10,000)이 주어진다. 두 번째 줄에는 N개의 스위치 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다. 세 번째 줄에는 N개의 전구 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다.

출력:

첫 번째 줄에는 가장 많은 전구가 켜지게 하는 스위치의 수를 출력한다. 두 번째 줄에는 눌러야 하는 스위치의 번호를 오름차순(번호가 커지는 순서)으로 빈칸을 사이에 두고 하나의 줄에 출력한다. 단, 두 번째 줄에 출력할 수 있는 답이 두 가지 이상일 때에는 그 중 한 가지만 출력한다.

풀이방법:

 겹치지 않도록 최대한 많이 선택해야 하는 문제다. 이는 곧 가장 긴 증가하는 부분 수열(LIS) 문제와 같다. 따라서 LIS 알고리즘을 사용하여 가장 긴 증가하는 부분 수열을 찾으면서 그 부분 수열의 번호들도 같이 찾는 문제에 해당한다.

 LIS 문제를 해결하는 방법에는 여러가지가 있지만, 이 문제에서는 bisect를 이용했다. 이 방법의 핵심은 최대한 작은 수들을 고르는 것이 가장 긴 증가하는 부분 수열을 만들기 유리하다는 것이다. 1 2 7 이라는 부분 수열과 1 2 4 이라는 부분 수열이 있을 때 후자의 경우가 더 긴 부분 수열을 만들 확률이 높다는 것이다. 따라서 입력으로 들어오는 배열에서 bisect을 이용하여 계속해서 배열을 최신화한다.

하지만 이 때 만드는 배열은 실제 가장 긴 증가하는 부분 수열은 아니다. 이는 길이만을 알 수 있기 때문에, 만드는 동시에 위치 정보도 같이 추가하여 마지막에 실제 가장 긴 부분수열을 찾을 수 있도록 한다. 이 때 사용하는 것이 idx 배열이며 , start의 각 원소가 몇 번째 자리에 들어가는지에 대한 여부다. idx=[0,0,1,1,2]라는 것은 2가 0번째, 4가 0번째, 1이 1번째, 5가 1번째, 3이 2번째 자리에 각각 들어가게 된다는 것이다. 따라서 역순으로 idx 배열을 탐색하면서 2, 1, 0이 먼저 나오는 순서로 넣는 것이 최종 답에 해당한다. (나중에 들어간 것이 마지막에 남아 있는 수들이기 때문)

문제링크:

https://www.acmicpc.net/problem/2550

문제:

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.

예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.

3 7 5 2 6 1 4

아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.

3 7 4 5 2 6 1

이제, 7번 아이를 맨 뒤로 옮긴다.

3 4 5 2 6 1 7

다음 1번 아이를 맨 앞으로 옮긴다.

1 3 4 5 2 6 7

마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.

1 2 3 4 5 6 7

위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다. 따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.

N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

출력:

첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

풀이방법:

 N명의 아이들을 번호 순서대로 배치하기 위해 최소의 움직임을 구한다는 것은 LIS 문제와 같다. 가장 긴 부분 수열을 찾고, 그 수열에 속하지 않은 아이들만 움직이는 것이 최소 움직임일 것이기 때문이다.

 따라서 DP를 사용한 LIS 문제를 풀고, N에서 그 값을 빼주도록 한다.

문제링크:

https://www.acmicpc.net/problem/2631

문제:

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

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

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

입력:

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

출력:

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

풀이방법:

 A, B를 쌍으로 저장한 뒤에 A를 기준으로 정렬한다. 그리고 B 값들에 대해 가장 긴 증가하는 부분 수열을 찾으면 가장 적게 제거하고 전깃줄이 서로 교차하지 않게 만들 수 있다.

 가장 긴 증가하는 부분 수열을 찾는 방법은 많지만 이분 탐색을 사용한 방법(N*log(N))을 통해서 찾고, 전체 길이에서 답을 구했다.

참조 링크 : https://seungkwan.tistory.com/8

문제링크:

https://www.acmicpc.net/problem/2565

문제:

반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오.

입력:

첫째 줄에 정수 n(1<=n<=40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, ... , n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

출력:

첫째 줄에 최대 연결 개수를 출력한다.

풀이방법:

복잡해 보이지만 LIS 문제라고 생각하면 쉽게 풀 수 있다. LIS를 푸는 방법에는 여러 가지가 있지만 가장 대표적인 방법인 DP를 사용해서 문제를 풀어보았다.

DP로 푸는 방법은 O(N^2)의 시간 복잡도이기 때문에 시간이 오래 걸리게 된다. 따라서 O(NlogN)으로 푸는 방법이 있다해서 다음을 참고 하였다.

https://dyngina.tistory.com/16

여기서 O(NlogN)이 두 개 있었는데 lower_bound는 python의 bisect를 쓰면 될 것 같다. 이번에는 인덱스 트리를 사용해서 문제를 풀어 보았다. 인덱스 트리를 만들기 위한 과정에서 시간이 많이 소요 되는 것 같아서 이 역시도 pypy3로 통과했다. 아마도 bisect를 사용하면 python으로도 통과할 수 있을 것 같다.

문제링크:

https://www.acmicpc.net/problem/2352

문제:

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수 있다. 예를 들어 앞에서부터 순서대로 크기가(1,5,2,3,7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법을 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.

상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.

입력:

파일의 첫 번째 줄은 상자의 개수 n(1<=n<=1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.

출력:

첫쨰 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.

풀이방법:

앞에 있는 작은 상자를 뒤에 있는 큰 상자에 넣을 수 있으므로 이는 다이나믹프로그래밍을 사용한 LIS 문제와 같다.

LIS에서 lis[i]는 i번째 수열까지 한 번에 넣을 수 있는 최대의 상자 개수이며, i+1을 추가했을 때, boxes[1]~boxes[i]까지 boxes[i+1]보다 작은 값이 있는지 파악하고, 그 수에 해당하는 lis[k] 값들 중에 최댓값에 1을 더해주는 방식으로 진행한다. 그러고 전체 lis에서 최댓값을 출력해주면 된다.

문제링크:

https://www.acmicpc.net/problem/1965

문제:

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A={10, 20, 10, 30, 20, 50}이고, 길이는 4이다.

입력:

첫째 줄에 수열 A의 크기(1<=N<=1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1<=Ai<=1,000)

출력:

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이 방법:

배열을 하나씩 커지게 만들어 가면서 증가하는 부분 수열을 찾도록 한다. 가장 큰 값을 빠르게 찾기 위해서 뒤에서 부터 값을 탐색하도록 하게 한다.

https://www.acmicpc.net/problem/11053