binary search

CS/PS
[BOJ] 2473번 : 세 용액
• 문제 설명 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net KOI 2010 고등부 1번 문제이다. 푸는 방법은 두 가지가 있는데, two pointers로 푸는 방법과 binary search로 푸는 방법이 있다. two pointers로 풀면 time complexity는 O(N^2)으로 풀 수 있고, binary search로 풀면 O(N^2*logN)으로 풀 수 있다. 다만 two pointers로 풀기 위해서는 ..
→2021.07.31
CS/PS
[BOJ] 1637번 : 날카로운 눈
https://www.acmicpc.net/problem/1637 1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 한참을 들여다봐도 풀 방법이 떠오르지 않아 푼 사람들로부터 힌트를 얻어 풀었다. binary search의 참신한 적용 문제이다. 그냥 brute-force를 쓰면 time complexity가 대략 20000* 2^32가 나오게 된다. 고로 다른 방법을 찾아야 한다. 이 문제에서는 범위를 잘라서 그 안에 있는 수들의 개수를 모두 세었을 때, ..
→2021.07.13

• 이전
• 1
• 다음