은비블로그

https://www.acmicpc.net/problem/1753[코드]package boj;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;/*방향그래프가 주어지면 시작점에서 다른 모든 정점으로의 최단 경로를 구하기모든 간선치의 가중치는 10 이하의 자연수 */public class Main_1753_최단경로 { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static StringBuilder s..

https://www.acmicpc.net/problem/11779[풀이과정]그냥 최소비용을 구하는 것이 아니라 경로까지 구하는 문제였다.경로를 구할 때 처음엔 배열 인덱스를 순서로 해서 넣을까 하다가 불가능한 것 같아서 엄청 고민했다.그러다 현재 도시 번호를 인덱스로 두고 이 도시에 오는 바로 이전 번호를 값으로 계속 갱신하면 기존 다익스트라 방식 그대로 하면서 복잡한 코드가 필요없을 것 같아 실행했다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Priorit..

https://www.acmicpc.net/problem/1092[풀이과정]처음에 복잡도가 N*M인 코드를 작성했는데 틀렸다. 왜 틀렸는지 아직도 잘 모르겠음..가장 중요했던 건 내림차순으로 정렬하는 것인 것 같다. 가장 큰 수들끼리 비교해서 옮기지 못 하면 -1 반환하고, 아니면 계산했는데,만약 크레인 무게 제한이 20 10 10일 때, 박스 무게가 20 20 10인 경우를 가정했을 때 20 10 / 20 이렇게 두 번 옮겨져야 한다. 그럼 박스를 가리키는 idx를 어떻게 앞으로 옮길지 엄청 고민했는데, 박스를 삭제하면 되는 일이었다. 옮겨진 박스를 삭제하면서 while문에서 초기화를 0으로 해주면 저절로 남겨진 박스 중 가장 무거운 박스를 가리키게 된다.  [코드]import java.io.Buffe..

https://www.acmicpc.net/problem/9205[풀이과정]모든 편의점을 들려야 한다고 생각했다.편의점을 들리지 않고도 페스티벌에 도착할 수도 있으므로 갈 수 있는 최적의 경로를 찾는 방식으로 해결해야 했다.BFS를 통해서 갈 수 있는 경로를 탐색하며 페스티벌에 도착하면 happy를 출력했다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;/*상근이네(출발), 맥주 한 박스(20개), 50미터 당 한 병씩, 페스티벌(도착)맥주를 더 구매할 수도 있지만 소지할 수 있는 맥주는 최대 20병 */public class Main { st..

https://www.acmicpc.net/problem/1245 [풀이과정]쉬운 문제인데 문제 이해를 이상하게 해서 엄청 헤맸다.DFS를 사용했고 모든 시작점을 산봉우리라고 가정한 후 탐색했다.시작점의 인접격자 중 시작점보다 값이 큰 곳이 있으면 산봉우리가 아니므로 isTop을 false로 바꿔주었고높이가 같은 곳이 있으면 같은 산봉우리로 취급되므로 dfs를 돌려주었다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/* N*M의 농장. 산봉우리가 총 몇 개인지 세야 한다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인..

https://www.acmicpc.net/problem/1504[풀이과정]처음엔 모든 경우의 수를 탐색하며 V1, V2를 방문하는지 체크하는 방식으로 하려 했다. 하지만 이미 방문한 노드와 간선을 재방문할 수 있다는 부분에서 그렇게 진행하면 무한루프가 발생할 것 같아 방식을 바꾸었다.i ) 1부터 V1까지의 최단 거리 + V1부터부터 V2까지의 최단 거리 + V2부터 N까지의 최단 거리ii ) 1부터 V2까지의 최단 거리 + V2부터부터 V1까지의 최단 거리 + V1부터 N까지의 최단 거리 중 더 작은 값이 최단 경로이고만일 경로가 없다면 초기에 설정해둔 INF 값보다 큰 값이 도출되므로 -1을 반환하면 된다. [코드]import java.io.BufferedReader;import java.io.IO..

https://www.acmicpc.net/problem/4803 [풀이과정]DFS 문제였다. 탐색을 하며 사이클이 존재하는지 여부를 체크하는 것이 중요.처음엔 이미 방문한 노드를 재방문했을 때 사이클이 발생한다고 했는데 여기서 오류가 생겼다.이미 방문한 노드 중엔 현재 주변을 탐색 중인 노드가 포함이었는데 이때는 제외했어야 했다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;import java.util.ArrayList;public class Main { static BufferedReader br = new Buf..

https://www.acmicpc.net/problem/11404 [문제풀이]플로이드 워셜 알고리즘 문제였다.플로이드 워셜 알고리즘이란 모든 정점에서 모든 정점까지의 최단 거리를 구하는 것으로,초기 그래프를 행과 열이 같은 곳을 제외하고 매우 큰 값으로 저장하여 최솟값으로 갱신하며 최단 거리를 찾는 알고리즘이다. 출력 할 때 INF으로 남은 값을 0으로 초기화해주어야 했는데 그 부분을 놓쳤다. 좀 더 꼼꼼하게 풀자!  [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*n개의 도시.한 도시에서 출발하여 다른 도시에 도착하는 m..

https://www.acmicpc.net/problem/1806 [문제풀이]처음엔 왼쪽 포인터와 오른쪽 포인터가 가리키는 두 수 중 더 작은 수를 빼주며 최소길이를 구하려고 했다.하지만 S 이상의 부분합을 전부 볼 수 없다는 문제점이 있었다.그래서 왼쪽과 오른쪽 포인터를 0에서 시작하여 오른쪽만 움직이다가 부분합이 S 이상이 되면 왼쪽 포인터가 가리키는 값을 빼준 왼쪽 포인터를 오른쪽으로 한 칸 옮기는 방식을 구현하였다. [정답]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*10,000 이하의 자연수로 이루어진 길이 N짜리 수열..

https://www.acmicpc.net/problem/30023 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;/*N개의 전구가 일렬로 세워져 빨, 초, 파 중 하나의 색으로 빛나고 있음.연속한 세 전구를 선택하여 상태를 바꿀 수 있음.빨 -> 초, 초 -> 파, 파 -> 빨모든 전구가 같은 색으로 빛나게 하려면 이 과정을 최소 몇 번 수행해야 하는지 구해라. */public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));..