[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..

→2021.06.09

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명이 놀이기구를 탈 수 있기 때문이다.)..

→2021.06.06

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개 초과인지 아닌지 판단한다. 초과라면, 해..

→2021.06.05

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를 갱신하..

→2021.06.04

Algorithm/Baekjoon Online Judge

[Java] 백준 21774 (가희와 로그 파일) Gold 3

Problem : https://www.acmicpc.net/problem/21774 21774번: 가희와 로그 파일 2000년부터 2020년까지 연도 중에, 윤년인 것은 2000, 2004, 2008, 2012, 2016, 2020년 입니다. www.acmicpc.net Approach 문자열을 파싱하여 DP를 구성하고, 이분 탐색의 lowerbound, upperbound를 활용해야 하는 문제이다. 문제 풀이의 로직은 다음과 같다. 먼저 문자열을 파싱한다. 주어진 시각 문자열이 YYYY-MM-DD hh:mm:ss 형식이고 순서대로 주어지므로, -:와 공백문자를 없애면 자연스럽게 정렬이 된 상태가 된다. (본인은 Long 타입으로 형변환을 하였지만, String 타입이어도 자연스럽게 사전순으로 정렬 상..

→2021.06.02

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의 각 요소들에 대해 ..

→2021.04.21

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 혹은 이분탐색으로 풀이가 가능한데, 여기서는 이분탐색으로 풀이를 해야한다. 이분 탐색을 이용하..

→2021.04.16

Algorithm/Programmers

[java] 프로그래머스 (입국심사) Level 3

Problem : https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr Approach 이분탐색(이진탐색)을 이용하는 문제였다. 주의할 점은 모든 자료형을 long으로 해줘야 런타임에러가 발생하지 않는다. 일단 이진탐색을 가능하게 하기 위해 정렬을 한다. 그리고 시간을 이분하면서 주어진 시간으로 몇명의 사람을 처리할 수 있는지를 체크한다. 주어진 사람 수 n미만 이면 시간이 더 필요하므로 반으로 나눠진 시간의 오른쪽..

→2021.02.04

티스토리툴바