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/11438알고리즘 분류 : 자료 구조, 트리, 최소 공통 조상, 희소 배열❓문제🔅해석순서input된 값을 adjacent list(양방향 간선)에 넣는다.BFS로 트리 탐색bfs로 트리를 탐색하면서 각 노드의 깊이(depth)와 부모(parent)를 기록한다. 희소 테이블(Sparse Table) 구성각 노드에 대해 2^k번째 부모를 미리 계산한다. 이 테이블을 이용하면, 두 노드의 깊이를 맞춘 후, 공통 조상을 빠르게 찾을 수 있다.Find LCA항상 b가 a보다 depth가 큰 노드(root로부터 먼)가 되도록 swapa, b의 depth 맞추기(0.에 의해 항상 b를 끌어올리게 된다)2에서 depth를 맞추었는데 a와 b가 같다면 lca를 ..
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/3830알고리즘 분류 : 자료 구조, 분리 집합❓문제🔅해석Union-Find 알고리즘으로 해결한다. 부모와 가중치를 함께 저장하기 위해 Node class를 정의한다. // TestCase34 7! 1 2 100? 2 3! 2 3 100? 2 3? 1 3! 4 3 150? 4 1 1. Initialize 2. "! 1 2 100" find를 통해 서로의 부모가 같은지 확인하고 같지 않다면, a의 부모를 b의 부모로 변경하여 하나로 합친다. 3. "? 2 3"2과 3의 부모를 확인한다. 2의 parent(=2) != 3의 parent(=3) 이므로 "UNKNOWN"를 반환한다. 4. " ! 2 3 100" 5. "? 2 3"2과 3의 부모를 확인..
https://www.acmicpc.net/problem/1717알고리즘 분류 : 자료 구조, 분리 집합❓문제🔅해석Union-Find의 기초 문제이다. Union 연산은 어떤 두 원소 a, b에 대해서 각 원소가 속한 집합을 하나로 합치는 연산이다.먼저 두 원소가 같은 집합인지 확인하고 같은 집합이 아니라면 하나로 합친다. 보통 같은 집합을 확인하는 과정은 부모의 번호를 기재하여 확인한다.Find 연산은 어떤 원소 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환한다. 문제의 예시를 아래와 같이 가정한다.//input7 40 1 31 1 70 7 61 1 3 1. 7 4n개의 집합을 생성한다. 각 집합의 부모는 자신을 가르키고있다. 2. 0 1 3union1과 3에 대해 parent를 확인하고 같..
https://www.acmicpc.net/problem/1202알고리즘 분류 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐 ❓문제🔅해석조건이 2개 이상이므로 우선순위 큐(PQ)를 사용하여 문제를 풀이한다. 보석의 속성이 2가지 있으므로 객체로 생성하여 짝을 이룰 수 있게한다. 가방에 넣을 수 있는 보석을 PQ에 담기 위해 가방과 보석의 무게를 오름차순 정렬한다. 이후 반복문을 돌면서 정답을 계산한다.1. 가방을 하나 고른다.2. 무게순으로 정렬한 보석을 해당 가방에 들어갈 수 있는지 비교하고 들어갈 수 있다면 해당 보석을 PQ에 넣는다.3. 한 가방에 다 넣었으면 PQ에서 보석을 꺼내어 해당 보석의 가격을 정답에 더한다. ⭕정답 코드import java.io.BufferedReader;impo..
https://www.acmicpc.net/problem/9202알고리즘 분류 : 자료 구조, 그래프 이론, 문자열, 브루트포스 알고리즘, 그래프 탐색, 트리, 깊이 우선 탐색, 백트래킹, 트라이❓문제🔅해석Trie 알고리즘을 활용하여 문제를 해결한다. 먼저, 입력받은 단어들로 Trie를 생성한다."ACM'을 입력받았다면 아래와 같이 Trie 객체가 생성된다. for문을 순회하여 Trie 객체인 root를 완성하면 뒤에 N개의 맵을 입력받아 탐색한다. dfs를 작성할 때는 아래 6단계를 거쳐 작성하는 것을 추천한다. 1. 체크인visited 배열에 true 를 입력하고 현재 map 좌표에 있는 알파벳 하나를 Stringbuilder에 붙인다. 2. 목적지인가목적지의 기준은 1) 현재 노드가 단어이면서, ..
https://www.acmicpc.net/problem/2243알고리즘 분류 : 자료 구조, 세그먼트 트리, 이분 탐색 ❓문제🔅해석 세그먼트 트리에서 구간의 정보를 조회하는 query는 총 다섯가지 정보를 넘긴다.query(int left, int right, int node, int queryLeft, int queryRight) 현재 문제에서는 해당 순위의 정보만 필요하므로 query(int left, int right, int node, int query) 으로 넘긴다. 문제의 입력을 보자면, 레벨 1 사탕 2개, 레벨 3 사탕 3개가 존재하고 여기서 2번째로 맛있는 사탕을 꺼내준다고 할 때, 답은 레벨 1이다. 위 그림을 볼 때, 노드를 탐색하면서 해당 노드의 값이 B보다 크거나 같을 때 왼쪽..
