본문 바로가기

백준 이분탐색6

[백준] 12015번 가장 긴 증가하는 부분 수열 2 사용 언어 - Python3 120154번: 덱 (골드5, 큐) 문제 ★이분 탐색 문제★ 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 정답 이분탐색으로 시간복잡도 O(nlogn) 개선 (코드 풀이) ans=[0] 리스트에 값 비교하면서 append 해주기 ans[-1] ans의 가장 마지막 값이 i보다 작으면 ans에 append해준다. 그렇지 않다면, 이분탐색으로 인덱스 mid값을 조정해준다. ans[mid]가 i보다 작으면 start = mid+1, i보다 크면 end = mid로 범위를 업데이트해준다... 2023. 1. 23.
[백준] 1300번 K번째 수 사용 언어 - Python3 1300번: K번째 수 (골드2, 이분 탐색) 문제 ★이분 탐색 문제★ 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 정답 i*j 배열의 규칙을 알아내는 이분탐색 문제!! 1~k 범위를 줄여가며 검색한다. (코드 풀이) 1. 변수 선언 n 배열의 크기 k b의 인덱스 2. 이분 탐색 정의 몇 번째인지 인덱스를 구해야하므로 k의 범위를 이분 탐색한다. 배열은 항상 1*1로 시작하기 때문에, start =1로 한다. end = k까지만 진행해서 더이상의.. 2023. 1. 21.
[백준] 2110번 공유기 설치 사용 언어 - PyPy3 2110번: 공유기 설치 (골드4, 이분 탐색) 문제 ★이분 탐색 문제★ 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net python3으로는 시간 초과로 오답이지만, pypy3으로는 정답! 이분탐색은 while문으로 돌아가서 python보다 빠른 pypy3으로 했을 때만 정답이 나올 수 있다. 정답 집 좌표값의 차이를 start/end/mid 값을 지정하는 이분탐색 문제 !! (코드 풀이) 1. 변수 선언 n 집의 개수 c 공유기의 .. 2023. 1. 21.
[백준] 2805번 나무 자르기 사용 언어 - Python3 2805번: 나무 자르기 (실버2, 이분 탐색) 문제 ★이분 탐색 문제★ 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 정답 시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !! (코드 풀이) 1. 변수 선언 나무의 수 n개 나무의 길이 m개 tree는 정렬된 상태로 입력받기 2. 이분 탐색 정의 높이가 1 이상, max(tree) 이하 여야 자를 수 있기 때문에, 시작점은 1 , 끝점은 max(tree)로 선언한.. 2023. 1. 21.
[백준] 10816번 숫자 카드 2 사용 언어 - Python3 10816번: 숫자 카드 2 (실버4, 이분 탐색) 문제 ★이분 탐색 문제★ 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 정답 시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !! (코드 풀이) 1. 리스트 원소별 개수 구하기 mycard를 sorted 정렬하여 입력받는다. 정렬한 내카드를 한개씩 확인하면서 개수를 센다. count = {} 딕셔너리를 만들어서 여러개일 경우 중복 개수를 세준다. list_1 = [1, .. 2023. 1. 21.
[백준] 1920번 수 찾기 사용 언어 - Python3 1920번: 수 찾기 (실버4, 이분 탐색) 문제 ★이분 탐색 문제★ 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 정답 시작/끝/중간값을 선언하여 중간값과 같을때까지 범위를 줄이는 이분탐색 문제 !! (코드 풀이) 0. 이분 탐색 전 정렬하기 이분 탐색을 하기 위해선 탐색 기준이 정렬되어 있어야한다. a를 정렬한 후 arr과 비교해야 a의 탐색 범위를 줄이는 의미가 있기 때문이다. 1. 시작/끝/중간 값 선언 n 범위 안에서 ar.. 2023. 1. 21.

티스토리툴바