Lower bound

프로그래밍/자료구조 & 알고리즘
[알고리즘] 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)이 좋지 않겠나..
→2022.02.02
프로그래밍/백준
백준 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..
→2022.02.01

• 이전
• 1
• 다음