728x90 반응형 CS/알고리즘9 강한 연결 요소 (Strongly Connected Component) 강한 연결 요소 (Strongly Connected Component)는 SCC라고 불리는 알고리즘 입니다. 유향 그래프에서 특정 노드에서 다른 노드들을 걸쳐 다시 특정노드로 돌아올 수 있으면, 노드들이 강하게 연결되어 있다 라고 합니다. DFS를 배우셨다면, 조금 쉽게 이해하실 수 있을거 같습니다. ex) https://www.acmicpc.net/problem/26146 26146번: 즉흥 여행 (Easy) 1번 정점에서 출발하면 모든 정점을 방문할 수 있는 경로가 존재하지만, 2번 정점에서 출발하면 모든 정점을 방문할 수 있는 경로가 존재하지 않으므로, 답은 No가 된다. www.acmicpc.net 1에서 2를 걸쳐 3으로 갔다가 다시 1로 돌아올 수 있음, 1에서 4로 갔다가 다시 돌아올 수 있.. 2023. 1. 26. 백트래킹(Backtracking) 백트래킹(Backtracking)은 답을 찾아가는 도중, 정답이 아닐거 같으면 뒤로 돌아가서 다시 답을 찾아가는 과정을 통해 해답을 구하는 방식의 알고리즘입니다. DFS을 알고 있다면, 이해하기 쉽습니다. DFS : 1번 방문한 곳은 다시 방문하지 못한다. 백트래킹 : 1군데를 여러번 방문할 수 있다. ex) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import java.io.BufferedReader; import java.io.IO.. 2023. 1. 25. SPFA(Shortest Path First Algorithm) SPFA(Shortest Path First Algorithm) 알고리즘은 "음수 간선을 포함한 데이크스트라 알고리즘"으로 이해하면 편한 "벨만 포드 알고리즘"을 개선한 알고리즘 입니다. BFS - 데이크스트라 - 벨만포드(SPFA)로 학습을 진행하시면 편합니다. 벨만 포드는 "모든 간선에 대해 업데이트를 진행"하지만, SPFA는 "바뀐 정점과 연결된 간선에 대해서만 업데이트를 진행"합니다. 벨만포드를 학습하지 않고, SPFA를 학습하셔도 태그로 벨만포드가 들어간 문제를 대부분 해결하실 수 있습니다. ex) https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주.. 2023. 1. 24. Dijkstra - 데이크스트라(다익스트라) 데이크스트라(Dijkstra)는 BFS 알고리즘을 알고 있다면 조금 더 쉽게 이해할 수 있다. 시작 지점 부터 가고자하는 도착지점까지 최소한의 시간으로 도착할 수 있는 거리를 구하는 알고리즘이다. ex)https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 예제 입력은 1번에서 출발하여 5번까지 도착하는데 걸리는 최소 시간을 구하는 문제입니다. 1 -> 4 -> 5을 이동하게 된다면 1 + 3 = 4의 시간이 걸리게 .. 2023. 1. 22. 이전 1 2 3 다음 728x90 반응형
