전체 글
-
[백준]11657. 타임머신알고리즘/백준 2021. 1. 7. 00:26
📄 링크 타임머신 💡 문제 분석 음의 가중치를 가질 수 있는 최소 비용 문제입니다. 음의 가중치를 가지고 있는지 판단할 수 있는 벨만-포드 알고리즘을 사용 해야겠다고 생각했습니다. V - 1번을 완화작업을 하면 모든 정점의 최소 비용을 알 수 있습니다. 그리고 V번째 완화 작업을 했을 때 실패하지 않고 성공한다면 음수 간선이 존재하는 것입니다. 문제를 풀면서 계속 출력초과 에러가 발생해서 계속 고민을 하다가 아주 큰 음수 가중치를 계속 더하면 언더플로우가 발생할 수 있다는 것을 깨달았습니다. 그래서 upper 배열 값을 long 타입으로 바꿨더니 해결이 되었습니다. ⌨️ 코드 import java.util.ArrayList; import java.util.Arrays; import java.util.Sc..
-
[백준]1238. 파티알고리즘/백준 2021. 1. 7. 00:16
📄 링크 파티 💡 문제 분석 N개의 정점, M개의 간선을 가진 그래프입니다. 무향 그래프였다면 도착지인 X가 정해져 있어서 한 번의 다익스트라로 가능했을 것 같은데 방향 그래프였기 때문에 플로이드-와샬을 쓰기로 했습니다. N이 1000이기 때문에 플로이드-와샬의 시간 복잡도 O(N^3)이므로 빠듯해보였습니다. 그래서 플로이드-와샬에서 i에서 k로 가는 정점이 없다면 건너 뛰는 가지치기를 적용했습니다. ⌨️ 코드 import java.util.Arrays; import java.util.Scanner; public class _1238_파티 { static int N, M, X; static int[][] adj; public static void main(String[] args) { // 입력 Scan..
-
[백준]1916. 최소비용 구하기알고리즘/백준 2021. 1. 7. 00:04
📄 링크 최소비용 구하기 💡 문제 분석 출발 지점과 도착지점이 제시되어 있고 간선에 가중치가 붙어 있기 때문에 다익스트라 혹은 벨만-포드로 풀 수 있다고 생각했습니다. 음의 가중치가 없어서 굳이 벨만-포드는 쓰지 않고 다익스트라를 사용했습니다 우선순위큐 정렬을 할 때 comparable을 쓸 때와 comparator 혹은 lambda 할수를 쓸 때 메모리와 시간이 많이 차이가 나는 것을 알게 되었습니다. 여유가 되는 문제들은 lambda를 사용하고 시간이 빠듯하면 comparable을 사용하는 것이 좋을 것 같습니다. ⌨️ 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import..
-
다익스트라 알고리즘알고리즘/이론 2021. 1. 6. 23:55
다익스트라 알고리즘 📄 설명 다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 거리를 찾는 알고리즘입니다. 음수 가중치가 있는 그래프에서는 정확한 최단 거리를 구할 수 없으므로 사용하면 안됩니다.(그럴 땐 벨만-포드) 단일 정점에서 다른 정점으로의 최단거리를 구하는 알고리즘이기 때문에 모든 정점들 간의 최단거리를 알고 싶다면 플로이드-와샬 알고리즘을 사용하는 것이 구현이 편합니다 우선순위큐를 이용한 정렬을 이용하기 때문에 O(ElogV)의 시간 복잡도를 가지게 됩니다. 💡동작 과정 각각의 정점마다 현재까지 발견한 최소 경로를 저장할 dist 배열을 만듭니다. 최단 경로를 구해야 하기 때문에 처음에는 모든 값을 아주 큰 값으로 초기화 시킵니다. 여기서는 1번 정점을 시작점으로 정했기 때문에 dist[1]..
-
[백준]10021. Watering the Fields알고리즘/백준 2021. 1. 5. 01:22
📄 링크 Watering the Fields 💡 문제 분석 최대 2000개의 정점을 가진 그래프의 MST를 구하는 문제입니다 정점들 사이의 거리를 구하고 입력에 주어진 C값으로 간선의 수를 제한하고 있지만, 상당히 많은 간선이 생길 것 같아 프림 알고리즘을 사용하기로 했습니다. 프림 알고리즘 모든 정점들에 굉장히 큰 값을 주고 시작합니다 임의로 시작 정점을 골라 연결되어 있는 정점들의 가중치를 갱신합니다 정점들 중 가장 가중치가 작은 정점을 골라 이를 반복합니다.(우선순위 큐를 사용할 수도 있습니다) 모든 정점을 갱신했다면 종료 → 이 문제에서는 그래프가 연결되어 있지 않은 경우가 존재하기 때문에 모든 정점을 검사하여 한 번도 갱신되지 않은 정점이 있다면 분리되어 있다고 판단하여 -1을 출력하도록 하였습..
-
[백준]20530. 양분알고리즘/백준 2021. 1. 5. 01:01
📄 링크 양분 💡 문제 분석 이런 문제가 왜 골드2인지 모를 정도로 힘든 문제였습니다. 처음엔 아무 생각 없이 dfs로 모든 경로를 다 찾아보려 했지만 정점이 200000개.. 당연히 시간초과가 떴습니다 이 문제의 핵심은 간선의 개수가 정점의 개수와 같기 때문에 반드시 하나의 사이클이 존재한다는 것입니다. 예제 입력을 그래프로 그려보았습니다. 어떤 두 정점으로 가는 단순 경로는 사이클이 하나이기 때문에 2개 또는 1개 밖에 나올 수 없습니다 2가지가 나오는 경우 두 정점이 모두 사이클에 속해 있는 경우 양 방향으로 갈 수 있기 때문에 2가지 경로가 존재합니다 LCA(최소 공통 조상)이 다른 경우 사이클을 구성하고 있는 정점들을 루트로 아래쪽 부분을 서브트리라고 생각했을 때 다른 루트에서 뻗어나왔다면 사이..
-
[백준]1904. 01타일알고리즘/백준 2021. 1. 5. 00:58
📄 링크 01타일 💡 문제 분석 입력 N이 100만으로 꽤 큰 숫자입니다. 기존 숫자에서 00을 더할지 1을 더할지를 선택하는 방법으로 메모이제이션을 사용했었는데 재귀로 문제를 풀면 스택 오버 플로가 발생하였습니다. 어쩔 수 없이 반복적 dp를 사용하였습니다. 덧셈을 할 때 계속 15746으로 나누어 주지 않으면 오버플로가 발생하게 됩니다 ⌨️ 코드 import java.util.Scanner; public class _1904_01타일 { static int[] cache = new int[1000001]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); cache[1] =..
-
[백준]10971. 외판원 순회2알고리즘/백준 2020. 12. 21. 23:39
📄 링크 외판원 순회2 💡 문제 분석 알고리즘의 대표적인 문제입니다. 모든 도시를 방문하고 시작 지점으로 돌아 오는데 필요한 최소 비용을 구하는 문제입니다. 완전 탐색으로 모든 경로를 계산해서 최소 비용을 구하는 방법을 사용할 수 있지만, 이럴 경우 O(N!)의 시간 복잡도가 소요됩니다. 이 문제에서는 N의 최대값이 10이기 때문에 10! = 3628800으로 시간 초과가 나지 않지만, N이 12를 넘어가게 되면 약 5억으로 시간 초과가 날 것입니다. 그렇기 때문에 부분문제로 쪼개서 동적 계획법을 사용하기로 했습니다. tcp(cur, visited) = 현재 방문한 도시들이 visited이고 현재 위치가 cur일 때 모든 도시를 방문하고 시작 지점으로 돌아가는데 필요한 최소 비용 이렇게 최적 부분 구조로..