목록2024/04 (18)
Binaryseop
2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 접근 n이 최대 100,000이므로 이중 for 문으로 0에 가장 가까운 용액을 만들어내는 두 용액을 찾으면 최악의 경우 시간 복잡도가 O(n^2)이 될 것으로 예상됩니다. 따라서 투 포인터를 이용한다면 시간 복잡도를 O(n)으로 줄일 수 있습니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Ma..
2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 접근 n이 최대 100,000이므로 이중 for 문으로 0에 가장 가까운 용액을 만들어내는 두 용액을 찾으면 최악의 경우 시간 복잡도가 O(n^2)이 될 것으로 예상됩니다. 따라서 투 포인터를 이용한다면 시간 복잡도를 O(n)으로 줄일 수 있습니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import j..
7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 접근 n이 최대 20,000, m이 최대 20,000이므로 선형 탐색을 사용한다면 최악의 경우 시간 복잡도가 O(n * m)가 될 것으로 예상됩니다. 따라서 이진 탐색을 사용하여 a가 b보다 큰 쌍의 개수를 구한다면 시간 복잡도를 O(m * logn)으로 줄일 수 있습니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import ja..
2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 접근 n이 최대 1,000,000, m이 최대 1,000,000이므로 선형 탐색을 사용한다면 최악의 경우 시간 복잡도가 O( n * m )가 될 것으로 예상됩니다. 따라서 이진 탐색을 활용하여 시간 복잡도를 O(m * logn)으로 줄일 수 있는 방법을 선택했습니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Str..