- 정의- 그래프에서 최단 거리를 구하는 알고리즘- 특징- 모든 노드간 최단 경로 탐색을 한다- 음수 가중치 Edge가 있어도 수행이 가능하다- 동적 계획법의 원리를 이용해 알고리즘에 접근한읻- 시간 복잡도는 O(V^3)로 노드의 갯수가 많아질수록 매우 느리다- 따라서 노드의 갯수가 적은 문제에 적합(?)- 핵심 이론- A노드에서 B노드까지 최단 경로를 구했다 가정했을 때, 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다- - ex) 최단 경로가 파란색 선으로 되어있을 때 1~4까지 가는 최단 경로는 1->3->4로 최단경로가 1->2->4처럼 다른 방법으로 가는것이 될 수 없다점화식 D\[S\]\[E\] = Math.min(D\[S\]\[E\], D\[S\]\[..

정의최단거리를 구하는 알고리즘특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색한다음수 갖우치가 에지에 있어도 수행할 수 있다전체 그래프에서 음수 사이클 존재여부를 판단할 수 있다시간 복잡도는 O(VE)핵심 이론에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화 하기에지를 중심으로 동작하므로 에지 리스트로 구현한다출발 노드는 0, 나머지는 무한대로 초기화 해준모든 에지를 확인해 정답 리스트 업데이트하기업데이트 반복 회수는 노드 개수 -1로 노드 개수가 N개이고 음수 사이클이 없을 경우 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수가 N-1이기 때문이다모든 에지 E =(s,e,w)에서 다음 조건을 만족하면 업데이트를 실행한다D[s] != INF && D[e] > D[s] + w..

정의그래프에서 최단거리를 구하는 알고리즘특징출발 노드와 모든 노드간의 최단 거리를 탐색한다에지는 모두 양수이다시간 복잡도는 O(ElogV)이다(V:노드 수, E:에지 수)핵심이론그래프를 인접 리스트로 구현해 줄것인데, 그래프의 연결을 표현하기 위해 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 만들어준다(시간복잡도 측면, N의 크기가 클것에 대비하여 인접 행렬보다 인접 리스트가 유리하다) 최단거리 배열을 반들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화하는데, 이때 무한은 적당히 큰 값으로 사용하면 된다최단거리 배열에서 현재 값이 가장 작은 노드를 고르는데 값이 0인 출발 노드에서 시작한다선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트 한다처음에 저장해 둔 ..

정의 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 항상 유일한 값으로 정렬되지 않는다 시간 복잡도는 O(V+E)이다 (노드수 V, 에지 수 E) 핵심 이론 진입차수는 자기 자신을 가르키는 에지의 갯수로, 그래프를 인접 리스트로 구현한 뒤, 실시간으로 진입 차수 배열을 초기화해준다 진입 차수가 0인 노드를 선택 후 정렬 배열에 저장한 뒤, 인접리스트에 연결된 값의 진입 차수를 1씩 빼준다 선택한 노드를 제외한 노드 중 진입 차수가 0인 노드를 다시 선택해준 뒤 위의 작업을 반복해준다 이때 2,3번 노드의 값이 둘다 0이므로 어떤것이 먼저 배열에 들어가도 상관이 없으므로 항상 유일 값으로 정렬되지 않는것을 볼 수 있다 모든 배열이 정렬되면 위와같은 결과를 볼 수 있다

그래프 영역은 아니지만 그래프 문제에서 부분으로 사용하는 경우가 있다 정의 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해있는지를 찾는 find연산으로 구성되어있다 find연산은 자신의 대표 노드를 찾아주는 연산이다 핵심이론 union 연산 두 노드가 속한 집합을 1개로 합치는 연산으로 합집합을 생각하면 된다 find 연산 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산으로 노드 a ∊ A 일때 find(a)는 A집합의 대표 노드를 반한다 원리 이해하기 일반적으로 1차원 배열을 사용하며, 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표노드가 되고, 각 노드 모두 대표노드 이므로 배열은 자신의 인덱스 값으로 초기화한..

에지 리스트 에지를 중심으로 그래프를 표현한다 가중치가 없는 그래프 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다 방향이 있지 않으면 [1,2]와 [2,1]은 같은 표현이다 가중치가 있는 그래프 행을 3개로 늘려 3번째 행에 가중치를 저장하면 된다 특정 노드와 관련되어 있는 에지를 탐색하기에는 쉽지 않아 노드를 기으로 탐색하는 알고리즘엔 부적합하며, 에지 기준으로 탐색하는 벨만 포드, 크루스칼 알고리즘에 사용된다 인접행렬로 가중치가 없는 그래프 인덱스를 기준으로 시작 노드와 도착 노드를 판단한다 에지의 인접 행렬은 1행 2열에 저장하는 1을 저장하는 방식으로 표현한다 인접행렬로 가중치가 있는 그래프 가중치가 없는 그래프와 같이 표현하나 1을 저장하는 것이 아닌 가중치를 저장한다 두 노드..

핵심 용어 노드와 에지로 구성된 집합이다 노드는 데이터를 표현하는 단위이고 에지는 노드를 연결한다 종류 유니온 파인드 그래프의 사이클이 생성되는지 판별하는 알고리즘 위상정렬 사이클이 없는, 방향이 있는 그래프를 선형으로 정렬하는 알고리즘 값이 유일하지 않다는 특징이 있다 다익스트라 시작점이 존재하며 시작점에서 다른 모든 노드를 통과하는 최단거리 알고리즘이다(음수간선이 존재하면 안된다) 벨만포드 다익스트라와 같으나 음수간선이 존재해도 되는 최단거리 알고리즘이다 음수 싸이클이 있는지 확인하는 문제로도 많이 나온다 플로이드 워셜 모든 노드에 대해서 최단거리를 구하는 알고리즘으로 다익스트라와 벨만포드에 비해 시간복잡도가 안좋다 최소 신장 트리 모든 노드를 연결하는데 간선의 가중치를 최소로 구하는 알고리즘 트리는..

정의 두 수의 최대 공약수를 구하는 알고리즘 재귀를 활용할 수도 있다 핵심이론 MOD연산은 최대 공약수를 구할 때 이용할 키이다 MOD연산은 두 값을 나눈 나머지를 구하는 연산이다 먼저 큰 수를 작은 수로 나누는 MOD연산을 수행한다 앞 단계에서 작은 수와 MOD 연산 결과값으로 MOD 연산을 수행한다 두번째 단계를 반복하여 나머지가 0이 되는 순간 작은 수를 최대 공약수로 선택한다 이해하기

정의 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소(공약수가 1이외에 없는 수)인 자연수의 갯수를 구하는 알고리즘 핵심이론 원리는 에라토스테네스의 체와 비슷하다 먼저 구하고자 하는 오일러 피의 범위만큼 배열을 자기 자신의 인덱스 값으로 초기화한다 2부터 시작해 현재 배열의 값과 인덱스가 같으면(= 소수이면) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐갯해 P[i] = P[i] - p[i]/K 연산을 수행한다 (i는 K의 배수) 배열의 끝까지 두번째 방법을 반복해 완성한다 이해하기 구하고자 하는 범위까지 배열을 생성 후 2를 선택한다 2의 모든 배수마다 P[i] = P[i] - P[i]/2 연산을 수행하여 값을 갱신한다 탐색을 진행하면서 N = ∫(N)인 곳 즉 ∫(N)이 소수인..