-
부동소수점 자료형에 대한 이해 1
서론 많은 프로그래밍 언어들에서 우리는 부동소수점 자료형을 사용하게 됩니다. 대표적으로 C, C++의 float와 double, 그리고 long double이 있습니다. 이러한 자료형들을 사용할 때에는 항상 듣는 주의사항이 있습니다. “오차가 발생할 수 있으니까 주의해야 해!” 이러한 경고는 듣는 것만으로는 잘 와닿지 않지만, 부동소수점 자료형들을 실제로 사용해보면 상식적으로는 이해되지 않는 어처구니 없는 상황을 목격하게 됩니다. 대표적으로 0.1 + 0.2 == 0.3이 거짓이라거나, 1.0 / 7.0을 7번 더했는데 1.0과 다르다고 나오는 것들을 보면서 비로소 이 자료형은 이런 간단한 연산 하나...
-
꼬리 재귀와 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에 대해...