알고리즘 (60) 썸네일형 리스트형 백준(BOJ) 11404: 플로이드 https://www.acmicpc.net/problem/11404 기본 Floyd-Walshall문제이다. 문제 조건에 두 도시간의 노선은 하나만 아니라는 조건이 있는데 이것만 입력받을 때 적절하게 처리해 주면 된다. //다익스트라=그래프 있어야 함. 벨만 포드: 그래프 없어도 됨. 플로이드. 그래프 있어야 함. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; public class Testing3{ static int[][]map; stat.. 백준(BOJ) 1865: 웜홀 #bellman https://www.acmicpc.net/problem/1865 (복습. 벨만포드: 음의주기가 있을때도 최단거리를 구할수 있고 음의주기가 있다면 판별할 수 있다. n번 반복하여 매번 모든 간선에 대해 dsit를 갱신한다. n-1번째에 dist가 갱신된다면 그것은 음의 주기가 있다는 것이다) 출발했던 지점으로 다시 돌아왔을때 시간이 되돌아간(시간이 줄어든)경우가 있는지를 묻고 있다. 기본적으로 벨만포드는 음의주기가 있을때를 포함하여 한점에서 다른 모든 정점까지의 거리를 구하기 위한 알고리즘이다. 그런 알고리즘이 이러한 출발정점으로 되돌아 왔을 경우에 별다른 코드 변경없이 쓰일수 있다는 것이다(물론 시간초과를 해결하기 위한 boolean변수는 필요했다). 어떻게 이것이 가능할까? 문제에서는.. 백준(BOJ) 1092: 배 https://www.acmicpc.net/problem/1092 문제가 깔끔하지 않을수 있다. 여기서 깔끔하지 않다는 것은 어떠한 명확한 알고리즘을 묻는것도 아니고, 그 알고리즘을 감추어 놓은 것도 아니고, 알고리즘과 관련된 어떠한 참신한 생각을 떠올려야 풀리는 문제도 아닌 문제를 말한다. 하지만 이런 더러운 문제도 가치가 있다. 왜? 이러이러한 문제가 내가 알고있는 어떠한 해결법으로는 깔끔하게 풀리지 않는다는 것을 알려준다는 점에서 그러하다. 나는 이문제가 "최소 회의실 개수" 문제와 같이 우선순위 큐를 이용하여 풀릴줄 알았다. 그래서 그렇게 접근해 보았지만 예제 테스트를 모두 통과했지만 결국 오답이 나왔다. 코드는 상당히 지저분했다. 즉, 최소 회의실 문제는 PriorityQueue에 넣는 것도 회.. 백준(BOJ) 1238: 파티 https://www.acmicpc.net/problem/1238 출처: https://steady-coding.tistory.com/106 다익스트라(Dijkstra)는 한정점에서 그 정점을 제외한 다른 모든 정점까지의 최단거리를 구할때 쓰이는 알고리즘이다. 그렇다면 다른 모든 정점에서 그 하나의 정점까지의 각각의 최단거리는 어떻게 구할까? 입력을 반대로 받아서 다익스트라 알고리즘을 적용하면 된다. 이 문제에서 배운것: 여러개의 정점에서 한정점으로 가는 각각의 최단거리는 출발점과 도착점에 대해 받은 정보를 반대로 적용하여 다익스트라 알고리즘을 적용하면 쉽게 구할 수 있다. import java.io.BufferedReader; import java.io.InputStreamReader; import j.. 백준(BOJ) 1753: 최단경로 https://www.acmicpc.net/problem/1753 처음에 인접리스트로 풀었다. 통과가 되었다. 하지만 방향그래프인만큼 인접행렬로 풀려고 시도를 하였다 => 메모리 초과가 났고 아래 글을 발견했다. 관련내용은 "3."번이다. https://www.acmicpc.net/board/view/34516 따라서, 방향그래프라고 해서 반드시 인접행렬을 사용해야만 하는 것은아니다. 아래는 인접행렬로 구현한 메모리초과가 나는 풀이다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Testing3 { static class Point { int vertex; int weight.. 백준(BOJ) 11657: 타임머신 /* 출력 초과를 논리적으로 계산하는 습관. 처음에는 출력초과가 나왔다. 이후 dist배열의 int를 long으로 바꾸니 통과되었다. 이 문제에서 출력 초과가 발생하는 이유는 -1을 출력해야 하는 상황에서 각 도시로 가는 최단 거리들을 출력하기 때문입니다. 질문하신 내용처럼 기존 dist에 들어있는 INF가 초과되어 overflow가 발생하지는 않으나, 이 문제는 가중치가 음수인 것이 허용되는 벨만-포드 알고리즘 문제입니다. 음수 사이클이 존재한다면 끝 없이 최소값이 갱신될 수 있고 이 때문에 출력초과가 발생하는 것입니다. 왜 이 때문에 출력초과가 발생하느냐? 가 궁금하실텐데 결론부터 말하자면 underflow때문입니다. 문제에서 주어진 조건인 정점의 개수가 500개, 간선의 개수가 6000개, 최소 가.. 백준(BOJ) 20546: 🐜 기적의 매매법 🐜 https://www.acmicpc.net/problem/20546 한번에 맞긴 했지만 문제 난이도를 생각할때 시간이 너무 오래 걸렸다. 뭔가 solution함수가 분기문이 많아 지저분한 느낌이 든다. 다른 코드는 어떤지 살펴보자. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main{ static int solution1(int asset, int[]price){ int myStock=0; for(var p:price){ if(asset/p>0) { int num= (asset / p); asset-=(num*p);.. 백준(BOJ) 20056: 마법사 상어와 파이어볼 https://www.acmicpc.net/problem/20056 출처: https://tussle.tistory.com/985 https://developer-u.tistory.com/101 접근 방법 이 문제에 핵심 1. 1번행과 N번 행은 연결, 1번열과 N번 열은 연결되어있습니다. 2. 마법사 상어는 문제의 조건에 맞게 파이어볼을 발사합니다. 3. K번 이동 명령을 진행한 후, 남아있는 파이어볼 질량의 합을 결과로 출력합니다. 알고리즘 진행 순서. 1. 입력된 정보를 저장합니다. 2. K번 이동명령을 진행합니다. 3. 남아있는 파이어볼 질량의 합을 결과로 출력합니다. 파이어볼 이동명령 1번행과 N번 행은 연결, 1번열과 N번열은 연결? ※처음에 이 문장에 대해서 이해하지 못하였지만 예제입력을 시.. 이전 1 2 3 4 5 6 ··· 8 다음
