문제 https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 풀이 전형적인 다익스트라 문제입니다. 다익스트라 알고리즘을 사용할 수 있는 조건이 몇 가지가 있습니다. 1. 가중치는 모두 0 이상이어야 한다. 2. 방향 그래프를 가정으로 둔다. 3. 사이클이 없어야 한다. 위 문제에서는 무방향 그래프가 주어졌기 때문에, 간선을 분리해서 방향 그래프로 바꾸었습니다. 소스 코드 import java.util.ArrayList; import java.ut..
Java/BOJ
문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 이전에 포스팅한 백준 2003. 수들의 합2 문제와 매우 유사합니다. 풀이 보러 가기 만약 수들의 합2 문제를 풀지 않으셨다면 위 문제부터 푸는 것을 추천드립니다. 위 문제의 풀이에서 포인터 사이의 간격을 최소로 갱신해주기만 하면 됩니다. 소스 코드 import java.util.Scanner; public class Main { public static void main..
문제 https://www.acmicpc.net/problem/19951 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 풀이 누적합을 이용해야하는 문제입니다. 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ a ≤ b ≤ N 입력값의 범위가 위와 같아서, 누적합을 이용하지 않고 배열을 일일이 연산할 경우에는 시간 복잡도가 O(N^2)으로 1초의 시간 제한을 넘어가게 됩니다. 그래서 누적합 배열에 모든 숫자를 넣는 것이 아니라, 처음과 끝만 기록합니다. for(int i = 0;i
문제 https://www.acmicpc.net/problem/25195 25195번: Yes or yes 첫째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($1 \leq N, M \leq 100\,000$) 이후 $M$줄에 걸쳐서 간선의 정보를 나타내는 두 정수 $u$, $v$ 가 주어진다. 이는 정점 $u$ 에서 정점 $v$ 로 가는 www.acmicpc.net 풀이 BFS, DFS 문제입니다. 문제의 포인트는 팬클럽 곰곰이를 거치지 않고 더 이상 이동할 수 없는 간선까지 도달할 수 있는가? 입니다. 우선 팬클럽 곰곰이의 정점을 boolean[] gomgom 배열에 저장해두었습니다. 그리고 BFS 탐색시에 gomgom 배열을 체크합니다. 만약 현재의 정점이 gomgom[] 배열의 t..
문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 BFS 문제입니다. 구역의 개수가 2이상이거나, 얼음이 존재하지 않을 때까지 반복문을 통해 얼음을 녹여야 합니다. addIce() meltIce() checkBlock() 의 세 가지 메서드 순서로 분리해서 문제를 해결했습니다. addIce()는 map[][] 배열의 얼음을 queue 자료 구조에 집어 넣는 메서드입니다. 그리고 동시에 다음 연도에 얼마나 줄어들지를 카운트해서 de..
문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 백준 11053. 가장 긴 증가하는 부분 수열의 문제와 매우 유사한 DP 문제입니다. 더보기 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = ..
