문제 난이도GOLD I (링크)   문제 풀이각각의 독립된 섬들을 최단 거리로 연결하고 싶을 때, 놓을 수 있는 다리의 총 길이의 최소값을 구하는 문제.역시나 최소 신장 트리를 응용한 문제가 되겠다. 이번에는 각 간선을 구하는 것과 더불어, 이 섬이 어느 정점인지를 구하는 것도 필요하다. 결국엔 두 정점 사이의 간선을 구해서 문제를 풀어야하기 때문이다.  위의 그림처럼 문제에서 요한 3가지 올바르지 않은 방법과 함께, 추가로 두 가지만 주의한다면 쉽게 풀 수 있다. 처음 다른 섬을 만났을 때 만족하지 않는 조건이라면 바로 빠져나올 것.부끄럽게도 처음 코드를 완성시켰을 때,  다른 섬을 만났을 때, 종료 조건을 부족하게 작성하여 아래 그림처럼 더이상 탐색하지 못함에도 불구하고 탐색을 시켰다.   Union..

문제 난이도GOLD III (문제 링크)  풀이 [알고리즘] 벨만-포드(Bellman-Ford) 알고리즘벨만-포드 알고리즘은 그래프의 최단 경로를 구하는 알고리즘의 하나로, 다익스트라로 해결하지 못하는 음의 간선이 포함된 문제를 효과적으로 해결할 수 있는 알고리즘이다.  [알고리즘] 다mag1c.tistory.com 포스팅에서 학습했기 때문에 자세한 설명은 생략하고, 풀었던 방법만 나열해보고자 한다. 벨만-포드 알고리즘은 특정 출발점에서 모든 노드로의 최단 경로를 탐색하는 알고리즘이다. 또한 음수 사이클을 검출할 수 있다. 도달할 수 없는 노드를 표시하기 위해 INF에 가까운 값들로 초기화해서 사용할 수 있다.  첫번째 방법문제에서, 특정 노드를 언급하지 않았다. 한 노드에서 출발하여~~~이기 때문에, ..

문제 링크 Gold 4 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 첫 풀이 크게 시간, 메모리 고려를 하지 않아도 될 것 같아보여서 뇌를 빼고 풀어보려고 했다. (사실 Union Find에 자신이..) 단순 String배열을 활용하고, List에 String배열을 저장하여 정답을 도출하려고 했고, 문제에서 제공하는 테스트케이스를 만족해서 됐다!!! 라고 생각했다. import java.io.BufferedReader; import java.io.IO..

문제 링크 Gold 5 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 필자는 BFS를 이용해 풀었으며 실버 DP문제들 보다 난이도가 쉬운 것 같다. 처음에는, BFS 메서드를 통해 한 번 완전탐색을 끝낸 후 바로 결과를 도출시키려고 했고, 실패했다. 이유는 모든 결과를 고려하지 않아서 인 것 같다. 어떤 경우였냐면 //bfs메서드의 파라미터로 color을 받아 RGBCheck배열 체크 switch(color) { case 'R':..

문제 링크 Silver 1 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 단순 BFS 구현 문제로 너비를 +1, -1, *2의 경우로 두었고 문제 조건에 알맞게 예외상황에 대한 처리를 하면 되는데 N == K일 때의 상황을 고려하지 않아서 20분동안 삽질했다.. 꼼꼼하게 보고 놓치지 말자.. import java.io.BufferedReader; import java.io.IOException; import j..

난이도 Gold 5 문제 링크 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 BFS로 풀이했다. 각 너비는 주사위를 1~6번 까지 나오는 경우를 각 너비로 잡았다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class BaekJoon16928 { private stat..

난이도Gold 4 문제 링크https://www.acmicpc.net/problem/14500 14500번: 테트로미노폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변www.acmicpc.net 풀이DFS로 풀이하였으며 'ㅗ' 모양을 단순 DFS로 구현할 수 없어서 따로 메서드화 했지만 DFS 내부에서 cnt = 3일 때 조건을 주어 처리할 수도 있다. 원하는 방식대로 풀면 된다. 메서드 이름이 마땅히 생각나지않아 fuck로 지었...import java.io.BufferedReader; import java.io.IOException; import java.io...

문제 링크 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 엄청난 삽질을 했던 문제 한번에 풀겠거니 했는데 처음에는 메모리 초과가 발생했는데, 이유는 아마 String 배열 하나로 풀었기 때문인 것 같다. 어떻게 boolean 배열 없이 단순 String 배열로만 풀어보자 하고 고집하다가 계속 오답을 발생시켰다. 추가로, l과 r을 계산하는 조건을 구할 때, 처음에 String으로 받아서 charAt로 풀었기 때문에 메모리가 ..