Algorithm100 [그래프] 위상정렬 위상정렬 (Topological sort) 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬 그래프 안에서 사이클이 존재하는 경우엔, 위상정렬을 적용할 수 없다. 근데, 사이클이 존재한다는 뜻이 무슨 뜻일까? 위와 같은 그래프가 존재한다고 가정할 떄, A->B->C->A... 이런식으로 다시 돌아올 때를 사이클이 존재한다고 한다. 즉, 한 노드에서 다른 노드들을 거쳐 처음 노드로 돌아오는 경우, 사이클이 존재한다고 얘기할 수 있다. 위와 같은 그래프가 주어졌을 때, 어떤 노드를 먼저 우선적으로 방문해야 할까? 우선적으로, indegree 배열을 만들어서 각 노드의 indegree 개수를 확인해보자. ABCDEFG0301210 indegree가 0인 정점을 살펴보면 A.. 2024. 7. 29. [백준] Silver I. 절댓값 힙 https://www.acmicpc.net/problem/11286사용 알고리즘우선 순위 큐 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.PriorityQueue;public class Main { static int n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()).. 2024. 7. 23. [백준] Silver II. 생태학 https://www.acmicpc.net/problem/4358 사용 알고리즘맵문자열 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.HashMap;import java.util.List;import java.util.Map;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new .. 2024. 7. 22. [백준] Gold IV. 부분 합 https://www.acmicpc.net/problem/1806 사용 알고리즘투 포인터 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static int n, s; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTo.. 2024. 7. 21. 이전 1 2 3 4 5 6 ··· 25 다음
