https://www.acmicpc.net/problem/2458알고리즘 분류 : 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 최단 경로, 플로이드–워셜❓문제🔅해석모든 학생의 키를 비교한 횟수를 알아야하기 때문에 전체 쌍의 계산이 필요한 "플로이드-워셜" 알고리즘을 사용한다. 1. 거리 초기화 만약 두 정점 간에 직접 연결된 간선이 있다면 그 가중치로 초기화하고, 연결되어 있지 않다면 무한대(또는 매우 큰 값)로 설정한다. 자신에게 가는 거리는 0으로 설정한다.for (int n = 1; n 2. 동적 프로그래밍(DP) 적용 각 정점을 중간 정점으로 고려하여, 다른 모든 정점 쌍에 대해 최단 경로를 갱신한다. 즉, 정점 k를 중간 정점으로 사용하는 경우, i에서 j로 가는 경로가 i -> k ->..
https://www.acmicpc.net/problem/11657알고리즘 분류 : 그래프 이론, 최단 경로, 벨만–포드❓문제 🔅해석 1. 거리 초기화 시작 정점의 거리를 0으로 설정하고, 나머지 모든 정점의 거리를 무한대로 설정한다. 2. 거리 갱신 모든 간선에 대해 V-1번 반복해서 간선의 시작 정점에서 도착 정점으로 가는 경로가 현재 알려진 경로보다 짧다면, 그 경로를 갱신한다.dist[from] > dist[to] + edge.cost 이므로 dist 업데이트를 한다. dist[from] > dist[to] + edge.cost 이므로 dist 업데이트를 한다. dist[from] == dist[to] + edge.cost 이므로 dist 업데이트 되지 않는다. dist[from] 이렇게 (..
https://www.acmicpc.net/problem/1753알고리즘 분류 : 그래프 이론, 데이크스트라, 최단 경로❓문제🔅해석음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제에서는 다익스트라 알고리즘이 사용된다.다익스트라 알고리즘은 인접리스트 형태로 그래프를 저장하고, Priority Queue를 사용하여 최소 비용의 정점이 먼저 나오도록 한다. // input5 615 1 11 2 21 3 32 3 42 4 53 4 6 1. 인접 리스트 생성ArrayList[] adjList = new ArrayList[V + 1]; 2. start로 부터 각 노드까지 최단거리를 담는 dist 배열과 노드를 방문했음을 체크하는 visited 배열을 생성한다. 3. Priority ..
https://www.acmicpc.net/problem/1922알고리즘 분류 : 그래프 이론, 최소 스패닝 트리❓문제🔅해석컴퓨터 == 정점선 == 간선 모든 컴퓨터(정점)를 연결하여 최소의 비용(가중치)을 얻기 위해 MST를 구현한다.MST를 구하기 위한 알고리즘에는 크루스칼, 프림이 있는데 크루스칼로 풀이해본다. // input691 2 51 3 42 3 22 4 73 4 63 5 114 5 34 6 85 6 8 1. 간선 정렬그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다. 2. 간선 선택정렬된 간선 리스트에서 순차적으로 간선을 선택한다. 이때, 선택된 간선이 사이클을 형성하지 않는다면 해당 간선을 최소 신장 트리에 추가한다. 3. 사이클 검증사이클이 형성되는지 확인하기 위해서 유니온-..
https://www.acmicpc.net/problem/2252알고리즘 분류 : 그래프 이론, 위상 정렬, 방향 비순환 그래프❓문제🔅해석위상정렬을 이용하여 풀이한다. 위상정렬은 비순회 방향 그래프에서 정점을 정렬하는 방식이며, 동일한 우선순위를 가진 작업들이 여러 가지 방법으로 나열될 수 있기 때문에 여러 개의 정렬 결과가 나올 수 있다. // input4 24 23 1 1. indegree 계산 및 indegree 배열 중에서 0인 노드를 Queue에 담는다. 2. Queue에서 pop를 하고, 3(pop 한 값)과 연결된 노드에 indegree를 하나 감소시킨다. 3. Queue에서 pop를 하고, 4(pop 한 값)와 연결된 노드에 indegree를 하나 감소시킨다. 4. Queue가 빌 ..
https://www.acmicpc.net/problem/9202알고리즘 분류 : 자료 구조, 그래프 이론, 문자열, 브루트포스 알고리즘, 그래프 탐색, 트리, 깊이 우선 탐색, 백트래킹, 트라이❓문제🔅해석Trie 알고리즘을 활용하여 문제를 해결한다. 먼저, 입력받은 단어들로 Trie를 생성한다."ACM'을 입력받았다면 아래와 같이 Trie 객체가 생성된다. for문을 순회하여 Trie 객체인 root를 완성하면 뒤에 N개의 맵을 입력받아 탐색한다. dfs를 작성할 때는 아래 6단계를 거쳐 작성하는 것을 추천한다. 1. 체크인visited 배열에 true 를 입력하고 현재 map 좌표에 있는 알파벳 하나를 Stringbuilder에 붙인다. 2. 목적지인가목적지의 기준은 1) 현재 노드가 단어이면서, ..
