Algorithms/Binary Search

[초기 접근 방법(x)] 1. 직행 다리가 감당이 가능하면, 가능한 중량을 올린다. 2. 직행 다리가 감당이 불가능하면, 경유 다리를 탐색하자 1) 경유 다리가 감당이 불가능한 경우, 가능한 중량을 내린다. 2) 경유 다리가 감당이 가능한 경우, 가능한 중량을 올린다. [생각] 위와 같이 접근을 하게 되면 감당 가능한 무게가 작은, 쓸데없는 다리가 있을 경우에 목적지까지 갈 수 있음에도 판단하지 못한다. - search 함수를 다음과 같이 작성하면 틀린다. 왜?? def search(start, end): while start < end: mid = (start + end) // 2 # 다리들이 현재 mid 무게를 감당 가능하면, 더 중량을 올려도 됨 if bfs(mid): start = mid + 1 ..

https://www.acmicpc.net/problem/1300[초기 접근 방법(X)]1. N^2의 [i][j] 값을 모두 lst에 넣으려면 시간복잡도가 이미 O(N^2)으로 시간초과이다.2. 그러면? 시간복잡도를 줄일 수 있는 방법은, 처음부터 [i][j] 값을 lst에 넣지 않는 것3. 그런 [i][j] 값을 전부 넣지않고, 어떤 값을 lst에 넣어야 하는가? 에서 시작했다. 대각선을 기준으로 중앙값이 가장 크므로,이분탐색을 하여 몇번째 대각선인지 찾고 남은 인덱스만큼 이동탐색하면 K번째 수를 찾으려고 했다.   [생각]위 방식대로 로직을 짜고 풀었지만 결과는 "틀렸습니다"저 로직을 생각하는데도 시간을 많이 썼던 문제라서, 미련없이 정답 코드를 참고했다...일단 K번째 수는 '1행의 원소들'이 존재..

https://www.acmicpc.net/problem/11663 [초기 접근 방법] 1. 점들을 먼저 오름차순 정렬한다. 2. 각 선분의 시작점(upper)과 끝점(lower)의 index를 찾는다 시작점 : lower_bound 끝점 : upper_bound 3. 해당 index 범위 내의 dot 개수를 구한다. [생각] lower, upper bound 문제는 빠르게 이해함. 그러나 하나의 함수로 통일하고, 후처리 하는 과정에서 시간을 소모했다. (결국 따로 메소드 만듦..) [코드] # 풀이 시간 : 1시간 # 시간복잡도 : O(2MlogN) # 공간복잡도 : O(N or M) # 참고 : - import sys input = sys.stdin.readline # lower_bound def l..

[초기 접근 방법] 1. 구간의 '최댓값' - '최솟값'이 작아야 한다. 2. 초기 구간은 '1개'이다. 3. 리스트의 길이를 중심으로 '최댓값 - 최솟값'(x)이 최소가 되게끔 2개의 구간을 만든다. 4. 위 구간들을 중 x가 가장 큰 범위를 다시 구간화한다. *문제점 : 맨 처음 중앙을 분기로 나눴을 때 정확하지 않음 [생각] 잘못된 접근법으로 디버그를 하면서 시간을 많이 썼던 문제.. 문제에서 구하고자 하는 '구간의 점수의 최댓값의 최솟값을'을 mid로 설정하고 접근하면 쉬운 문제이다. mid로 설정했을 때, 각 구간의 '최대 - 최소'가 mid보다 큰 구간인지 count 한 후, 이분탐색하면 된다. [코드] # 풀이 시간 : 1시간 20분 + 1시간 # 시간복잡도 : O(Nlog(max(lst))..

[초기 접근 방법] - 각 캐릭터의 power에 따라, 각 칭호 limit 기준이 부합되는지 판단하여 출력 (오름차순이므로) [생각] - 위 로직으로 풀었을 때, 캐릭터들의 개수는 10^5, 칭호의 개수도 10^5 최대 시간 복잡도는 10^10.. - limit 기준에 따라, 적절한 칭호 index 이분탐색 진행한다. [코드] # 풀이 시간 : 15분 # 시간복잡도 : O(MlogN) # 공간복잡도 : O(N or M) # 참고 : - # 이분탐색 문제인가..? # 적절한 칭호를 빨리 찾는 이분탐색 문제였네.. ㅎㅎ # lower_bound인 이유 : 기준 power가 포함된 범위 내의 칭호를 붙여주는 것이다. 초과가 아닌 import sys input = sys.stdin.readline def sea..

[초기 접근 방법] - mid*mid < n이면, start = mid + 1 아니면, end = mid [생각] - 기본적인 이분탐색 문제였지만, 코드 내의 등호 유무와 lower_bound, upper_bound의 개념을 정확히 짚고 넘어가고 싶어 블로그를 참고했다. [코드] # 풀이 시간 : 10분 # 시간복잡도 : O(logn) # 공간복잡도 : - # 참고 : 개념 정리 # 등호 판단 : 1) https://blossoming-man.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search-%EA%B2%BD%EA%B3%84-%EC%84%A4%EC%A0%95%EC%9D%84-%EC%96%B4%EB%96%BB%EA%B2%8C-%ED..