나아가는중

[백준 Baekjoon] 15711번 환상의 짝궁- JAVA 문제 풀이 문제의 설명만 보면 정말 간단한 문제처럼 보인다. A, B를 더한 값을 소수 2개로 만들 수 있는지 검사하면 된다. 하지만 제한사항의 A와 B의 최댓값이 2 x 10^12로 매우 커서 일반적인 방법으로는 불가능하다. A와 B의 합이 최대 4 * 10^12로 범위가 매우 큰데 그것의 루트값 2000000으로만 검사해주면 된다.. 합이 4미만의 경우 합이 4미만인 경우 소수 2개로 만드는 방법은 없다. 합이 짝수인 경우 골드바흐의 추축에 의하면 2보다 큰 모든 짝수는 두 개의 소수의 합으로 표시할 수 있다. 합이 홀수인 경우 두 수의 합이 홀수가 되려면 짝수 + 홀수이어야만 한다. 따라서 짝수인 소수 + 홀수인 소수로 동일한 합을 만들 ..

백준 Baekjoon 18870번 좌표 압축 - JAVA 문제 풀이 주어진 입력 값들을 정렬했을 때 몇번째 순서인지 출력하는 문제이다. 입력 배열은 후에 다시 사용되어 새로운 배열에 복사한 다음 정렬한다. Map 을 사용하여 0부터 좌표의 순서를 저장한다. 중복되는 좌표값들이 있기 때문에 Map을 사용한다. 입력 값들을 Map에서 찾으면 그 순서를 알 수 있다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Strin..

백준 Baekjoon 1504번 특정한 최단 경로 - JAVA 문제 풀이 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 위의 두 가지 방법 중에 최단거리로 N까지 가는 방법을 구하는 문제이다. 다익스트라 알고리즘을 사용하여 각 이동(예, 1->v1, v1->v2, 1->v2)의 최단거리를 구하고, 두 가지 방법 중에 최단 경로를 출력하면 된다. 각 이동에 대해 다익스트라를 사용하여 총 6번 해도 되지만, 편의상 1, v1, v2에서의 모든 정점과의 최단거리를 구하여 사용하였다. min[0] = 1에서 모든 정점의 거리 min[1] = v1에서 모든 정점의 거리 min[2] = v2에서 모든 정점의 거리이다. 두 방법의 최단경로는 아래의 값을 비교해주어 구한다. min[0][v1](1..

백준 Baekjoon 1238번 파티 - JAVA 문제 풀이 다익스트라 알고리즘을 사용하여 푸는 문제이다. 주로 양방향 그래프가 주어지고 다익스트라 알고리즘을 활용하여 푸는 문제들이 나왔는데, 이번에는 단방향 그래프가 주어졌다. 모든 마을에서 다익스트라를 사용하여 최단거리를 구하는 방법도 존재하지만, X를 출발지로 지정하면 다익스트라 알고리즘을 두번만 사용하여 구할 수 있다. 정방향과 역방향 그래프와 각각의 최단 거리를 저장할 배열이 필요하다. 주어진 단방향 그래프를 그대로 입력받고 다익스트라를 사용하면 모든 마을에서 X까지의 최단거리를 구할 수 있다. 하지만 반대로 X에서 마을로 돌아오는 길을 구하기 위해서는 입력 받는 그래프를 역으로 바꿔 저장한 다음 다익스트라를 사용하여 구해야 한다. 소스 코드 i..

백준 Baekjoon 2616번 소형기관차 - JAVA 문제 풀이 다이나믹 프로그래밍과 누적합을 사용하여 푸는 문제이다. 제한사항의 기관차의 수가 그리 크지 않어 dfs탐색으로도 풀 수는 있을거 같지만, 시간이 오래걸리고 문제에서 원하는 풀이 방식은 아닌듯 했다. 누적합을 사용하여 뒤에 DP에서 기관차가 끌 수 있는 최대 객차의 수의 승객의 합을 쉽게 구할 수 있다. DP의 점화식은 다음과 같다. dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - max] + sum[j] - sum[j - max]) i를 1 ~ 3 범위로 증가 시키며 각 숫자의 기관차가 운송할 수 있는 최대의 손님 수를 구한다. j를 i * max의 범위부터 시작하는데, 예시로 주어진 문제를 예로 들어..

