https://www.acmicpc.net/problem/20551
20551번: Sort 마스터 배지훈의 후계자
지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제
www.acmicpc.net
소스코드
풀이
★ 이분탐색을 연습하는 중이었는데, 실버4의 난이도를 가지고 있어서 이분탐색을 활용하는 전형적인 문제라고 생각했습니다 ! 하지만 3~4번의 시간초과를 겪고 구글링 해봤는데, lower bound를 구현하여 해결하는 문제였습니다 ! 문제를 풀면서 경계값을 찾는 lower bound와 upper bound에 대해서 공부할 수 있는 기회였습니다.
★ 일반적인 이분탐색으로 문제를 풀면 시간초과를 받게 되는데, 이분탐색은 mid값을 가지고 있는 정렬된 배열 a의 값이 target 값과 같으면 그 값을 바로 리턴해버립니다. 하지만 lower bound를 구현하여 이분탐색한다면, 가장 먼저 target이 등장하는 mid 값을 찾아줄 수 있습니다 !
★ 배열의 mid값이 target값보다 작거나 클 때는 일반적인 이분탐색과 같이, lt = mid+1, rt = mid-1 로 범위를 줄여나갑니다. 하지만 mid값이 target값과 같을 때(a[mid] == target), 조금 다른데, rt의 값을 mid로 설정하여 while문이 성립할 때 동안 계속해서 mid값을 찾아줍니다 ! 이때, rt 값이 mid와 같아지는 경우는 break를 통해 반복문을 빠져 나와야합니다.
★ 문제에서 정수 D가 존재하지 않는 경우 -1을 출력해야 하기 때문에 if문으로 return 값을 달리 해줍니다 !
★ lower bound, upper bound 참고자료
https://ojt90902.tistory.com/531
파이썬, Lower Bound 및 Upper Bound 구현
구현 전, 알아두어야 할 것 Lower Bound 및 Upper Bound는 모두 경계값을 찾는 함수다. 이 함수는 반드시 정렬이 된 값들에서만 사용할 수 있다. Lower Bound 파이썬 코드 구현 : O(logn) Lower Bound는 찾고자 하
ojt90902.tistory.com
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 1205번: 등수 구하기 (Python) (1) | 2023.11.01 |
|---|---|
| [백준 알고리즘] 1590번: 캠프가는 영식 (Python) (0) | 2023.10.31 |
| [백준 알고리즘] 1655번: 가운데를 말해요 (Python) (1) | 2023.10.27 |
| [백준 알고리즘] 2231번: 분해합 (Python) (0) | 2023.10.26 |
| [백준 알고리즘] 14940번: 쉬운 최단거리 (Python, BFS) (0) | 2023.10.23 |