-
꼬리 재귀와 Trampoline In Scala
안녕하세요! 오늘은 스칼라 초심자를 대상으로 Tail Recursion (꼬리 재귀) 와 Trampoline 에 대해 포스팅하려고 합니다. 함수형 프로그래밍이나 모나드를 몰라도 이해할 수 있도록 노력해봤습니다~~ » 이 글을 좀 더 좋은 가독성으로 읽기 « 간단하게 1부터 n 까지 더해주는 함수를 아래와 같이 작성한 뒤 실행 해봅시다. 스택오버플로우 에러가 뜨는 것을 확인할 수 있습니다. def unsafeSum(n: Int): Int = if (n == 1) 1 else n + unsafeSum(n - 1) println(s"sum = ${unsafeSum(100000)}") // 실행결과 // Exception in...
-
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이 아니여야 한다는 조건을 달고 있습니다....