semtax의 개발 일지

도형 내부에 포함된 점을 찾는 알고리즘에 대한 내용입니다.

개인 프로젝트를 수행하면서, 위치정보(위도, 경도) 가 포함된 데이터를 빠르게 검색해야 할 일이 있어서 정리한 내용을 올려봅니다. 참고바랍니다.

개요 이번 포스팅에서는, 자료 구조에서 그래프를 모델링 하는 방법들에 대해서 알아보도록 하겠습니다. 그래프? 그래프는 정점(Vertex) 와 간선(Edge)로 이루어진 자료 구조 입니다. 보통 수학적으로는 아래와 같이 표기하게 됩니다. G = (V, E) V = {A, B, C} E = {(A,B),(B,C),(A,C)} 즉, 위의 설명을 그림으로 나타내면 아래와 같습니다. graph TD A[A] --- B[B] B[B] --- C[C] A[A] --- C[C] 보통 위와 같은 형태의 자료구조를 그래프 라고 부릅니다. 또한 그래프의 종류에는 방향 그래프와, 무방향 그래프 2종류가 존재합니다. 방향 그래프는 A -> C, C -> A 와 같이 서로 방향이 존재하는 그래프를 가리킵니다. 무방향 그래프는 반..

개요 이번 시간에는 백 트래킹 알고리즘에 대해서 알아보도록 하겠습니다. 또한, 백 트래킹 알고리즘을 이용해서 스도쿠 퍼즐을 만드는 프로그램을 작성 해보도록 하겠습니다. 백 트래킹(Back Tracking)? 백 트래킹(Back Tracking)은 단어 뜻 그대로, 되 추적이라는 다시 되돌아가서 되돌아간 자리에서 시작한다는 말입니다. 어릴 적에 "경우의 수" 문제나, "확률과 통계" 문제를 풀 때를 떠올려 봅시다. 문제를 맨 처음 풀 때, 우리는 종이에 수형도 라고 부르는 나뭇가지를 처음부터 하나씩 그려서 갯수를 전부 세었습니다. 아니면, 길 찾기 문제를 풀 때 에도, 종이에 거의 모든 경우의 수를 그려서 직접 세서 풀었던 것을 기억 하실겁니다. 사실은 모든 경우의 수를 전부 세서 그렸다고 생각을 하고는 ..

개요 이번 포스팅에서는 온라인 알고리즘을 이용해서 평균값을 구하는 법에 대해서 다루어 보도록 하겠다. 온라인 알고리즘 보통 알고리즘을 이용해서 어떠한 문제를 풀때에는, 보통 문제를 풀때 필요한 데이터를 전부 들고 있어야 한다. 예를 들어서, 100만 개의 데이터를 퀵소트를 이용해서 정렬한다고 가정하면, 메모리에 100만개의 데이터를 미리 가지고 있어야 정렬이 가능하다. 위에서 언급한 이러한 알고리즘을 보통 오프라인 알고리즘(off-line algorithm) 이라고 한다. 하지만, 실제 서비스를 만드는 경우 데이터가 언제/얼마나 들어올지도 모르는 데다가 설사 예측을 한다고 하더라도 데이터의 크기가 너무 커서 메모리에 한번에 다 못올리는 경우가 생긴다. 이러한 경우, 모든 데이터를 들고 있지 않아도 알고리..