아래 글은 'Introduction to Algorithms(한빛아카데미)'와 위상 정렬 개념 및 구현를 보고 작성한 것이다. 대표 문제 백준 2252번: 줄 세우기 위상 정렬(Topological Sort) 위상 정렬을 알기 위해서는 먼저 '방향 비순환 그래프(DAG)'에 대해 알고있어야 한다. 방향 비순환 그래프(Directed Acyclic Graph): DAG는 말 그대로, 사이클이 없는 방향 그래프이다. DAG는 보통 이벤트/객체 간의 우선순위를 나타내기 위해 사용된다. DAG인 그래프 G = (V, E)의 위상 정렬은 G가 간선 (u, v)를 가질 때, u가 v보다 순서상으로 먼저 나타나도록 모든 노드를 선형으로 나열하는 것이다. 즉, 우선순위에 따라 배열을 정렬하는 것이다. 따라서 우선순위 ..
아래 글은 'Introduction to Algorithms(한빛아카데미)'와 분할 정복 블로그 를 보고 정리한 것이다. 대표 문제 백준 6549번: 히스토그램에서 가장 큰 직사각형 분할 정복 분할 정복(Divide and Conquer)은 (1) 분할과 (2) 정복, (3) 결합의 세 가지 단계를 거치면서 재귀적으로 문제를 해결한다. 분할: 현재의 문제와 동일하되 입력의 크기가 크기, 또는 문제의 크기를 더 작은 부분 문제로 분할한다. 정복: 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다. 결합: 부분 문제의 해를 결합해 원래 문제의 해가 되도록 만든다. 부분 문제가 재귀적으로 풀 수 있을 만큼 충분히 클 때, 재귀 대상이라고 한다. 부분 문제가 충분..
아래 글은 'Do it! 자료구조와 함께 배우는 알고리즘 입문(파이썬 편)'을 보고 정리한 것이다. 힙(Heap) 힙이란, 아래의 조건을 만족하는 완전 이진 트리이다. 힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다. 따라서 힙은 형제의 대소 관계가 정해져있지 않으므로 부분 순서 트리(partial ordered tree)라고도 한다. 부모의 값이 자식의 값보다 항상 크다/작다. 인덱스 i에 대해 부모와 자식 인덱스 사이에는 다음과 같은 관계가 성립한다. 부모: a[(i-1)//2] 자신: a[i] 왼쪽 자식: a[i*2 + 1] 오른쪽 자식: a[i*2+2] 힙 정렬(Heap Sort) 힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다. 힙에서 최댓값은 root에 위치한..
