지민 개발 블로그

쿼드 트리(QUADTREE)대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리란 것이 있다.주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 위해 쿼드 트리라는 이름이 붙었다. 가장 유명한 예시로 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현한 사례가 있다. 쿼드 트리는 2**n * 2**n크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축한다. 이 그림의 모든 픽셀이 검은 색일 경우 이그림의 쿼드 트리 압축 결과는 그림의 킉에 관계없이 b가 된다.이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계 없이 w가 된다.모든 픽셀이 강튼 색이 아니라면, 쿼드 트리는 이그림을 가로 세로로 각각 2등분해 4개의 조각으로 ..

1. 무식하게 풀기공부를 할수록 우아한 답안을 만들고 싶은 마음이 커진다. 그래서 바로 앞에 보이는 쉽고 간단하며 틀릴 가능성이 낮은 답안을 간과하기 쉽다. 이런 실수를 방지하기 위해서 '무식하게 풀 수 있을까?' 라는 생각을 해보아야한다. "brute-force(무식하게 푼다)"컴퓨터의 빠른 계산 능력을 이용해, 가능한 경우의 수를 일일이 나열하며 답을 찾는 방법을 의미한다.이런 알고리즘을 완전 탐색(exhaustive search)라고 한다.  2. 재귀 호출과 완전 탐색컴퓨터가 수행하는 많은 작업들은 대개 작은 조각으로 나눌 수 있다.범위가 작아지면 작아질 수록 각 조각의 형태들은 유사해진다.이러한 작업을 구현할 때 유용하게 재귀 함수(recursive function)/재귀 호출(recursion..

알고리즘의 정당성 증명 해결해야 할 문제가 간단할 때는 직관적으로 알고리즘을 설계할 수 있지만, 문제가 복잡해지면 알고리즘이 과연 문제를 제대로 해결하는지 파악하는 것이 힘들다. 물론 단위테스트를 통해서 해결할 수도 있겠지만, 이 방법으로는 턱없이 모자라다. 따라서, 알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 한다. 알고리즘에 대한 증명은, 알고리즘을 유도하는 데 결정적인 통찰을 담고 있다. 모든 알고리즘은 치열한 고민과 개선 과정을 거쳐 태어나고 이 과정에서 결정적으로 필요한 깨달음이 증명에 담겨있는 경우가 많다. 또한, 증명을 아는 편이 사용하는 입장에서도 큰 공부가 된다. 1. 반복문 불변식 귀납법은 알고리즘의 정당성을 증명할 때 가장 유용하게 사용되는 기법이다. 대부분의 알..