Per ardua ad astra.

백트래킹(Backtracking) 개념 모든 경우의 수를 고려하는 알고리즘 상태 공간을 트리(Tree)로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘(Tree Search Algorithm)이라고 봐도 된다. 방식에 따른 분류 깊이 우선 탐색(Depth First Search, DFS) 너비 우선 탐색(Breadth First Search, BFS) 최선 우선 탐색(Best First Search / Heuristic Search) 경우의 수 구하기는 일반적으로 DFS가 편리하며, 대다수의 문제들은 DFS를 써도 일단 답은 나온다. 하지만, 트리의 깊이(Depth)가 무한대가 될 경우에는 DFS를 사용하면 안된다. 예) 미로 찾기에서 루프(회로)가 발생하는 경우, DFS는 이 가지를 ..

이항 계수(Binomial Coefficient) 개념 이항식을 이항 정리로 전개했을 때 각 항의 계수(Coefficient) 주어진 크기의 (순서 없는) 조합의 가짓수(${}_{n}C_{k}$) 파스칼의 삼각형의 형태로 이미 중세 동서양 수학에 알려져 있었다. 오늘날 쓰이는 표기법 $\displaystyle { n \choose k }$ 은 안드레아스 프라이헤르 폰 에팅스하우젠(Andreas Freiherr von Ettingshausen)이 1826년에 도입하였다. 정의 자연수 `n` 및 정수 `k` 가 주어졌을 때, $\displaystyle { n \choose k }$ 는 다음과 같다. $${n \choose k} = \begin{cases} {}_{n}C_{k} = \frac{n!}{k!(n ..

최대 공약수(GCD)와 최소 공배수(LCM) ; 유클리드 호제법(Euclidean Algorithm) 최대 공약수(GCD; Greatest Common Divisor(Factor)) 두 개 이상의 자연수들의 공통인 약수들의 모임을 공약수(Common Divisor)라고 하고, 공약수 중에서 가장 큰 수를 최대 공약수(Greatest Common Divisor)라고 한다. 예) $12$의 약수는 $\{1, 2, 3, 4, 6, 12\}$ 이고 $18$의 약수는 $\{1, 2, 3, 6, 9, 18\}$일 때, 두 수 $12$와 $18$의 공약수는 $\{1, 2, 3, 6\}$이고 최대 공약수는 $6$이 된다. 코드 int gcd(int x, int y) { for (int i = (x > y ? y : x..

브루트 포스(Brute Force) 개념 브루트(Brute)와 포스(Force)가 결합되어 만들어진 단어이며, "난폭한 힘(폭력)" 이라는 뜻이다. 문제 해결을 위해 오래 걸리고 자원이 많이 들어서 무식하다고 생각될 수도 있지만, 항상 100%의 정확성을 보인다. 정답(Solution)이 발견될 때까지 가능한 모든 선택지를 찾는 방법이다. 예) 4자리 숫자의 패스워드를 찾기 위해 0000부터 9999까지 하나씩 입력하여 찾아보는 경우 따라서 브루트 포스 알고리즘은 완전 탐색 알고리즘이라고 할 수 있다. 간단하고 일관적이지만, 매우 느리다는 단점이 있다. 거의 완벽하게 병렬 작업이 가능하여 병렬 프로그래밍에서 사용된다. 패턴 매칭(Pattern Matching) 등의 작업에 사용될 수 있다. 너비 우선 탐..

하노이 탑(Tower of Hanoi) 개념 프랑스의 수학자 에두아르 뤼카(François Édouard Anatole Lucas)가 1883년 소개한 유명한 문제 재귀(Recursion)를 연습하는데 도움이 되는 알고리즘 다음과 같이 3개의 막대와 N개의 원판(Disk)이 있을 때, 원판을 다음의 순서를 지키면서 A에서 C로 옮기는 작업 각 원판의 크기는 모두 다르다. 원판의 크기는 아래에서부터 위로 갈수로 점점 작아진다. ① 한 번에 하나의 원판만 이동한다. ② 맨 위에 있는 원판만 이동한다. ③ 크기가 작은 원판 위에 큰 원판을 쌓을 수 없다. 이 조건에서 다음을 구하는 것이 하노이 탑의 문제가 된다. ① 최소의 이동 횟수로 옮기는 가짓수 ($2^{N} - 1$) ② 최소의 이동 횟수로 옮길 때, ..

스캐닝 메소드(Scanning Method) 일렬로 나열된 데이터가 주어질 때, 문제에서 요구하는 어떤 특정 구간과 그 구간의 길이를 구하고자 할 때가 있다. 예 아래와 같이 배열 a에 0 또는 1의 데이터가 주어질 때, 연속적으로 1이 발생되는 최대 구간의 길이와 그 때의 위치를 구하라. X 1 0 1 1 0 1 1 1 1 0 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 구간 [1, 1]에는 연속된 1이 1개 발생되었고, 구간 [3, 4]에는 연속된 1이 2개 발생되었으며 구간 [6, 9]에는 연속된 1이 4개 발생되었다. 여기서 연속적으로 1이 발생되는 최대 구간은 [6, 9]이고, 구간의 길이는 4가 된다. 3중 for 문을 이용하여 구하기 다..

부분합(Partial Sum) ; 누적합(Prefix Sum) 연속된 구간 $start$ 부터 $end$ 까지의 합 구하기 일차원 배열 a가 아래와 같이 초기화되어 있다. X 10 20 30 40 50 60 70 80 90 100 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 배열 a에서 연속된 구간 $start$ 부터 $end$ 까지의 합을 $\displaystyle \sum_{k=\text{start}}^{\text{end}} a[k] = a[start] + a[start + 1] + \cdots + a[end -1] + a[end]$ 로 정의한다면 ($start ≤ end$), 구간 5부터 구간 9까지의 합 $\displaystyle \sum_{..

형상수(Figulate Number) 고대 그리스 시대의 피타고라스학파는 우주의 만물이 수로 이루어져 있다고 믿었다. 그래서 도형을 이용하여 숫자를 표현하였고, 수와 도형의 관계를 연구하였다. 이렇게 도형으로 묘사된 자연수를 형상수(Figulate Number)라고 한다. 삼각수(Triangular Number) 개념 삼각형 모양으로 어떤 점을 놓았을 때, 삼각형을 이루기 위해 사용된 점의 개수 알고리즘 삼각수는 연속하는 자연수의 합과 같으며, 공식은 다음과 같다. $$1 + 2 + 3 + \cdots + n = \frac{n × (n+1)}{2}$$ 코드로 나타내면 다음과 같다. #include using namespace std; int main() { int a[6]; for (int i = 1; ..

에라토스테네스의 체(Sieve of Erathosthenes) 개념 지구의 둘레를 처음으로 계산한 고대 그리스 수학자 에라토스테네스(BC273 ~ BC192, Eratosthenes)가 기원전 200년에 고안한 방법으로, 아래와 같은 방법을 이용하여 소수를 구한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1은 소수가 아니라고 했으므로 우선 지워버린다. 다음으로 맨 처음 나오는 수(= 2)는 무조건 소수이다. 왜냐하면 약수가 1과 자기 자신밖에 없기 때문이다. 그리고 2의 배수는 소수가 아니므로 모두 지워버린다. 다음으로 지워지지 않은 수들 중에서 가장 작은 수(= 3)를 찾는다. 이렇게 지워지지 않고 남은 수는 소수이다. 왜냐하면 1이 아니면서 3보다 ..

소인수 분해(Prime/Integer Factorization) 개념 특정 자연수를 1보다 큰 자연수인 소인수(소수인 인수)들만의 곱으로 표현하는 것 합성수를 소수의 곱으로 나타내는 방법 소인수 분해를 일의적으로 결정하는 공식은 아직 발견되지 않았다. 현대 암호학에서 소인수 분해는 암호 처리를 하는데 중요하게 사용된다. 모든 합성수는 소인수 분해된 형태를 가지고 있다. 산술의 기본 정리(Fundamental Theorem of Arithmetic)로 증명된다. 알고리즘 기본 알고리즘 소인수는 1이라는 값이 아닌 2부터 시작하는 것이 핵심이며, 2로 나누지 못할 경우 2에서 하나씩 증가시켜주면서 나누어지는지 체크하면 된다. void factorize(int n) { int factor = 2; // 시작 ..

피보나치 수열(Fibonacci Sequence) 레오나르도 피보나치(1170 ~ 1250, Leonardo Fibonacci) 레오나르도 피보나치(1170 ~ 1250, Leonardo Fibonacci)는 1170년 상업 도시인 이탈리아의 피사에서 태어났다. 그의 아버지는 피사에서 탁월한 상인으로 지중해에서 강력한 권력을 가진 사람 중 한 명이었다. 그의 아버지가 북부 아프리카의 통상 무역 대표로 임명받자, 북부 아프리카로 아들을 데려가 최신 이슬람 수학을 배울 수 있도록 하였다. 피보나치는 이집트, 시리아, 그리스, 시칠리아와 프로방스에서 다양한 공부를 하였고, 그곳에서 인도의 기수법과 아라비아 숫자를 사용하여 10진법으로 계산하는 것을 알게 되었다. 피보나치는 이런 다양한 경험을 살려서 피사로 돌..

삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) 배열에서 특정 key 값이 정해지고, 그 key 값 앞에 있는 배열의 요소들이 오름차순으로 정렬되어 있을 때, key 값이 삽입될 위치를 찾아서 그 위치에 key 값을 삽입하면서 정렬해 나가는 방식 두 번째 요소를 key 값으로 정해서 두 번째 요소가 삽입될 위치를 찾아서 첫 번째 요소부터 두 번째 요소까지 정렬시키고, 다시 세 번째 요소를 key 값으로 정해서 세 번째 요소가 삽입될 위치를 찾아서 첫 번째 요소부터 세 번째 요소까지 정렬시키고 다시 네 번째 요소를 key 값으로 정해서 네 번째 요소가 삽입될 위치를 찾아서 첫 번째 요소부터 네 번째 요소까지 정렬시키고, 다섯 번째 요소를 key 값으로 정해서 다섯 번째 요소가..

버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort) 배열에서 가장 큰 값을 찾아서 마지막에 배치시키고, 다음으로 큰 값을 찾아서 끝에서 두 번째에 배치시키고, 다음으로 큰 값을 찾아서 끝에서 세 번째에 배치시키면서 정렬해 나가는 방식 거품 모양과 같아서 버블 정렬(Bubble Sort)이라고 한다. 구현 $O(n^{2})$ 으로 구현하기 #include using namespace std; #define N 5 int main() { int a[N] = { 7, 6, 9, 5, 8 }; int tmp; for (int i = 0; i a[j + 1]) { tmp = ..

선택 정렬(Selection Sort) 데이터의 교환 스왑(Swap) : 두 변수의 값을 서로 교환하는 작업 다음과 같이 임시 변수(temp)를 생성하여 데이터 교환 작업을 수행할 수 있다. temp = a; a = b; b = temp; 다음과 같이 콤마 연산자(Comma Operator)를 사용하여 한 줄로 처리할 수도 있다. temp = a, a = b, b = temp; 오름차순 정렬(Ascending Sort) 순서 없이 나열된 자료를 작은 순에서 큰 순으로 다시 재배열하는 작업 내림차순 정렬(Descending Sort) 순서 없이 나열된 자료를 큰 순에서 작은 순으로 다시 재배열하는 작업 선택 정렬(Selection Sort) 배열에서 가장 작은 값을 찾아서 배열의 첫 번째에 배치시키고, 다..

최대(Max), 최소(Min), 최빈(Mode) 최대(Max)와 최소(Min) 주어진 배열에서 최댓값과 최솟값을 찾는 알고리즘은 다음과 같다. 만약 배열을 검색해서 max/min 보다 큰/작은 값이 없다면 처음에 가정으로 세운 max/min 값이 최댓값/최솟값이 된다. 최댓값 구하기 ① 배열의 첫 번째 값을 최댓값(max)이라 가정한다. ② 배열을 검색해서 max 보다 큰 값(x)이 있으면 max 값을 x로 변경해준다. (max = x) ③ 결국 마지막엔 최댓값이 max 변수에 남게 된다. 최솟값 구하기 ① 배열의 첫 번째 값을 최솟값(min)이라 가정한다. ② 배열을 검색해서 min보다 작은 값(y)이 있으면 min 값을 y로 변경해준다. (min = y) ③ 결국 마지막엔 최솟값이 min 변수에 남게..

콜라츠 추측(Collatz Conjecture) 개념 1937년에 처음으로 이 추측을 제기한 독일의 수학자 로타르 콜라츠(1910 ~ 1990, Lorthar Collatz)의 이름을 딴 법칙 처음 시작은 임의의 양의 정수 `N` 에서 시작한다. 만약 `N` 이 짝수이면, `N` 을 2로 나눈다. 만약 `N` 이 홀수이면, `N` 에 3을 곱한 후 1을 더한다. 위와 같은 과정을 1이 될 때까지 반복한다. 예) 8 → 4 → 2 → 1, 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 이러한 수들을 마치 우박이 구름 속에서 오르내리며 자라다가 지상으로 떨어지는 것과 비슷하다 하여 "우박수(Hailstone Sequence)" 또는 "3N + 1 Problem" 이라고 불리기도 한다. 아직까지 증..

소수(Prime Number) 약수의 개수를 이용한 소수의 판별 1보다 큰 자연수 중에서 1과 자기 자신 이외에는 약수를 가지지 않는 수, 즉 약수의 개수가 2개인 자연수를 소수(Prime Number)라고 한다. 2의 약수 : 1, 2 3의 약수 : 1, 3 4의 약수 : 1, 2, 4 5의 약수 : 1, 5 6의 약수 : 1, 2, 3, 6 7의 약수 : 1, 7 2, 3, 5, 7, ... 등은 약수의 개수가 2개 이므로 소수이다. 예제 #include using namespace std; int main() { int cnt; for (int i = 2; i

팰린드롬(Palindrome) 팰린드롬(Palindrome) 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시하고, 앞으로 읽으나 거꾸로 읽으나 같은 문장 또는 낱말을 회문(回文) 또는 팰린드롬(Palindrome) 이라고 한다. 예) "소주 만 병만 주소", "여보 안경 안보여" 수학에서도 111, 12321과 같이 똑바로 읽으나 거꾸로 읽으나 같은 수를 팰린드롬 수(Palindrome Number) 또는 대칭수라고 한다. 숫자 뒤집기 숫자 k = 123, r = 0 으로 초기화되어 있다고 할 때, 다음의 순환문을 완료하면 k의 값은 0이 되고 r의 값은 k의 값이 거꾸로 뒤집어진 321이 된다. int k = 123; int r = 0; 숫자 뒤집기 알고리즘 while (k != 0) { p = k..

완전제곱수(Perfect Square Number, 제곱수, 정사각수) 정사각수(Square Number) 어떤 자연수의 제곱이 되는 `1^{2}, 2^{2}, 3^{2}, 4^{2}`과 같은 수를 완전제곱수(Perfect Square Number) 또는 제곱수(Square Number) 또는 정사각수라고 한다. 1 = 1² 1 + 3 = 2² 1 + 3 + 5 = 3² 1 + 3 + 5 + 7 = 4² 1 + 3 + 5 + 7 + 9 = 5² 위에서와 같이 1부터 연속된 홀수의 합은 언제나 완전제곱수임을 알 수 있다. 완전제곱수 판별하기 ① 약수의 개수를 이용한 완전제곱수 판별 완전제곱수는 약수의 개수가 언제나 홀수개이므로 약수의 개수를 확인하여 완전제곱수인지 판별할 수 있다. 예제 1부터 100까지의..

팩토리얼(Factorial) 팩토리얼(Factorial) 1부터 N까지 모두 곱한 수를 N 팩토리얼(Factorial)이라 부르며, 기호로는 N!로 나타낸다. N! = 1 x 2 x 3 x ... x N 곱셈 연산을 할 때의 초깃값은 언제나 1이어야 한다. 초깃값이 0일 경우, 어떤 수를 곱해도 항상 0이 된다. 예) 5! = 1 × 2 × 3 × 4 × 5 = 120 예제 5! 구하기 #include using namespace std; int main() { int fact; fact = 1; // 초깃값은 항상 1이어야 한다. for (int i = 1; i

완전수(Perfect Number), 부족수(Deficient Number), 과잉수(Abundant Number) 완전수(Perfect Number) 그 수 자신을 제외한 모든 약수의 합이 그 수 자신과 같은 수를 완전수(Perfect Number)라고 한다. 예) 6의 약수는 {1, 2, 3, 6} 이고, 그 수 자신을 제외한 1 + 2 + 3의 합은 6과 같으므로 6은 완전수이다. 부족수(Deficient Number) 그 수 자신을 제외한 모든 약수의 합이 그 수 자신보다 작은 수를 부족수(Deficient Number)라고 한다. 예) 8의 약수는 {1, 2, 4, 8} 이고, 그 수 자신을 제외한 1 + 2 + 4의 합은 7과 같으므로 8은 부족수이다. 과잉수(Abundant Number) 그..

