에라토스테네스의 체란? 에라토스테네스의 체란 소수를 판별할 때 사용하는 알고리즘으로 고대 그리스 수학자 에라토스테네스가 발견했다. 여기서 말하는 소수란, 1과 자기 자신만을 약수로 가지는 수를 말한다. 에라토스테네스의 체 원리 1) 아래 그림과 같이 1에서 100까지의 수가 있다. 2) 1은 소수가 아니기 때문에 제외하고 2부터 생각해보자. 2는 소수에 해당하기 때문에 소수임을 체크해주고 2의 배수들은 소수가 아니기 때문에 제외시킨다. 3) 그다음 수인 3을 보면 제외되지 않았기 때문에 소수이다. 그리고 3의 배수를 모두 제외시킨다. 4) 그다음 수인 4는 제외됐으므로 5를 확인한다. 5는 제외되지 않았기 때문에 소수이다. 5의 배수까지 모두 제외시키면 아래와 같다. 5) 이렇게 계속해서 반복하다 보면 ..
유클리드 호제법이란 무엇인가? 유클리드 호제법(Euclidean Algorithm)은 두 자연수의 GCD(최대공약수 - Greatest Common Devisor)를 구하는 알고리즘이다. 서로 호(互) 덜 제(除) 법 법(法) 유클리드 호제법의 원리 두 개의 자연수 A, B가 있다. (A > B) 그리고 A를 B로 나눈 나머지 R이 있다. R이 0이라면, A와 B의 최대공약수는 B이다. R이 0이 아니라면, A와 B의 최대공약수는 B와 R의 최대공약수와 같기 때문에 A에는 B, B에는 R을 대입한 후 1번으로 돌아간다. 재귀로 구현하기 C / C++ int get_gcd(int A, int B) { int R = A % B; if(R == 0) return B; else return get_gcd(B, ..
완전 탐색, 브루트 포스란 무엇인가? 브루트 포스를 사전적 의미로 찾아본다면 아래와 같다. 브루트(Brute) : 무식한 + 포스(Force) : 힘 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. 브루트 포스의 장점 알고리즘을 설계하고 구현하기 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 브루트 포스의 단점 알고리즘의 실행 시간이 매우 오래 걸린다. 메모리 효율면에서 매우 비효율적이다. 브루트 포스의 종류 브루트 포스는 크게 선형구조와 비선형 구조로 나눌 수 있다. 선형 구조 ..
재귀함수란 무엇인가? 자기 자신을 호출하는 함수를 재귀함수(Recursive Function)라고 하며 이때 하는 호출을 재귀호출(Recursive Call)이라고 한다. 팩토리얼, 하노이 탑과 같은 문제에서 많이 사용된다. 재귀 함수의 장점 직관적이며 간단하게 구현할 수 있다. 깊이 우선 탐색, 백트래킹, 분할 정복 등 많은 알고리즘에서 사용되기도 해서 기초가 되는 개념이다. 재귀 함수의 단점 재귀함수의 종료 조건을 잘 설정해주지 않으면 재귀함수를 빠져나오지 못하게 되면서 무한루프에 빠질 수 있다. 재귀 호출의 깊이가 너무 깊어지면 너무 많은 메모리를 사용한다. 불필요한 반복 연산을 하게 될 가능성이 있다. 팩토리얼 문제 재귀함수로 해결하기 팩토리얼을 구하는 함수가 있다고 생각해보자. 5팩토리얼을 재귀..
** C / C++17, Java, Python 언어를 기반으로 진행했으며 모든 문제는 BOJ에서 풀어보실 수 있습니다.** 모든 코드는 불펌을 금지하며 학습을 목적으로 글을 작성하였습니다. 코드 작성자 : 본인 (백준 ID: happiness96) 알고리즘을 시작하기 전에 알고리즘을 시작하기 위해서는 먼저 프로그래밍 언어에 대한 기초 지식이 필요하다고 하였다. 자신이 프로그래밍 언어에 대한 기초 바탕이 돼있는지 확인하기 위해 간단히 몇 문제를 풀어볼 것이다. 앞서 조건문과 반복문을 잘 이해하고 있는지 테스트해보는 문제를 풀어보았다. 그렇다면 이번에는 무엇일까? 아마 PS를 하면서 런타임 에러를 가장 많이 발생시키는 녀석이 바로 이 녀석일 것이다. 손 풀기 정도로 생각하고 아직 이 정도도 어렵거나 벅차다..
** C / C++17, Java, Python 언어를 기반으로 진행했으며 모든 문제는 BOJ에서 풀어보실 수 있습니다.** 모든 코드는 불펌을 금지하며 학습을 목적으로 글을 작성하였습니다. 코드 작성자 : 본인 (백준 ID: happiness96) 알고리즘을 시작하기 전에 알고리즘을 시작하기 위해서는 먼저 프로그래밍 언어에 대한 기초 지식이 필요하다고 하였다. 자신이 프로그래밍 언어에 대한 기초 바탕이 돼있는지 확인하기 위해 간단히 몇 문제를 풀어볼 것이다. 손 풀기 정도로 생각하고 아직 이 정도도 어렵거나 벅차다면 프로그래밍 언어를 더 공부해야 할 때이다. 문제 목록 [2557번] Hello World [1000번] A + B [9498번] 시험 성적 [2884번] 알람 시계 [10817번] 세 수 ..
알고리즘.. 사실 나는 알고리즘이라는 분야를 조금 늦게 접한 편이다. 24살.. 5학년 때 ㅠㅠ 개인적으로는 미리 준비하지 못한 것에 대한 미련이 없기 때문에 지금은 취미로 알고리즘 공부를 하고 있다. 마냥 알찬 삶을 살아온 것이 아니라서 실력으로 보면 마냥 허접하다. 직장 생활을 하면서도 알고리즘 공부를 놓지 못하는 이유는 그만한 매력을 느끼고 있기 때문이 아닐까 생각한다. ㅎㅎ 알고리즘에 대해 이것저것 찾아보신 분들이라면 세상에는 수많은 괴물들이 존재하고 있다는 사실을 알고 있을 것이다. 하지만 기죽을 필요는 전혀 없다. 이 글을 보고있는 당신이 "지금 알고리즘 공부를 하기에 늦지 않았을까?"라고 고민한다면 그런 생각할 시간에 문제 하나를 더 푸는 것을 추천한다. 실은 나보다 훨씬 더 유능하고 똑똑한..