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. 백트래킹Go as deep as possible, backtrack if impossible 모든 조합을 시도해서 문제의 해를 찾는 알고리즘이다.모든 가능성을 하나의 트리(상태 공간 트리)처럼 구성할 수 있으며, 가지 중에 정답이 있다.하지만 모든 경로를 찾는 것은 비효율적이기 때문에, 해답이 될 가능성이 있는 선택지만 타고 들어간다.즉, 완전 탐색(순열, 조합, 부분집합, BFS, DFS 등) + 가지 치기라고 생각하면 편하다.상태 공간 트리(State-Space Tree)문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리ex) 미로를 해결할 때 갈림길에 놓인 지점가지치기(pruning)가능성이 없는 노드가 포함되는 경로는 더 이상 고려하지 않는다.1. 적용 예시n-queenn*n 체스 보..
0. 이진 탐색(Binary Search)이진 탐색은 타겟(원하는 값)을 찾을 때까지 이진 탐색을 반복 수행하며 검색 범위를 반으로 줄여가면서 순차 탐색보다 빠르게 검색을 수행하는 알고리즘이다.단, 이진 탐색을 하기 위해서는 자료가 정렬된 상태여야 하는 제약이 존재한다. 분할 정복을 기반으로 하는 방식으로, 분할 정복을 알고 있다면 더욱 이해하기 쉽다.1. 이진 탐색의 로직자료의 중앙에 있는 원소를 고른다.중앙값(중앙 원소의 값)과 타겟을 비교한다.중앙값과 타겟이 일치하면 탐색을 끝낸다.타겟이 중앙값보다 작으면 자료의 왼쪽 반에 대해 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해 새로 검색을 수행한다.찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다아래 그림은 6을 찾는 이진 탐색의 그림이다...
