minkylee

개념다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘이다. 드론이나 로봇 차량의 인공지능을 위해 개발되었다.  A* 알고리즘은 현재 상태의 비용을 $ g(x) $  현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 $ h(x) $ 라고 할 때, 둘을 더한$ f(x) = g(x) + h(x) $ 가 최소가 되는 지점을 우선적으로 탐색하는 방법이다.  $ f(x) $ 가 작은 값부터 탐색하는 특성상 우선순위 큐가 사용된다.  휴리스틱 함수 $ h(x) $ 에 따라 성능이 극명하게 갈리며, $ f(x) = g(x) $ 일 때는 다익스트라 알고리즘과 동일하다.  다익스트라 : 가중치 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 그리디 알고리즘A* : 가중치 그래프, 시작 노드에서 ..

그리디 알고리즘 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자. 예를 들어 5개의 도시를 모두 한 번씩만 거쳐서 여행한다고 가정하자, 기름값을 아끼기 위해 가장 짧은 경로를 선택해야한다고 하면, 이 문제를 해결하기 위해 여러 방법을 사용할 수 있다. 모든 경로를 검사하는 브루트 포스를 이용해 답을 구하거나, 외판원 순회같은 복잡한 전략을 쓸 수도 있고 " 지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다 " 는 방법, 즉 그리디 알고리즘을 쓸 수도 있다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 전혀 없다. 그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될..

행렬 곱셈 정사각 행렬 A, B를 가지고 곱셈을 한다고 생각해보자. 행렬곱 C = AB는 다음과 함께 정의된다. 이 때 i = 1, ... ,m, j = 1, ..., p에 대해 C의 성분은 다음과 같이 정의된다. 이는 곧 A의 i번째 행과 B의 j번째 열의 성분들을 각각 곱해 더한 것과 같은데, A의 i번째 행과 B의 j번째 열의 스칼라곱인 것이다. 그런고로 AB는 다음과 같이 쓸 수도 있다. 3중 반복문이 행렬의 크기 n만큼 돌기 때문에 n x n 크기의 두 행렬을 곱하면 O(n^3) 의 시간이 소요된다. 줄이는 방법이 없을까? Strassen algorithm (슈트라센 알고리즘) 행렬의 덧셈이 곱셈보다 더 빠른 점을 이용하기 위해 쪼갠 행렬들의 곱셈 횟수를 줄이고 덧셈 횟수를 늘린다. 곱셈은 $ ..

d-차원 안의 n개의 점이 주어질 때 서로 거리가 가장 짧은 두 점을 구하는 문제이다. 많은 응용 프로그램의 근본적인 문제이며 많은 알고리즘의 핵심 단계이다. 1-Dimension Problem 정렬을 통해 O(nlogn)의 시간 복잡도로 풀이가 가능하다. 그러나 정렬하는 것은 더 높은 차원일 때 문제를 풀 수 없다. 1D를 통한 분할과 정복을 개발해보자 모든 p ∈ S1, q ∈ S2에 대해 p < q가 되도록 점 S를 두 세트로 나눈다. S1에서 가장 가까운 쌍 (p1, p2)를 재귀적으로 계산하고 S2에서 (q1, q2) 를 계산한다. 그리고 S1에서 한개의 점, S2에서 한개의 점을 사용하여 중간영역까지 고려해준다. (p3, q3) δ이지금까지 발견된 가장 가까운 쌍이라고 했을 때 δ = min(..

분할 정복이란? 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음, 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합 정렬이 있다. 그림에서와 같이 분할 정복은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합하는 형태로 도식화 할 수 있다. 분할 : 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. 정복 : 가장 작은 단위의 하위 문제를 해결하여 정복한다. 조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다. 마스터 정리 점화식을 해결하기 위한 일반적인 방법 중 하나로, 분할 정복 알고리즘에서 주로 사용된다. 점화식이 특정한 ..

알고리즘이란? 컴퓨터 프로그램 특정 작업 (ex. 정렬)을 해결하는 개별 모듈로 구성된다. 문제를 해결하기 위한 절차나 방법, 더 정확한 정의로는 모든 입력값에 대해 튜링머신이 정지하게 하는 명령 표현 방법 implementation 슈도 코드 (pseudo code) Natural Language(영어, 한국어) 알고리즘 이름, Input, Outpu, 방법이 나오도록 명시 용어 정리 Correctness : 맞는 답을 찾아가는 과정 ex. n개의 도시가 있고 도시간의 거리가 포함되어 있을 때 모든 도시를 방문하고 다시 내 도시로 돌아왔을 때 이동한 거리가 최소가 되는 값을 구해라 맞는 접근법을 찾아보자! 가장 가까운 도시부터 접근해서 돌아오기 모든 방법을 검사해서 최소값을 찾기 이런식으로 맞는 답을 ..

Searching list : 하나 이상의 필드로 된 레코드의 집합 키 (key) : 레코드를 구분하기 위해서 사용되는 필드 순차 탐색(Sequential Search) 레코드 리스트를 왼편에서 오른편 또는 오른편에서 왼편으로 레코드를 검사하는 것 int SeqSearch(int a[], const int n, const int key) { for (int i = 1; i n) return 0; return i; } 이원 탐색 (Binary Search) n개의 레코드를 가진 리스트를 탐색하기 위해 O(logn) 시간이 걸림 (순차탐색보다 빠르다.) 순차나 이원 탐색 방법은 실제로 사람이 사용하는 탐색 방법과 대응되지 않는다. 보간법(interpolation)에 의한 탐색 리스트가 정렬되었을 때만 사용 ..

어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾는다. 각 도시를 한 번씩 방문한다고 했을 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까? 만약 도시가 20개라고 할 때, 이 문제의 정답을 찾기 위해 다녀야 하는 총 경로의 수는 20!이다. 20!=2,432,902,008,176,640,000 이기 때문에 시간복잡도가 어마무시하다... 정의 주어진 완전 그래프 G=(v, E)가 연결되어 있고, 가중치가 있는 완전한 그래프라고 가정하자. 이 그래프에서 출발 정점에서 다른 모든 정점들을..