NAN-NOO

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 시간 복잡도는 O(V + E)다. 항상 유일한 값으로 정렬되지 않는다. 진입 차수 자기 자신을 가리키는 엣지의 개수를 말한다. 주어진 그래프를 인접 리스트로 구현하면서 동시에 진입 차수 배열을 초기화한다. 정렬 과정 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고, 선택한 노드를 위상 정렬 배열에 저장한다. 인접 리스트에서 선택한 노드와 연결된 노드들의 진입 차수를 1씩 감소시킨다. 위 과정을 반복한다. 이미 선택한 노드는 선택하지 않는다. 위상 정렬 배열의 길이가 노드 개수와 같다면 정렬이 끝난 것이다.

🔰 개념 그래프에 사이클이 생성되는지 판별하는 알고리즘이다. union 연산 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 연산이다. 노드 a, b가 각각 A, B 집합에 속 때, union(a, b) = A ∪ B 다. find 연산 두 노드가 같은 집합에 속해 있는지를 확인하는 연산이다. 자신의 대표 노드를 찾아준다. 노드 a가 집합 A에 속할 때, find(a)는 A 집합의 대표 노드를 반환한다. 단순히 대표 노드를 찾는 역할만 하는 것이 아니라, 그래프를 정돈하고 시간 복잡도를 향상시킨다. 🔰원리 초기화: 일반적으로 대표 노드를 저장하는 1차원 배열을 이용한다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 모두 대표 노드다. 따라서 배열을 자신의 인덱스값으로 초기화한다..

노드와 엣지로 구성된 집합이다. G = (V, E) V = a set of vertices(=nodes, points) E ⊆ {(x, y)| x, y ∈ V and x ≠ y} 트리도 그래프의 일부다. 🔰관련 알고리즘 유니온 파인드 그래프의 사이클이 생성되는지 판별하는 알고리즘이다. 위상 정렬 cycle이 없고 방향이 있는 그래프일 때 사용한다. 그래프 노드를 선형으로 정렬하는 알고리즘이다. 결과가 유일하게 나오지 않는다. 수강신청, 게임 빌드 순서와 같이 전후관계가 명확한, 순서(방향)가 정해져 있을 때 유용하다. 다익스트라, 벨만-포드, 플로이드-워셀 최단거리를 구하는 알고리즘이다. 다익스트라는 시작 노드부터 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘이다. 단, 간선의 가중치가 음수면 안 ..

현재 선택지 중 최선의 선택지를 선택하는 것이 전체 문제에서 최선의 선택지라고 가정하는 알고리즘 최적해를 보장하지 않음 🔰그리디 알고리즘 과정 아래 세 과정을 반복하여 문제를 해결한다. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 적절성 검사: 현재 선택한 해가 문제 제약 조건에 벗어나지 않는지 검사한다. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 첫 단계로 돌아가 반복한다.

데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘이다. 데이터의 중앙값과 찾고자 하는 값을 비교해 절반씩 탐색하며 대상을 찾는다. 시간 복잡도는 O(logN)이다. 🔰이분 탐색 과정 오름차순으로 정렬된 데이터가 있다고 가정하자. 현재 데이터셋의 중앙값을 선택한다. 중앙값이 타겟보다 클 때, 중앙값 기준으로 왼쪽 데이터셋을 선택한다. 작을 때는 오른쪽 데이터셋을 선택한다. 위 과정을 반복하다가 중앙값과 타겟 데이터의 값이 같으면 탐색을 종료한다.

DFS와 BFS는 모두 그래프 완전 탐색 기법이다. 🔰DFS(Depth First Search) 시작 노드에서 출발하여 매번 한 쪽 분기를 선택하여 최대 깊이까지 탐색을 마치고 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 재귀 함수로 구현하거나, 스택 자료구조를 이용한다. 재귀 함수를 이용할 시 스택 오버플로를 주의하자. 시간 복잡도는 O(V + E)다(V: 노드의 수, E: 엣지의 수). DFS 응용 문제에는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다. DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로, 방문 여부를 확인할 배열이 필요하다. 인접 리스트로 표현된 그래프가 있다고 했을 때, 스택과 방문 여부를 확인하는 배열을 이용해서 DFS를 구현할 수 있다. ..

🔰자료구조 스택 한 쪽 끝에서만 데이터를 넣거나(push) 꺼내는(pop) LIFO 자료구조다. DFS, 백트래킹 종류의 문제에 효과적이다. 🍎 파이썬에선 리스트와 append, pop 메서드로 스택을 구현한다. 큐 한 쪽 끝에서는 데이터를 넣고(enqueue), 다른 한 쪽에서는 데이터를 꺼내는(dequeue) FIFO 자료구조다. BFS 문제에 자주 사용한다. 🍎 파이썬에선 리스트와 deque을 이용하여 큐를 구현한다. 일반 리스트를 사용하는 것보다 deque를 사용하는 것이 삽입 및 삭제 성능 면에서 좋다. deque을 사용하면 append와 popleft로 enqueue와 dequeue를 구현한다. 우선순위 큐 큐나 스택과 비슷하지만, 각각의 요소가 우선순위를 가지고 있어 우선순위대로 처리된다. ..

합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘 배열의 데이터 변경이 적을 때 활용 -> 많을 땐? index tree 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 함 합 배열 S S[i] = A[0] + A[1] + ... + A[i - 1] + A[i] S[i] = S[i - 1] + A[i] 합 배열을 구해 놓으면 기존 배열의 일정 구간 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감 구간 합 공식(인덱스 i에서 j까지 합) S[j] - S[i - 1]

🔰자료구조 배열 연속된 메모리 공간에 데이터를 저장하고 있는 자료구조다. 인덱스로 값에 바로 접근할 수 있다(O(1)). 첫번째 값의 메모리 주소를 기준으로 메모리 주소를 계산한다. 새로운 값 삽입, 또는 기존값 삭제가 어렵다. 기존 배열에 있는 값들을 이동시켜야 한다. 배열의 크기는 선언할 때 지정하고, 선언 후에 크기를 변경할 수 없다. 리스트(linked list) 데이터를 저장하고 있는 각 노드가 포인터로 연결되어 있는 자료구조다. 인덱스가 없으므로 값에 접근하려면 O(n)의 시간복잡도를 가진다. 새로운 값 삽입, 또는 기존값 삭제가 빠르다(O(1)). 포인터로 노드를 연결하면 된다. dynamic list라고도 불리며, 선언 후에도 크기를 변경할 수 있다. 🍎 파이썬에서는 배열과 리스트를 구분하..

🔰기본 개념 n: input size c_op: execution time for basic operation C(n): number of times basic operation is executed T(n): running time ≒ c_op * C(n) O(g(n)): worst(upper bound). The set of all functions with a lower or same order of growth as g(n) T(n) ≤ c_op * g(n) n^3 ∉ O(n^2) Ω(g(n)): best(lower bound). The set of all functions with a higher or same order of growth as g(n) T(n) ≥ c_op * g(n) n^3 ..