반응형 개발/알고리즘3 다각형 근사화 Douglas-Peucker 알고리즘 원리 (더글러스 피커 알고리 이번에는 이렇게 찾은 외곽선을 근사화 하는 알고리즘에 대해 알아보도록 하겠습니다.Ramer Douglas Peucker algorithm 또는 iterative end-point algorithm 이라고 불리는 DP 알고리즘은 line segment들로 이루어진 곡선이나 다각형을 근사화하는 알고리즘으로 많이 사용되는 알고리즘 입니다.컨셉이 간단하고 강력하기 때문에 꼭 알아두시면 좋은 알고리즘입니다.DP 알고리즘 원리다각형 또는 곡선은 여러개의 vertex로 이루어져 있습니다. 이 꼭지점들을 하나의 vector로 만들어 놓았다고 가정합니다. 일단 알고리즘을 다각형으로 설명을 드리면 곡선은 자연히 이해가 되실 거 같아 아래와 같은 다각형으로 설명드리겠습니다.1. 점들중 가장 멀리 떨어져있는 두 점을 찾고 두.. 2024. 5. 7. DFS, BFS 스터디용 DFS, BFS 정리 DFS, BFS는 그래프에 속하는 알고리즘이다. 코딩테스트에서 경로를 찾는 문제에서 많이 출제가 된다. DFS Root Node 혹은 다른 임의의 Node에서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. Stack 혹은 재귀함수(Recursion)으로 구현된다. 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행 모든 노드를 방문하는 경우에 이 방법을 사용한다. 시간 복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 접점(V), 간선(E) Java Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 .. 2021. 2. 5. 트라이(Trie)알고리즘 트라이(Trie) 트라이란 문자열 검색을 빠르게 할 수 있는 알고리즘이다. 예를 들어 영어사전이 있을 때 특정 단어가 있는 지 빠르게 찾을 수 있다. 문자열을 특정 키값으로 변환해서 그 값으로 찾는 방법인 해시 테이블을 대체하기 위해 트라이를 사용할 수 있다. 불완전한 해시 테이블의 최악의 검색속도는 모든 데이터를 다 확인하는 것으로 O(N)이지만 트라이를 사용하게 되면 문자열 길이 만큼의 O(M)의 속도가 걸리기 때문에 훨씬 더 빠르게 적용이 될 수 있다. 보통 트라이 알고리즘을 사용할 때 고려해야할 점이 단어의 길이, 그리고 파생되는 노드 child개수다. 위에 영어사전으로 예를 들었는데 영어는 알파벳이 26가지로 child 노드는 26개를 갖고 있을 수 있다. 전화번호 목록같은 경우도 0부터 9가지.. 2020. 4. 7. 이전 1 다음 반응형
