1. Introduction 이번 포스팅에서는 호제법보다 빠른 최대공약수 식별 알고리즘을 소개한다. 스테인 알고리즘 (Stein's algorithm) 이라고도 불리는 알고리즘이며, 기존의 호제법보다 60%의 효율개선을 보이는 획기적인 알고리즘이다. 는 그렇게 대단한 알고리즘이 아니다... 스테인 알고리즘은 이진 GCD 알고리즘이라고도 불리며, 호제법의 이진버전이라고 생각하면된다. 호제법에서 각 루틴마다. $A \bmod B (A>B)$ 를 수행하지만, 스테인 알고리즘에서는 A와 B를 모두 반으로 나눈다. 2. Approach 다음과 같은 규칙을 따른다. 두 수가 짝수일 때는 2로 나눈다. a 변수를 1증가시킨다. 한 수만 짝수일 때는 그 수를 2로 나눈다. 두 수가 홀수일 때는 큰 수에서 작은 수를 뺀..

1. Question 어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다. 이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수..

1. Introduction 호제법은 유클리드의 저서 원론에 적혀있는, 인류 최초의 알고리즘이다. 두 수의 최대공약수를 구하는 방법으로, 정의는 다음과 같다. 두 양의 정수 $a, b (a > b)$에 대하여 $gcd(a, b) = gcd(b, (a\bmod b))$이다. 2. Proof $gcd(a, b)=G$라 하자. 그럼 적당한 서로소인 정수 $A, B$에 대해 $a=GA, b=GB$가 성립한다. 이를 $a=bq+r$에 대입하면, $GA=GBq+r$이고, $r=G(A−Bq)$이다. 여기서 $G$는 $b$와 $r$의 공약수임을 알 수 있다 ($b=GB, r=G(A−Bq)$). 만약 $B$와 $A−Bq$ ($b$와 $r$에서 $G$를 제외한 남은 부분)가 서로소이기만 하면, 즉 $gcd(B, A−Bq)..

1. Introduction 소수는 1과 자기 자신외에는 약수를 가지지 않는 수를 의미한다. 소수를 판별하는 가장 간단한 방법은 2부터 자기자신까지의 수 (효율적으로는 $\sqrt {n}$까지)를 차례로 나눠보는 것이다. 하지만 대량의 소수를 얻어야 할 경우에도 위와 같은 방법을 쓰는 것이 최선일까? 이번 포스팅에서는 대량의 소수를 효율적으로 얻는 에라토스테네스의 체라는 방법을 소개한다. 2. Approach 에라토스테네스의 체의 기본적인 아이디어는 단일 소수판별법처럼 n에 대한 약수로 접근하는 것이 아니라, n의 배수를 기반으로 접근한다. 먼저 1은 소수가 아니므로 제외한다. 2부터 시작해서 소수를 찾으면서 합성수를 제거해 나간다. 2의 배수들은 모두 2를 약수로 가지므로 제외한다. 이제 다음으로 제외..

1. Question 어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다. 빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 진입/이탈 횟수를 최소화하는 경로이며, 원은 행성계의 경계를 의미한다. 이러한 경로는 여러 개 존재할 수 있지만 적어도 3번의 행성계 진입/이탈이 필요하다는 것을 알 수 있다. 위와 같은 은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에게 필..

1. Question 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이..

1. Question 시작 -> 실행 -> cmd를 쳐보자. 검정 화면이 눈에 보인다. 여기서 dir이라고 치면 그 디렉토리에 있는 서브디렉토리와 파일이 모두 나온다. 이때 원하는 파일을 찾으려면 다음과 같이 하면 된다. dir *.exe라고 치면 확장자가 exe인 파일이 다 나온다. "dir 패턴"과 같이 치면 그 패턴에 맞는 파일만 검색 결과로 나온다. 예를 들어, dir a?b.exe라고 검색하면 파일명의 첫 번째 글자가 a이고, 세 번째 글자가 b이고, 확장자가 exe인 것이 모두 나온다. 이때 두 번째 문자는 아무거나 나와도 된다. 예를 들어, acb.exe, aab.exe, apb.exe가 나온다. 이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야 그 결과가 나오는지를 출력하는 문제..

본격적으로 들어가기 전에 적당히 알고 가야할 것 들과 배경지식에 대해 간략하게 설명. 소프트웨어란? - 쉽게 말해, 문서화된 컴퓨터 프로그램 Software Product - 일반적인 대중을 대상으로 만들어질 수도 있고 (Generic) - 특정분야의 전문가를 대상으로 만들어질 수 있음 (Custom) Software Characteristics (SW 개발이 힘든 이유) - 소프트웨어는 눈에 보이지 않음 (invisibility) - 복잡도가 줄어들지 않음 (complexity) - 완성된 이후에도 계속 진화함 (changeability) ... Software Engineering : 소프트웨어의 개발, 운영, 유지보수, 폐기에 대한 체계적인 접근법 (IEEE의 정의) 전체 개발 비용의 60~80%는..