upper_bound1

• 

  [c++] 백준 - 합이 0인 네 정수 ( 이분탐색) 1. 문제 2. 입출력 및 예제 3. 문제 해설 처음에 이 문제를 접했을 때 비슷한 문제가 생각났다. 백준-피자판매 문제와 백준-두배열의 합 문제였다. 따라서 처음엔 두 문제와 같이 map을 사용해서 풀면 쉽게 풀릴 줄 알았다. 위의 두 문제의 경우 가능한 모든 합의 경우의 수를 미리 구해두어 map에 그 합과 그 합이 나오는 경우의 수를 모두 저장해둔다. 그 후 다른 배열을 돌면서 합이 K가 되는 경우를 구해야한다면 cnt += map[K - 다른배열[i]]와 같은 로직으로 경우의 수를 모두 구해 더해주면 되었다. unordered_map의 경우 정렬을 하지 않는 map이고 hash table을 기반으로 하는 자료구조이기 때문에 O(1)의 시간복잡도로 원하는 자료에 접근이 가능했다. 하지만 위의 접근 .. c++/알고리즘 2023. 2. 6.