이진탐색
백준 1654: 랜선자르기 해설- python
✏️ 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ✏️ 풀이 이진탐색을 이용하는 문제다. 이진탐색에 대한 내용은 여기에서 랜선의 길이에 대해서 이진탐색을 시행한다. k,n= map(int, input().split()) line = [] for _ in range(k): line.append(int(input())) start = 1 end = max(line) while(start=n: start=mid+..
![[알고리즘] Lower Bound와 Upper Bound](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcdaiNd%2FbtrscOrNAc5%2FrFozFBsAqSggsTtiehn3uk%2Fimg.png)
[알고리즘] Lower Bound와 Upper Bound
✏️ 무엇인가?Lower Bound와 Upper Bound는 모두 경계값을 찾는 과정이다. 이진탐색(Binary Search)가 '원하는 값을 찾는 과정' 이었다면 Lower Bound는 '원하는 값이 처음 나오는 위치'를 찾는 과정이고, Upper Bound는 '원하는 값보다 큰 값이 처음 나오는 위치'이다.Array = [1, 1, 2, 2, 3, 4, 4, 4, 6]이런 리스트가 있에서 Lower Bound로 4를 찾는다면 4가 처음 나오는 인덱스인 5가 Output이 될 것이고, Upper Bound로 찾는다면 4가 마지막으로 나오는 인덱스인 7이 Output이 될 것이다. ✏️ 구현과정의 고민사실 선형 탐색으로 구현하면 바로 해결되지만 기왕이면 O(N)보다는 O(lgN)이 좋지 않겠나. 이진탐색..
백준 10816: 숫자카드 2 해설- python
✏️ 문제 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ✏️ 풀이 아래는 10815에서 만들어쓴 이진탐색 함수이다. def BS(array, target, start, end): if start > end: return 0 mid=(start+end)//2 if array[mid]==target: return 1 elif array[mid]>target: return BS(array, target, start, mid-1) else: return BS(array, targe..
백준 10815: 숫자카드 해설- python
✏️ 문제 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ✏️ 풀이 1920 수찾기 문제와 완전하게 동일한 문제였다. 해당 문제의 해설과 이진탐색에 대한 설명은 여기를 참고 (Python) N=int(input()) card=list(map(int,input().split())) card=sorted(card) M=int(input()) target_list=list(map(int,input().split())) def BS(array, target, start, end): if..
Binary Search (이진탐색) 알고리즘
✏️ 이진탐색알고리즘의 작동방식 이진탐색은 정렬된 리스트에서 특정 요소를 찾는 알고리즘이다. 분할(Devide) 리스트를 중간값을 기준으로 두개의 리스트로 분할한다. 정복(Conquer) - 검색할 숫자 중간값 이면 중간값 뒤의 리스트에서 검색할 요소를 찾는다. - 검색할 숫자 == 중간값 이면 값을 리턴한다. ✏️ 이진탐색알고리즘 구현 (Python) 재귀적 구현 def BS(array, target, start, end): if start>end: return None mid=(start+end)//2 if array[mid]==target: return mid elif array[mid]>target: return B..
백준 12015: 가장 긴 증가하는 부분 수열 2- python
✏️ 문제 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net ✏️ 풀이 11053 가장 긴 증가하는 부분 수열 1과 뭐가 다를까? 다른 것은 단 하나. N의 조건 범위이다. 11053에서는 1