전체 글
유클리드 호제법(Euclidean Algorithm)
어떤 자연수 $n$을 나누어 떨어지게 하는 자연수 $i$를 $n$의 약수라고 하고, $i \mid n$라고 쓴다. 두 자연수 $a, b$의 공통인 약수를 $a, b$의 공약수라고 하고, 가장 큰 공약수를 최대공약수라고 한다. $a,b$의 최대공약수는 $\gcd(a, b)$로 표기할 수 있다. 반대로 $n$으로 나누었을 때 나누어 떨어지는 자연수 $i$를 $n$의 배수라고 한다. 두 자연수 $a, b$의 공통인 배수를 $a,b$의 공배수라고 하고, 가장 작은 공배수를 최소공배수라고 한다. $\text{lcm}(a, b)$로 표기한다. 유클리드 호제법 유클리드 호제법(Euclidean Algorithm)은 유클리드가 기원전 300년경에 만든 인류 최초의 알고리즘으로, 두 수의 최대공약수를 구하는 알고리즘이다..
동적 계획법(Dynamic Programming)
피보나치 수열은 다음 점화식을 통해 나타낼 수 있다. $$F_n = \begin{cases} 0 & \text{if }n = 0 \\ 1 & \text{if }n = 1 \\ F_{n-1} + F_{n-2} & \text{if }n > 1 \end{cases}$$ 그대로 재귀함수로 구현하면 다음과 같다. int fibo(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibo(n-1) + fibo(n-2); } 이 함수는 작은 $n$에 대해서는 빠르게 계산된다. 하지만 $50$을 넣으면 1초 안에 답이 나올까? 아마 나오지 않을 것이다. 그러면 입력값에 따른 총 함수 호출 횟수를 계산해보자. int cnt; int fibo(int n) { cnt..
분할 정복(Divide and Conquer)
분할 정복(Divide and Conquer)은 이름에서도 알 수 있듯이 어떤 문제를 분할하고 분할된 부분 문제(Subproblem)을 각각 정복하여 합쳐서 원래 문제를 해결해 내는 알고리즘 설계 방법이다. 분할하다 기저 사례(Base case)가 나오면 기저 사례는 더 이상의 분할 없이 계산할 수 있다. 이 문제를 예시로 들겠다. 기저 사례는 종이의 내부 색이 모두 같거나 종이가 1x1 사이즈일 때다. 그러면 위 그림을 기저 사례까지 분할하는 과정을 짚어보겠다. 우선 각 단계마다 기저 사례인지 확인해야 한다. 첫 번째 단계에서는 1x1 사이즈도 아니고 내부 색이 모두 같지도 않으므로 바로 해결할 수 없다. 따라서 분할을 해야 한다. 분할을 어떻게 하면 좋을까? 종이의 사이즈가 항상 $2^n \times..
브루트 포스(Brute-Force)
컴퓨터의 가장 큰 장점이 무엇일까? 바로 연산 속도가 사람에 비해 훨씬 빠르다는 것이다. 브루트 포스(Brute-Force)는 컴퓨터의 이러한 특성을 이용하여 가능한 모든 답을 고려해보고, 그 중 정답을 찾아내는 문제 해결 기법이다. 브루트 포스는 거의 모든 문제를 해결하는 데 사용할 수 있지만 가능한 답의 개수와 실행 시간이 비례하기 때문에 가능한 답의 개수를 계산해보고 시간 제한 안에 계산할 수 있는 범위인지 확인한 다음에 사용해야 한다. 이 문제를 보면 두 수 $a, b$의 최대공약수와 최소공배수를 찾아야 한다. 최대공약수는 항상 $\text{min}(a,b)$보다 같거나 작고, 최소공배수는 항상 $ab$보다 같거나 작기 때문에 $1$부터 답이 될 수 있는 수까지 순회하면서 찾으면 된다. 이 경우에..
알고리즘과 시간 복잡도
알고리즘의 정의는 어떤 문제를 풀기 위해 정해진 일련의 절차, 방법을 공식화해 표현한 것. 알고리즘은 다음과 같은 특성을 가지고 있다. 입력: 0개 이상의 외부에서 제공된 자료가 존재함 출력: 1개 이상의 결과를 가짐 명확성: 각 단계가 명확하고 모호함이 없음 유한성: 단계를 유한한 횟수만큼 반복한 후 문제를 해결하고 종료해야 함 일반성: 정의된 입력들에 일반적으로 적용할 수 있음 이처럼 알고리즘은 특정한 문제를 해결할 때 사용되는 방법을 명확하게 나타낸 것이다. 그렇다면 한 문제를 풀 수 있는 알고리즘은 여러 가지가 있을 수 있다. 그렇다면 어떤 알고리즘을 선택해서 문제를 해결해야 할까? 시간 복잡도와 Big-O 표기법 알고리즘의 시간 복잡도는 알고리즘이 답을 내놓기까지 걸리는 시간을 대략적으로 표기하..
알고리즘 공부를 시작하면서
2021년 7월 14일, Baekjoon Online Judge에 가입했다. 그 후 한 달 남짓한 기간동안 500문제 정도를 풀었고, 기초적인 알고리즘을 공부하며 AtCoder와 Codeforces에도 참가하게 되었다. 그런데 지금까지는 알고리즘을 공부하면서 정리를 해 놓지 않고 머릿속으로만 이해했다. 그렇게 하니까 학습을 제대로 하지 않는 것 같은 느낌이 들어서, 이제부터 다시 기초적인 알고리즘을 블로그에 정리해두려고 한다. 아직 초보자의 글이고 공부하면서 정리해 놓는 거라 오류나 잘못된 설명, 혼동을 줄 수 있는 표현을 굉장히 많이 사용할 수 있다. 읽는 사람이 있을지는 모르겠지만 만약 있다면 읽으시면서 오류나 설명이 더 필요한 부분은 댓글로 알려주시면 더 공부해서 수정/보충하도록 하겠다. 목차 목차..