판교의 메타몽

두 함수 모두 C++에서 이진 탐색을 활용하여 원소의 위치를 찾아낼때 활용한다. 공통적으로 아래 두 가지 특징을 지니고 있다. 1. 배열, 혹은 벡터가 오름차순으로 정렬되어있어야 함 2. algorithm 라이브러리를 사용함 lower_bound 목적 : 찾으려는 key 값이 배열, 혹은 벡터의 몇 번째에 존재하는지 반환 Tip 1 : key값이 존재하지 않을 경우, 찾으려는 key값보다 바로 다음으로 큰 값의 위치를 반환 (ex : 아래 예시에서 -1의 lower_bound 결과를 찾을 경우, 0을 반환) Tip 2 : key값과 key값보다 큰 값 모두 존재하지 않을 경우, 배열의 size를 반환함 (ex : 아래 예시에서 6을 찾을 경우 5를 반환) 사용법 // 사용법 lower_bound(배열, ..

문제 링크 : www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제를 한 줄 요약하자면, 배열에 입력된 각 값들의 크기 순서를 출력해주면 된다. 작은 값일수록 작은 순서를 지니게 되며, 이때 순서는 0부터 시작된다. 한 가지 중요한 점은, 중복된 값의 원소들은 중복된 순서를 가지게 된다는 것이다. 문제 풀이는 다음과 같다. 1. 배열에 값을 입력받고, 이를 복사한 배열을 하나 더 만든다. 이때 배열, 벡터 어..