백준 Baekjoon 16954번 움직이는 미로 탈출 - JAVA 문제 풀이 BFS탐색을 사용하여 캐릭터를 이동 시킨다. 최초에는 처음 시작위치인 7,0을 넣고 시뮬레이션을 시작한다. 큐에서 캐릭터를 현재 케릭터들의 위치들을 꺼내와 9방향으로 이동할 수 있는지 검사하고 새로운 위치를 큐에 추가한다. 큐의 사이즈만큼만 반복하여 큐에서 캐릭터를 꺼내면 새로 추가되는 위치는 탐색하지 않게 된다. 동일한 위치에 여러 캐릭터가 이동하는 것을 방지하기 위해 visit배열을 둔다. visit배열은 매 턴이 끝날때 마다 새로 생성되어야 한다. 이전에 있었던 위치로 돌아가야 하는 상황도 존재한다. 새로운 위치로 이동시켜 큐에 추가한 위치가 벽이 이동하면서 벽과 겹쳐질 수 있어 큐에서 꺼냈을 때 검사해야 한다. 케릭터 이..

[백준 Baekjoon] 14719번 빗물 - JAVA 문제 풀이 특별한 알고리즘의 사용은 없는 구현을 사용한 문제이다. 빗물이 고이는 두가지 경우를 생각하여 각각 구해줌으로 문제를 풀었다. 1 왼쪽 기둥보다 오른쪽의 기둥이 큰 경우. 좌에서 우로 순회한다. 1.1 왼쪽 기둥의 높이를 h, 위치를 left에 저장하였다. 1.2 왼쪽 기둥보다 오른쪽 기둥이 큰거나 같은 경우 양 기둥 사이를 순회하며 두 기둥중 작은 기둥의 높이에서 뺄셈을 한다. 1.3 왼쪽 기둥과 위치를 새로 최신화 해준다. 2 왼쪽 기둥보다 오른쪽의 기둥이 작은 경우. 우에서 좌로 1에서 구한 마지막 왼쪽 기둥까지 순회한다. 2.1 1에서 구한 마지막 왼쪽 기둥까지의 빗물을 계산이 완료되어 마지막 왼쪽 기둥까지만 한다. 2.2 오른쪽 기..

백준 Baekjoon 16235번 나무 재테크 - JAVA 문제 풀이 구현, 시뮬레이션으로 분류된 문제이다. 문제 설명을 잘 읽고 정리하여 따라 하는것으로 풀 수 있다. 풀이에 대한 설명보다 코드의 주석을 보는것이 이해가 쉬룰 것이다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System..

백준 Baekjoon 2749번 피보나치 수 3 - JAVA 문제 풀이 피보나치 수의 개념을 알고 여러 문제들을 풀어봤지만, 이번 문제처럼 큰 입력은 처음으로 주어졌다. 메모리제이션을 하고 최대한 시간초과가 나지 않게 하려 해도 불가능하여 검색을 해보니 피사노라는 피보나치의 속성이 있고, 이를 활용하여 문제를 풀 수 있었다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead..

백준 Baekjoon 15684번 사다리 조작 - JAVA 문제 풀이 구현 + dfs + 완전탐색 문제이다. 문제가 길고 복작해서 정말 읽기 싫은 문제였다. 최대 사다리를 3개까지 놓아 i번째 사다리가 i번으로 가게 만드는 문제이다. 사다리를 입력 받을 때 양측 통행{(x,y), (x,y+1)}이 가능하도록 놓는 것이 편하다. i번에서 i번 탐색 시 좌 우 어느 방향으로 이동해야 하는지 알 수 있으며, 이렇게 하면 검사시 두 점을 검사하는 것으로 두 가로선이 연속하거나 접하지 않게 놓을 수 있다. 사다리를 최대 3개까지 놓을 수 있어 0 ~ 3개를 놓는 경우를 dfs로 검사한다. dfs 탐색 시 이미 검사한 가로선 위치(i)를 매번 검사하지 않도록 i = h에서 검사하게 한다. x는 세로 높이가 되고 y..