유혁스쿨

위상정렬 사이클이 없는 방향에서 노드 순서를 갖는 정렬 기능 특징 시간복잡도 (노드수: V, 엣지수: E) 노드간 순서 결정 사이클이 없어야 함 O(V+E) 항상 유일한 값으로 정렬되지 않음 사이클 존재시 노드간 순서를 명확하게 정의 불가 (위상정렬 적용 불가) 핵심 이론 인접리스트 , 진입차수배열 , 위상정렬배열 세가지를 구현한다. 1. 그래프를 인접리스트로 구현 2. 구현된 인접리스트의 진입차수를 계산하여 진입차수 배열에 저장 3. 진입차수배열에서 진입차수가 0인 노드 선택 4. 선택된 노드 위상정렬 배열에 저장 5. 저장된 노드가 가리키는 노드들의 진입차수를 -1 연산 후 저장(선택) 된 노드의 다음노드를 진입차수 배열에서 다시 선택 6. 3 ~ 5 과정을 반복하며 모든 노드가 정렬될 경우 종료 [..

유니온 파인드 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find연산으로 구성되어 있는 알고리즘 (엄밀히 말하면 그래프 영역이라고 보기에 약간 무리가 있으나 실제로 그래프 문제에서 부분 알고리즘으로 많이 사용됨) find연산이란? 자신의 대표 노드를 찾아주는 연산 핵심이론 union, find 연산을 완벽히 이해하는 것 UNION : 각 노드가 속한 집합을 1개로 합치는 연산 → 노드 a, b가 a ∈ A, b ∈ B일 때 UNION(a,b) 는 A ∪ B를 말함 FIND : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산 → 노드 a가 a ∈ A일 때 find(a)는 A집합의 대표노드를 반환 (대..

그래프의 표현 그래프를 표현할때는 대표적으로 엣지리스트, 인접행렬, 인접리스트 3가지 방법으로 표현한다. 그래프 예 ① → ② → ⑤ ↓ ↓ ↗ ③ → ④ 엣지리스트 엣지를 중심으로 그래프를 표현한다. 배열에 출발,도착 노드를 각각 저장하여 엣지를 표현한다. 가중치가 있는 노드의 경우 배열에 가중치를 추가 행으로 함께 저장한다. 가중치 없는 그래프 표현 출발, 도착 2개의 노드만 2개의 배열행을 구성하여 표현한다. ex) 첫번째 행을 [1, 2]로 표현하며 1에서 2로 뻗어가는 엣지를 뜻한다. ⓢ ⓔ 1 2 1 3 3 4 2 4 2 5 4 5 이처럼 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다. 노드를 배열에 저장하여 엣지를 표현하므로 엣지리스트 라고 한다. 방향이 없는 그..

그래프 노드와 엣지로 구성된 집합. 예) 트리 노드 데이터 표현 단위 엣지 노드를 연결할 때 사용 그래프 알고리즘 종류 유니온 파인드 위상 정렬 다익스트라 벨만-포드 플로이드-워셜 최소 신장 트리 유니온 파인드 그래프의 `사이클 생성 유무`를 판단하는 알고리즘 그래프에서만 쓰이는 알고리즘은 아님 사용 예) `집합에서 대표 노드 탐색` 혹은 `각 원소들을 유니온 하여 하나의 집합으로 통합` ex) 3개의 노드와 2개의 엣지로 구성되었다고 가정했을 때 엣지를 추가할 경우 현재 그래프에 사이클이 생성되는가 → 유니온 파인드로 사이클 생성 여부를 도출한다. 위상 정렬 그래프의 각 노드들을 선형으로 정렬하는 알고리즘 알고리즘 사용 선 조건 사이클이 없어야 한다. 방향(간선)이 있는 그래프이다. ⓐ → ⓑ → ⓒ ..

유클리드 호제법 두 수의 최대 공약수를 구하는 알고리즘 일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현 할 수 있지만 유클리드 호제법은 조금 더 간단한 방법을 제시한다. 먼저 MOD 연산을 이해 → MOD 연산은 유클리드 호제법에서 최대 공약수를 구하는 핵심 이론 연산 기능 예제 MOD 두 값을 나눈 나머지를 구하는 연산 10 MOD 4 = 2 # 10 % 4 = 2 아래 3단계로 진행한다. 큰 수를 작은 수로 나누는 MOD 연산 수행 앞 단계에서의 작은 수와 MOD 연산 결괏값 (나머지)으로 MOD 연산을 수행 단계 2.를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택 GCD : Greatest Common Divisor로 최대 공약수의 줄..

서로소란? 공약수가 1외에 없는 수를 뜻함 공약수란? 둘 이상의 정수에서 공통된 약수를 뜻함 공약수와 연관지어 설명하자면 서로소란 둘 이상의 정수에서 공통된 약수중 공약수가 1 외에 없는 수를 말한다. ex) 28과 45은 서로소이다. => 공약수가 1밖에 없기 때문 (두 수는 공통분모, 연관성이 1외에는 없다) 오일러 피(phi) 오일러 피 함수 P[N]의 정의는 1부터 N 까지 범위에서 N과 서로소인 자연수의 갯수를 뜻한다. ex) P[6] = 1~6 범위에서 6과 서로소인 자연수의 갯수 {1, 2, 3, 4, 5, 6} => {1, 5} 2개 에라토스테네스 - 체 이론과 비슷하다. 구하고자 하는 오일러 피의 범위 만큼 배열을 자기 자신 인덱스값으로 초기화 2부터 시작해 현재 배열의 값과 인덱스가 같..