-
knon0501's profile image
knon0501
November 24, 2025
Map Matching Algorithm
개요 Map Matching이란 Vehicle의 GPS 좌표 목록이 주어졌을 때 실제 도로상에서 어떠한 경로로 이동했는지를 복원하는 문제입니다. 다시 말해 입력으로 위경도 timeseries 데이터와 방향그래프로 구성된 도로 데이터가 주어졌을 때 도로상의 경로를 출력하는 문제입니다. 이 포스팅에서는 2009년 마이크로소프트 연구진에서 저술한 Hidden Markov Map Matching Through Noise and Sparseness 논문에서 제시하는 Map Matching 문제를 해결하는 알고리즘에 대해 설명하겠습니다. 맵매칭 문제의 어려움 맵매칭을 하는 가장 단순한 방법은 gps 좌표를 가장 가까운 도로로 매칭하는 것입니다. 그러나 gps 측정은 완벽하지 않고...
-
knon0501's profile image
knon0501
June 21, 2024
Kotlin 변성
이 포스트에서는 코틀린 제네릭의 주요 개념 중 하나인 변성에 대해 알아보겠습니다. 변성이란 List<String>와 List<Any>와 같이 기저 타입이 같고 타입 인자가 다른 여러 타입이 서로 어떤 관계가 있는지 설명하는 개념입니다. List<Any> 타입의 파라미터를 받는 함수에 List<String>을 넘기면 안전한지에 대한 질문을 생각해봅시다. 결론부터 말하면 안전합니다. 예를 들어 다음과 같은 코드는 정상적으로 컴파일됩니다, fun print(list: List<Any>){ println(list.joinToString()) } print(listOf("a","b","c")) 그러나 MutbleList의 경우는 그렇지 않습니다. fun add(list: MutableList<Any>) { list.add(42) } val strings = mutableListOf("a","b","c") add(strings) println(strings.maxBy{it.length}) 만약 이...
-
knon0501's profile image
knon0501
March 18, 2023
Knapsack Algorithm의 여러 응용
Introduction 배낭 문제란 무게제한이 있는 가방에 고유한 무게와 가치를 가지는 물건들을 채워넣을 때 어떻게 해야 최대 가치를 가방에 넣을 수 있을지 계산하는 문제입니다. 무게에 별다른 제한이 없을 경우 물건이 총 $N$개일 때 $O(2^N\times N)$정도의 시간복잡도로 계산할 수 있으며 NP-complete 임이 알려져 있습니다. 물건의 무게가 정수이고 가방의 무게제한이 $W$일 경우 동적계획법으로 $O(NW)$에 해결할 수 있습니다. 이 글에서는 독자가 동적계획법으로 배낭 문제를 해결하는 법을 이미 알고 있다고 전제하고 다양한 배낭문제의 응용들을 살펴보겠습니다. 각 물건을 여러개 사용할 수...
-
knon0501's profile image
knon0501
February 16, 2023
Dilworth's Theorem
Introduction 딜워스의 정리(Dilworth’s Theorem)는 부분 순서 집합(partially ordered set)에서 최대 반사슬(antichain)의 크기는 사슬 분할의 최소 개수와 같다는 정리입니다. 먼저 용어들을 설명하겠습니다. 부분 순서 집합이란 말 그대로 순서가 부분적으로 정의된 집합입니다. 예를 들어 자연수 집합 $S$에서 $x$가 $y$로 나누어 떨어질 때 $x\geq y$로 정의하는 경우 $S$를 부분 순서 집합이라고 생각할 수 있습니다. 여기서 6과 3은 비교 가능하지만 6과 5는 비교 불가능합니다. 다른 예시는 2차원 좌표를 원소로 하는 집합에서 $x_1\leq x_2,y_1\leq y_2$이면 $(x_1,y_1)\leq(x_2,y_2)$로 정의하는 것입니다. 여기서는 (1,5)와...