알고리즘 문제 풀이 중 이진탐색 lower bound, upper bound를 사용해야되는 경우가 발생했다. 이론은 알고 있지만 이를 코드로 구현하는 것에 어려움을 겪어 아직 이해가 부족하다고 생각해서 글로 정리하게 되었다. lower bound 정렬된 데이터에서 처음으로 해당 값 이상이 되는 인덱스를 찾는 것이다. def find_lower_bound(number): start = 0 end = n while start < end: mid = (start + end) // 2 if cards[mid] >= number: end = mid else: start = mid + 1 return start 여기서 기존 이진 탐색과 end의 의미가 다른 것을 알아야된다....
입력 길이에 따라 알고리즘이 처리하는 시간을 정량화한 것이다. 일반적으로 빅오 표기법을 사용한다. 빅오 표기법이란, 식의 최고 차항을 제외한 모든 항과 최고차항의 계수를 제외시킨다. 일반적으로 문제를 풀 때 시간 제한이 1초라면 시간복잡도는 다음과 같다. N범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 풀 수 있다. N범위가 2000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 풀 수 있다. N범위가 100000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 풀 수 있다. N범위가 10000000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 풀 수 있다....
문제 상황 처음에 segment tree를 이용해, 배열에 공통적인 변화량을 기록했다. 하지만, 이후에 주어진 범위 내에서 최대 값을 구해야되는 문제가 나왔다. 범위 내의 최대값을 구하기 위해서는 결국 segment tree의 모든 leef node를 탐색해야되므로 O(n)이 걸린다. 해결 방법 배열을 n개의 그룹으로 나누어서 공통적인 변화량을 기록한다. 배열의 크기는 n^(0.5)가 된다. 이렇게 하면 값을 수정할 때도 O(n^(0.5)) 가 걸리고, 최대값을 구할 때도 O(n^(0.5))의 시간 복잡도로 탐색을 하게된다. 참고 자료 https://kesakiyo.tistory.com/22