0. 위상 정렬(Topological Sort)위상 정렬은 유향 그래프의 정점들을 나열하는 것을 의미한다.순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘으로 위상 정렬의 결과는 여러 개일 수 있다.가장 잘 설명되는 예시로는 선수과목(prerequisite) 구조이다. 만약 특정 수강 과목에 선수 과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 수강 순서를 찾아낼 수 있다.위상 정렬이 성립하기 위해서는 그래프의 순환이 존재하지 않는 비순환 유향 그래프(directed acyclic pragh)여야 한다. 위상 정렬은 아래 2가지에 대한 판단이 가능하다.현재 그래프는 위상 정렬이 가능한지 → 사이클이 존재하지 않는지위상 ..

0. 병합 정렬병합 정렬은 O(NlogN)의 시간복잡도를 가진 정렬 알고리즘이다.가장 일반적인 O(N^2)인 삽입, 선택, 버블 정렬보다 빠르며,많이 쓰이는 퀵 소트보다 높은 안정성을 보여준다.퀵 소트는 평균적으로 O(NlogN)이지만 최악의 경우 O(N^2)이기 때문이다.(이 이유때문에 알고리즘 문제에선 절대 퀵소트를 써선 안된다...)자세한 건, 퀵 소트를 찾아보면 이해가 될 것이다.1. 알고리즘n의 길이를 가진 배열을 절반(m) 크기의 배열로 쪼갠다.쪼개진 배열의 길이가 2가 될 때까지 1번을 반복한다.쪼개진 두 배열을 [그림 1]과 같이 정렬한다.m 길이의 정렬된 배열을 통해 2 * m 길이의 배열도 정렬한다.2 * m이 n이 될때까지 4번을 반복한다. 2. 코드3. 참고https://www.yo..

0. 그래프그래프는 아이템과 이들 사이의 연결 관계를 표현하는 자료구조이다.그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조이다.정점(Vertex): 그래프의 구성요소로 하나의 연결점간선(Edge): 두 정점을 연결하는 선차수(Degree): 정점에 연결된 간선의 수인접(Adjacency): 두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.경로(Path): 어떤 정점에서 시작하여 다른 정점으로 끝나는 순회로 두 정점 사이를 잇는 간선들을 나열한 것싸이클(Cycle): 경로의 시작 정점과 끝 정점이 같음(시작한 정점에서 끝나는 경로)V개의 정점을 가지는 무향 그래프는 최대 V * (V-1) / 2개의 간선이 가능하다.선형 자료구조나 트리..

0. 백트래킹Go as deep as possible, backtrack if impossible 모든 조합을 시도해서 문제의 해를 찾는 알고리즘이다.모든 가능성을 하나의 트리(상태 공간 트리)처럼 구성할 수 있으며, 가지 중에 정답이 있다.하지만 모든 경로를 찾는 것은 비효율적이기 때문에, 해답이 될 가능성이 있는 선택지만 타고 들어간다.즉, 완전 탐색(순열, 조합, 부분집합, BFS, DFS 등) + 가지 치기라고 생각하면 편하다.상태 공간 트리(State-Space Tree)문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리ex) 미로를 해결할 때 갈림길에 놓인 지점가지치기(pruning)가능성이 없는 노드가 포함되는 경로는 더 이상 고려하지 않는다.1. 적용 예시n-queenn*n 체스 보..