알고리즘||코딩테스트/BinarySearch

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 사용한 알고리즘 : 이분 탐색 풀이전략 두 용액에서와 달리 이번 문제는 세 용액의 합이 0에 가까워야 한다. 저번 두 용액에서는 입력받은 용액들을 오름차순으로 정렬시키고, 최좌측 인덱스 start와 최우측 인덱스 end에 속하는 양 끝값의 합을 구하고 이 합이 0보다 크면 총합의 값을 줄이기위해 end=end-1, 합이 0보다 작으면 총합의 값을 늘리기 위해 start=..

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 풀이 사용한 알고리즘: Binary Search 풀이전략 이분탐색을 통해 특정 값과 오차가 M 이상이면서 가장 적은 오차의 수를 구하면 된다. 완전 탐색을 통해 값을 비교하게 되면 시간 복잡도가 O(n^2)으로 n이 최대 100,000 까지 가능하다 했기 때문에 최대 10,000,000,000번(10억 번)의 연산을 하게된다. 그런데 JAVA는 통상 1초당 1억번의 연산을 수행..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 풀이 사용한 알고리즘 : 이진탐색, 해쉬 맵 자료구조 풀이전략 이진탐색을 사용하지 않고, 해쉬 맵 또는 배열 카운팅 방식으로 풀이할 수도 있는 문제이다. (실제 이진 탐색은 시간 복잡도가 O(nlogn)인데 반해, 위 방법들의 시간 복잡도는 O(n)으로 더 빠르다.) 하지만 이진 탐색 기법을 사용하여 문제를 풀이해보겠다. C++과 python과 달리 JAVA에는..