조대협의 블로그

튜토리얼 포인트자료 구조에 대한 설명과 코드들을 간략하게 잘 정리해 놓음http://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm 코세라 프린스턴 알고리즘 강의https://class.coursera.org/algs4partI-010 코세라 데이타 구조에 대한 강의 (그래프 구조에 대한 문제가 잘 정리되어 있음)https://class.coursera.org/algs4partI-010 알고리즘에 대한 일반적인 설명 (Algorithm 4th edition)http://algs4.cs.princeton.edu/ Octree와 QuadTree에 대한 설명 (게임에서의 응용)http://www.gamedev.net/page/r..

동적 연결 알고리즘 (Dynamic Connectivity) 조대협 (http://bcho.tistory.com) 요즘 알고리즘이 대세라 기초를 다지는 차원에서 다시 알고리즘을 보고 있는데, 오늘은 동적 연결 알고리즘에 대해서 공부한 내용을 간략하게 정리해본다. 동적 연결 알고리즘은 노드끼리 연결이 되어 있는지를 찾는 알고리즘이다.각 도시간에 연결이 되어 있는지, SNS에서 친구끼리 서로 연결이 되어 있는지와 같은 연결성만을 판단한다. 예전에 이러한 문제를 그래프 형태의 자료구조를 이용해서 풀려고 했는데, 여기서 문제의 핵심은 노드 A와 B가 연결되었는지만 판단하면 된다. 즉 자료 구조상에서, 어떤 노드가 어떤 노드와 인접해 있는지등은 표시할 필요가 없다. 아래 그림을 보자, 아래 그림에서 1과 5는 연..