[TIL] 20230224 성장일지

Algorithm

• Leetcode Study Plan

-  Day 15. Heap, Binary Search

 

• Sort() 의 Compare 함수

-  Compare 함수의 결과가 true면 그대로, false면 재정렬 한다고 생각한다. 또한, 2개의 매개변수를 받을 때 먼저 받는 인자를 기존의 원소, 뒤에 받는 인자가 새로 들어온 원소라고 생각한다.

ex)
bool compare(int a, int b){
return a > b;
}
이 경우 기존에 이미 들어있던 a가 새로 들어온 b보다 크면 정렬할 필요가 없음. 이라는 의미가 되므로 내림차순이다.
(더 큰게 왼쪽에 있을때 정렬할 필요가 없다는 의미이므로)

-  Priority_queue 의 Compare 함수는 기존의 Sort() 함수의 결과에서 반대로 한다고 생각하면 된다.
ex)
bool compare(int a, int b){
return a > b;
}
기존 sort() 함수 대로라면 내림차순으로 정렬이 되겠지만, prority_queue는 반대로 정렬되므로 오름차순이다.
즉, top에는 가장 작은 원소가 들어가 있을 것이다.

정확한 해석인지는 모르겠지만 이렇게 생각하고 코드를 작성하자.

참고
https://velog.io/@whipbaek/sort-%EC%99%80-%EC%82%AC%EC%9A%A9%EC%9E%90-%EC%A7%80%EC%A0%95-compare-%ED%95%A8%EC%88%98

https://codingdog.tistory.com/entry/c-priority-queue-%EC%98%88%EC%A0%9C-compare-%EA%B5%AC%EC%A1%B0%EC%B2%B4%EB%A7%8C-%EC%9E%98-%EC%A0%95%EC%9D%98%ED%95%A9%EC%8B%9C%EB%8B%A4

• lower_bound, upper_bound

-  lower_bound와 upper_bound를 사용하려면 주어진 배열이 반드시 오름차순으로 정렬되어 있어야 한다.

-  lower_bound는 찾으려는 key값보다 같거나 큰 숫자가 배열에서 처음 등장하는 위치를 리턴한다. 리턴값은 iteration이다.

ex) lower_bound(arr.begin(), arr.end(), 3) - arr.begin();
arr 배열의 처음부터 끝까지 중 3과 같거나 큰 숫자가 처음 등장하는 위치를 arr.begin() + x 로 반환해주므로 마지막에 arr.begin()을 빼주면 몇번째 인덱스인지 알 수 있다.

-  upper_bound는 찾으려는 key값을 초과하는 숫자가 배열에서 처음 등장하는 위치를 리턴한다. 사용법은 lower_bound와 같다.

-  두 경우 모두 탐색에 실패한다면 매개변수로 주어진 두번째 인자 last를 리턴한다.

ex) lower_bound(arr.begin(), arr.end(), 3) - arr.begin();
arr 배열에 3보다 크거나 같은 수가 없다면 arr.end()가 리턴되며 거기서 arr.begin()을 빼면 arr.size() 가 된다.

 

-  풀이 코드 : Modisc/Algorithm: Algorithm Study (github.com)