배수(Multiple)와 약수(Divisor) 배수(Multiple) 어떤 수에다 1배, 2배, 3배, 4배, ... 한 수들을 그 수의 배수(Multiple)라고 한다. 예) {3, 6, 9, ...} 는 3의 배수이다. 예제 1부터 100 사이의 3의 배수 출력하기 #include using namespace std; int main() { for (int i = 1; i

가우스 계산법(Gaussian Calculation) 가우스(1777 ~ 1885, Carl Friedrich Gauss) 가우스(1777 ~ 1885, Carl Friedrich Gauss)의 선생님 뷔트너는 수업 시간에 잠시 쉴 생각으로 학생들에게 1부터 100까지 더하는 문제를 냈다. 가우스는 순식간에 5050 이라는 정답을 알아내었다. 가우스의 천재성을 알아본 뷔트너는 그에게 고등학교 수학 교과서를 선물했다고 한다. 독일의 수학자 가우스는 아르키메데스, 뉴턴과 함께 수학의 역사살 가장 위대한 세 명의 수학자 중 한 명이다. 가우스 계산법 연속된 수 또는 규칙적으로 나열되어 있는 수열 등의 합을 쉽게 계산하기 위해서 사용하는 계산법 일반화하면 다음과 같다. 처음 값부터 마지막 값까지의 합 = (처음..

알고리즘이란? 알고리즘의 개념 알고리즘(algorithm) : 주어진 문제를 해결하는 절차(Procedure) 각 단계는 기본적인 연산(Operation) 하나로 이루어져 있을 수도 있고, 혹은 다른 부분 문제(Subproblem)에 대한 알고리즘일 수는 있지만 충분히 구체적이어야 한다. 알고리즘의 조건 일반적으로 알고리즘은 다음의 두 조건을 반드시 만족해야 한다. 종료(termination) : 모든 가능한 입력 사례에 대하여 반드시 끝난다. 정확성(correctness) : 모든 가능한 입력 사례에 대하여 옳은 답을 출력한다. 좋은 알고리즘 자원(Resource)을 적게 쓰는 알고리즘이 좋은 알고리즘이라고 할 수 있다. 가능한 입력에 대하여 항상 종료하고 옳은 답을 출력하면 알고리즘이 되지만, 실행시..