Lis
[백준] 1365. 꼬인 전깃줄 - Python
[Gold II] https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 풀이 Binary Search를 이용해 O(NlogN)으로 풀이하는 LIS 문제. 아래 문제들과 거의 동일하다. 따로 설명을 적지 않겠음. [백준] 2565. 전깃줄 - Python [백준] 12015. 가장 긴 증가하는 부분 수열 2 - Python AC. import bisect from collections import deque import sys input..
[백준] 2568. 전깃줄 - 2 - Python
[Platinum V] https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 풀이 이분탐색을 이용한 LIS - O(NlogN) 문제. 아래 두 문제를 참고하면 쉽게 풀이할 수 있다. [백준] 2565. 전깃줄 - Python [백준] 14003. 가장 긴 증가하는 부분 수열 5 - Python AC. import bisect from collections import deque n = int(input()) lines = [] for _ in r..
[백준] 14003. 가장 긴 증가하는 부분 수열 5 - Python
[Platinum V] 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 풀이 이분 탐색(Binary Search)를 이용해, log(n logN)의 시간 복잡도로 풀어내는 LIS 문제에서, LIS 배열까지 구해야 한다. 입력된 배열을 순회하며, res 배열의 몇 번째 index에 들어가는 지를 모든 원소에 대해 기록하고, (res_idx) res_idx 배열을 거꾸로 순회하면서, index가 가장 처음 나오는 부분..
[백준] 12015. 가장 긴 증가하는 부분 수열 2 - Python
[Gold II] https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 이분 탐색(Binary Search)를 이용해, log(n logN)의 시간 복잡도로 풀어내는 LIS 문제. res 배열을 생성, 입력된 배열을 모두 순회하며, res 배열의 마지막 숫자보다 크다면 res 맨 뒤에 append. 작다면, 이분 탐색을 이용해 들어갈 자리를 찾고, 그 index에 대신 삽입. 최종적으로 LIS의 길이를 구할 수 있게 된다. 다만 이렇게 만들어진..
[백준] 2352. 반도체 설계 - Python
[Gold II] https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 풀이 [백준] 2565. 전깃줄 - Python 문제와 동일하다시피 한 문제이다. 다만, 전깃줄 문제는 O(N^2)의 LIS (DP)로 풀이할 수 있는 반면, 이 문제는 n
[백준] 2565. 전깃줄 - Python
[Gold V] https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 전깃줄이 교차하는 경우를 생각해 보자. A 전봇대에서 B 전봇대로의 모든 전깃줄을 시작부터 숫자가 작은 순서대로 하나하나 연결한다고 생각할 때, 도착하는 위치가 이미 존재하는 도착지들보다 더 작은 숫자라면, 전깃줄이 교차하게 된다. 따라서 그러한 전깃줄들을 제거하면 되는 문제이다. 이 과정에서, A 전봇대에서의 출발 위치를 기준으로 정렬하게 되면, 아래와 같다. [[1, 8], [2..