-
A* 알고리즘
안녕하세요? 오늘은 A* 알고리즘에 대해 설명해보려 합니다. A* 알고리즘은 주어진 출발지에서, 목적지까지 가는 최단 경로를 찾아내기 위해 고안된 알고리즘입니다. 최단경로를 찾아내기 위해 보편적으로 사용되는 다익스트라 알고리즘과의 차이점이 있다면, A* 알고리즘은 완전한 최단 경로를 찾지 않고 최단 경로의 근사값을 찾아내는 것을 목표로 한다는 점입니다. 가까운 노드부터 순차적으로 모두 방문하며 탐색하는 다익스트라 알고리즘과 달리, A* 알고리즘은 현재 위치가 얼마나 좋은 상태인지를 적당한 휴리스틱 함수를 통해 추정하여 점수를 매기고, 그 점수를 바탕으로 탐색을 진행합니다. 정확한 정답을 포기한 대신,...
-
양자 컴퓨팅 입문 (1) - 개요
“양자(quantum)를 이용해서 상태를 저장하는 컴퓨터를 만들면 어떨까?” 이 허무맹랑할 수도 있는 1981년 리처드 파인만에 의해 제기되었습니다. 양자 컴퓨팅은 암호학 쪽에서 1997년 Shor가 다항 시간에 인수분해를 할 수 있는 양자 알고리즘을 발견하면서 각광받기 시작했습니다. 지금까지도 고전 컴퓨팅으로 인수분해를 다항 시간 안에 할 수 없고, 또 RSA 같은 많은 암호체계가 인수분해의 수학적 어려움(infeasibility)을 기반으로 두고 있는데 다항 시간에 인수분해를 할 수 있다는 소식은 획기적인 발전이었습니다. 또 Grover는 정렬되지 않은 $N$개의 항목 중 특정 조건을 만족하는 항목을 $O(\sqrt{N})$에...
-
Maximum Matching in General Graph
Maximum matching algorithm of “General graph” 그래프에서 matching은 인접해있는 정점쌍을 중복되지 않게 선택한 것들의 집합이며, maximum matching은 이 집합 중 가장 크기가 큰 것을 구하는 문제이다. 이와 관련하여 만약 그래프가 bipartite라면 보다 간편하게 풀 수 있으며, 이 알고리즘은 잘 알려져있다. 하지만 일반적인 그래프에서 찾는 알고리즘은 보다 복잡하여 CP에서 잘 다루지 않는 내용이다. 그래서 이번에는 잘 알려지지 않은 그래프 최대 매칭에 대한 알고리즘을 소개해보려 한다. 여기서는 일반적인 그래프에서 최대 매칭을 구하는 알고리즘 중 Blossom algorithm에 대해...
-
Singular Elliptic Curves
서론 최근 타원 곡선에 대해서 공부하면서 피상적으로 이해하던 부분을 좀 더 깊이 이해하는 단계에 들어서고 있습니다. 특히 수학에 대해서 배우는 것은 좋아하지만 고등 수학 위로 배운 것이 없어, 많은 재미를 느끼고 있습니다. 그러면서 해소된 궁금점은 바로 “Discriminant가 왜 0이면 안 되는 것일까?” 였습니다. 타원 곡선에 대한 Wikipedia article 을 살펴보면, $y^2 = x^3 + ax + b$ 꼴의 short Weierstrass equation에 대해서 Discriminant $\Delta = -16(4a^3 + 27b^2)$ 가 0이 아니여야 한다는 조건을 달고 있습니다....
-
FPT Inapproximability of Directed Multicut
FPT Inapproximability of Directed Multicut 그래프의 연결성, 그리고 연결성을 변화시키는 방법 (그래프 절단) 은 알고리즘 연구의 극초창기부터 연구되었던 문제들이다. 그래프 절단은 냉전 초기 공중폭격으로 적국의 철도망을 파괴하는 군사적인 목적으로 연구가 시작되었다. 이후 반세기 이상 이러한 류의 문제는 그래프에 대한 최적화 문제 중 가장 기초적인 문제로 자리잡는다. 이 문제는 이론적으로도 다른 문제의 근간이 되며, 무수히 많은 현실적 계산 문제와 연관되어 있다. 그래프 절단 유형의 문제로는 크게 다음과 같은 4가지 종류가 있다. 이하 특정한 언급 없을 시,...