BinarySearch

    [Java] 백준 3197 (백조의 호수) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 3197 (백조의 호수) Gold 1

    Problem : https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net Approach BinarySearch 를 이용한 BFS + 구현 문제였다. 먼저, 얼음이 며칠 뒤에 녹는지에 대한 전처리가 필요하다. (코드에서는 iceberg라고 표현했다.) 얼음에 대한 전처리는 다음 과정으로 처리하였다. findIcebergNearWater(): 물과 인접한 얼음들을 구하였다. icebergsNearWater 큐 : 이 변수는 ..

    [Java] 백준 1981 (배열에서 이동) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1981 (배열에서 이동) Gold 1

    Problem : https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net Approach 이분탐색 + BFS 문제이다. 꽤 어렵게 문제를 풀었다. 문제 풀이에 앞서, 입력을 받으면서 구해놔야 할 것이 있다. 배열의 값중 최솟값 minNum과 최댓값 maxNum을 이분탐색의 left와 right에 이용하기 때문이다. left는 0이다. (배열의 값이 모두 같은 경우 최대 - 최소 = 0이다.) right는 maxNum - minN..

    [Java] 백준 1561 (놀이 공원) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1561 (놀이 공원) Gold 2

    Problem : https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net Approach 이분탐색을 이용하여 풀이가 가능한 문제이다. 먼저 n이 m이하일 경우, 0초에 모든 사람들이 놀이기구에 탑승할 수 있으므로 n번째 놀이기구가 마지막 사람이 타는 놀이기구가 될 것이다. 위 경우가 아니라면, 문제를 푸는 주요 로직은 다음과 같다. 먼저 n -= m 을 수행한다. (0초에 m명이 놀이기구를 탈 수 있기 때문이다.)..

    [Java] 백준 13397 (구간 나누기 2) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 13397 (구간 나누기 2) Gold 4

    Problem : https://www.acmicpc.net/problem/13397 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net Approach 이분탐색을 이용한 문제이다. 문제에서 말한 점수의 최솟값은 구간의 크기가 1일 때, 0이다. 점수의 최댓값은 최대 요소값 - 최소 요소값이지만, 편의상 최대 요소값 - 1로 이분탐색의 left와 right를 정해도 상관없다. 이분탐색을 진행하면서 해당 값을 만족시키는 구간의 개수가 m개 초과인지 아닌지 판단한다. 초과라면, 해..

    [Java] 백준 1939 (중량제한) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1939 (중량제한) Gold 4

    Problem : https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net Approach 이분탐색과 DFS/BFS를 사용하는 문제이다. 먼저 입력을 받으면서 그래프를 구성한다. 와중에 중량제한의 최솟값과 최댓값 또한 같이 구한다. 이 두 값이 이분탐색에 쓰일 left와 right가 될 것이다. 이 중량제한 값을 이용하여 BFS를 수행한다. 시작 섬을 출발하여 도착 섬에 도달할 수 있다면, ans를 갱신하..

    [Java] 백준 2143 (두 배열의 합) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2143 (두 배열의 합) Gold 3

    Problem : https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net Approach 이분탐색 문제이다. 먼저 A 배열 과 B 배열의 요소들로 부 배열의 합들을 구하여 각각 aSum, bSum 에 저장한다. 그런 후, aSum에 있는 각 요소들에 대하여 더해서 T가 되는 요소를 bSum에서 구할 것이다. 그러기 위해 일단 bSum을 정렬한다. aSum의 각 요소들에 대해 ..

    [Java] 백준 2568 (전깃줄 - 2) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2568 (전깃줄 - 2) Gold 1

    Problem : https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net Approach 겉으로는 그렇게 보이지 않을지도 모르지만 LIS (Longest Increase Subsequence) 문제이다. 한 쪽 전봇대를 오름차순으로 정렬한 뒤, 최대 LIS의 요소가 아닌 전깃줄들을 제거하면 된다. LIS 는 시간제한에 따라(입력데이터의 범위에 따라) DP 혹은 이분탐색으로 풀이가 가능한데, 여기서는 이분탐색으로 풀이를 해야한다. 이분 탐색을 이용하..

    [java] 백준 14003 (가장 긴 증가하는 부분 수열 5) Gold 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 14003 (가장 긴 증가하는 부분 수열 5) Gold 1

    문제 원문 링크 : https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net Approach 이 문제는 백준 12015번 가장 긴 증가하는 부분 수열 2 과 백준 12738번 가장 긴 증가하는 부분 수열 3 의 문제에 LIS을 추가로 출력해야 하는 문제이다. 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가..

    [java] 백준 12738 (가장 긴 증가하는 부분 수열 3) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 12738 (가장 긴 증가하는 부분 수열 3) Gold 2

    문제 원문 링크 : https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net Approach LIS(Longest Increasing Subsequence)는 Backtracking을 이용한 DP 방식과 이분탐색 방식이 가능하다. DP 방식은 O(N^2) 의 시간복잡도를 가지며, 이분 탐색은 O(NlogN)의 시간복잡도를 가진다. 이 문제에서는 입력의 크기가 최대 1,000,000 이므로 DP를 이용한 풀이는 시간이 너무 ..

    [java] 백준 12015 (가장 긴 증가하는 부분 수열 2) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 12015 (가장 긴 증가하는 부분 수열 2) Gold 2

    문제 원문 링크 : https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net Approach LIS(Longest Increasing Subsequence)는 Backtracking을 이용한 DP 방식과 이분탐색 방식이 가능하다. DP 방식은 O(N^2) 의 시간복잡도를 가지며, 이분 탐색은 O(NlogN)의 시간복잡도를 가진다. 이 문제에서는 입력의 크기가 최대 1,000,000 이므로 DP를 이용한 풀이는 시간이 너무 오래걸리므로 이분탐색을 이용한 ..

티스토리툴바