알고리즘/개념

# 위상 정렬이란? 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘 선후 관계가 정의된 그래프 위상 정렬이 성립하기 위해서는 방향 비순환 그래프이어야 한다. # 흐름 0. 모든 정점의 진입 차수를 계산한다. 진입 차수(in-degree) : 자신으로 들어오는 간선의 수 1. 진입 차수가 0인 정점을 모두 큐에 넣는다. 진입 차수가 0인 정점 = 시작점 위 경우에서는 A, E가 큐에 들어가게 된다. 2. 큐에서 정점을 꺼내어 해당 정점과 인접한 정점의 간선을 제거하고 인접한 정점의 진입 차수를 1 감소시킨다. 인접한 정점의 진입 차수가 1 감소 이후 0이 된다면 인접한 정점을 큐에 넣어준다. 큐가 빈 상태가 될 때까지 반복한다. # 관련 문제 (2252 - 줄 세우기 ..

# 최소 공통 조상 (LCA) 정점 A와 정점 B가 각각 자신을 포함하여 초상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점 구하기 처음 아이디어 = 정점의 부모를 따라 1칸씩 올라가자 시간 복잡도 = O(N) => 어떻게 더 빠르게 찾을 수 있을까? 1칸씩 올라가는 것이 아닌 2^K씩 올라가자 => 시간 복잡도 = O(logN) 이때 다른 수도 아닌 2^K인 이유는??? 모든 수는 이진수로 나타낼 수 있기 때문에 parent[0][V] = 정점 V의 1(=2^0)번째 부모 parent[1][V] = 정점 V의 2(=2^1)번째 부모 ★ = 정점 V의 1번째 부모의 1번째 부모 ★ => parent[1][V] = parent[0][ parent[0][V] ] ★★ parent[K][V] = p..

# 플로이드-워셜 알고리즘 모든 정점 사이의 최단 경로를 구하는 알고리즘 순환만 없다면 음수 가중치도 가능 동적계획법으로 접근 dist[i][j] = Math.min( ~ , ~ ) 형태를 가짐 N개의 정점을 가진다고 할 때, 모든 정점으로 가는 최단 거리를 확인하므로 시간복잡도 = O(N^3) N이 200~300 이하인 경우에만 가능 # 코드 1. INF 값으로 세팅 public static final int INF = 1_000_000_000; INF 값을 Integer.MAX_VALUE로 설정하는 경우, 연산 과정에서 overflow 발생하는 문제 종종 있음 => 잘 확인해서 INF 값 적당히 크게 설정하기 for(int i=1;i

# 구간 합 구간 합 : i ~ j 인덱스 값들의 합 => 특정 구간 인덱스의 합 부분 합 : 0 ~ k 인덱스 값들의 합 => 처음부터 특정 인덱스까지의 합 시간 복잡도 반복문을 통해 i ~ j 인덱스 값들의 합을 구하는 경우) O(N) (i=0, j=N) 시간 복잡도를 줄이기 위해서는 합 배열을 이용해야 함 => O(1)으로 감소 # 합 배열 합 배열 S, 배열 A S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] 합 배열 : 기존의 배열을 전처리한 배열합 배열 만드는 공식 S[i] = S[i-1] + A[i] 합 배열을 이용해 구간 합 구하는 공식 S[j] - S[i-1] # 관련 문제 [JAVA] 백준 q11659 - 구간 합 구하기 4 11659번: 구간 합 ..