간타타 공부장 간타타 공부장

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 알고리즘 분류 1. 투포인터 2. 이분탐색 아이디어 1. N이 1,000,000이므로 두 용액을 고르는 가장 쉬운 방법인 O(n^2)시간 복잡도로는 시간 초과 위험이 있음 2. 용액을 상수대로 정렬하고 가장 작은 수와 가장 큰 수에 포인터를 둔 다음 두 용액을 혼합했을 때의 결과를 보고 0에 가까운 수면 정답셋에 저장 3. 혼합 용액의 수가 음수이면 0에 가깝게 만들어주기 위해서 low 포인..

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 알고리즘 분류 1. 이분탐색 아이디어 1. N이 10의 5승이기 때문에 O(n^2)시간복잡도로 풀면 시간이 오래 걸릴 것임 2. 이분탐색으로 O(logn) 시간복잡도로 푸는 것으로 접근 3. 탐색 범위를 목표한 수로 잡고 탐색한 수의 이하의 정수들이 행렬에 몇개가 있는지 생각해서 탐색 4. 17 ~ 18번째 라인이 생각하기 어려운데 행마다 for문을 돌면서 행렬의 값..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 알고리즘 분류 1. 투포인터 아이디어 1. 2중 for문으로 구해 볼 수 있는 방법도 있을 것 같으나 시간초과가 날 것 같아 시도하지 않음 2. 투포인터 문제로 판단하고 용액의 수를 정렬 한 다음 왼쪽 끝과 오른쪽 끝을 투포인터로 두고 탐색을 시작 3. 포인터 상으로 용액 혼합 시 0에 가까우면 답 후보군 업데이트를 함 4. 현재 포인터 상으로 용액 혼합 시 음수..

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 알고리즘 분류 1. 이분탐색 아이디어 1. 최장길이 증가수열을 이분탐색으로 만듬 2. 최장길이 증가수열을 만드는 방법 - 리스트는 점점 증가하는 수로 앞부터 작은 수로부터 정렬하여 채움 - 가장 큰 수보다 더 큰수가 있으면 리스트 뒤에 추가 - 추가하는 수가 리스트의 가장 큰수보다 작으면 리스트에서 적절한 위치에 수를 위치해서 넣어줌 (맨 끝수가 더 작은수로 업데이트를 하는 것이 포인트라고 생각 ..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 아이디어 1. list가 크기 때문에 전형적인 이분탐색 문제 2. 포인트는 "가장 인접한 두 공유기 사이의 거리" 이고 이를 코드에서는 mid 변수로 판단한다. (mid기준으로 공유기 설치가 C보다 많으면 이도 정답 후보군이 될 수 있음.) 3. 최댓값을 구하는 것을 지켜야 함 4. 공유기를 sorting 한 다음 탐색을 진행, 가장 첫번째 집에..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 아이디어 1. python find 사용시 시간초과 2. 이분탐색으로 시간복잡도 줄여야 통과 if __name__ == '__main__': N = int(input()) cards = list(map(int, input().split(" "))) M = int(input()) find = list(map(int, input().split(" "))) res = []..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 아이디어 1. M의 숫자가 크기 때문에 O(n)으로 찾으면 시간 오류 2. 이분탐색으로 구현 N, M = list(map(int, str(input()).split(" "))) tree_list = list(map(int, str(input()).split(" "))) low = 0 hight = max(tree_list) answer = 0 def get_..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 아이디어 1. N, M 숫자가 매우 큼 => 단순히 for문을 돌면 시간 초과 2. 시간 복잡도를 줄여야 하고 O(n)에서 O(logn)으로 줄이기 위해 이분 탐색 알고리즘 사용 N = int(input()) cards = list(map(int, input().split(" "))) M = int(input()) targets = list(map(int, in..