binary search
[백준] 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..
[백준] 28257. 알록달록 초콜릿 만들기 - C++
[Gold III] https://www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 백준 제 2회 초콜릿컵 C번 문제 대회 당일 런타임 에러로 애를 먹었던 문제다. 이분탐색할 때 vector를 사용했었는데, 큰 숫자 범위 때문에 메모리 제한을 벗어난 듯 했음. 풀이 조금의 규칙성(?)과, 이분 탐색을 이용해야 하는 문제. 우선, 첫 번째 규칙은, 각 줄에 존재하는 민트초코의 개수. 1개 0개 1개 / 2개 1개 2개 / 3개 2..
[백준] 2467. 용액 - 파이썬
[Gold V] https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 1과 풀이 2 모두 AC(통과)가 가능한 코드입니다. 풀이 1 일단, 모든 경우의 수를 다 따져본다면(Brute-Force), NC2 이기 때문에, (N * (N-1)) / 2 => O(N^2) 정도의 Time Complexity로 풀 수 있게 됨. 당연히 이 방법은 아닐 테고, 일단 문제를 보자마자 직감적으로 생각난 것은 Two Pointer였다. 그런데 일반적인 tw..