선형 시간에 힙 만들기 Building Heap in Linear Time 힙을 만드는 방법 힙을 만들기 위해서 heapify라는 연산을 정의하겠다. heapify(x): 노드 x의 왼쪽, 오른쪽 자식을 루트로 서브트리가 각각 힙일 때 노드 x를 루트로 하는 서브트리를 힙으로 만든다. 이 연산을 bottom-up으로 모든 노드에 대해서 수행해 주면 해당 트리는 힙이 된다. Heapify의 시간 복잡도 heapify는 다음과 같은 알고리즘으로 수행할 수 있다. 노드 x의 자식이 없다면 이미 힙이므로 종료한다. 그게 아니라면(자식이 있다면) 자식 중 값이 더 큰 노드를 찾는다. 해당 노드의 값이 노드 x의 값보다 작다면 이미 힙이므로 종료한다. 그게 아니라면(1번에서 찾은 노드의 값이 노드 x의 값보다 크다면) 해당 노드와 노드 x를 swap한다. 1번으로 돌아간다. 이 알고리즘은.. 2021. 5. 14. 오로지 PS만을 위한 Sprague-Grundy Theorem(스프라그-그런디 정리) PS를 하다 보면 Combinatorial Game Theory(조합론적 게임 이론) 분야가 있다. 이번 방학 동안 참가한 알고리즘 캠프에서 알게 된 분야인데, 내용이 상당히 어려웠고 다른 사람들도 어렵게 느낄 것이라는 생각이 들었다. 이 분야를 이해하기 위해 열심히 발버둥친 결과, 증명 등은 배제하고 몇 가지 핵심만 안다면 많은 사람들이 충분히 이 분야의 문제들에 도전해볼 수 있을 것이라는 생각을 했다. 따라서 이 글은 엄밀하게 Combinatorial Game Theory를 공부해 보자는 글은 아니며 오로지 PS만을 위한 응용을 목적으로 하는 글이다. 이어지는 내용에서 결론만 이야기하고 넘어가는 부분들이 많은데 이 글의 목적을 위해서 그렇게 서술한 것이니 관심이 있는 사람들은 마지막에 달아 놓은 링크.. 2021. 3. 2. 이전 1 다음
