알고리즘

[Algorithm] 에라스토테네스의 체 : 소수 구하기

#에라스토테네스의 체 에라스토테네스의 체란 일정 범위 내의 소수를 찾는 가장 효율적인 알고리즘이다. 알고리즘의 원리는 어떤 수의 배수는 소수가 될 수 없다는 원리에 착안하여, 어떤 수의 배수가 되는 수들을 지워나가는 식이다. 1. 2 ~ N 까지의 자연수 중 먼저 소수를 찾는다(해당 범위에서는 2부터 시작됨) 2. 그 소수(2)를 제외한, 나머지 N까지의 수 중 우리가 찾은 소수(2)의 배수들을 모두 지운다. 3. 다음 소수(3)를 찾고 이 수를 제외한, 나머지 N까지의 수 중 방금 우리가 찾은 소수(3)의 배수들을 모두 지운다. 4. 위 과정을 N의 제곱근까지 반복한다(소수점은 내림한다). 해당 과정을 반복하고나면, 지워지고 남은 수들이 모두 소수가 된다. #구현 #include #include #de..

[Algorithm] 순차 탐색(Sequential search)과 이진 탐색(Binary search)

순차 탐색(Sequential search) 순차 탐색이란 나열된 데이터를 처음부터 끝까지 하나하나 순차적으로 탐색하면서 원하는 데이터를 찾는 방법을 말합니다. 코드 구현이 쉽고 알고리즘이 간단하다는 장점이있지만, 다른 탐색에 비해 상대적으로 시간이 많이 걸리는 단점이 있습니다. 최악의 경우, 순차 탐색은 1부터 n까지 모든 데이터를 탐색해야하기 떄문에 순차 탐색의 시간복잡도는 O(n)이 됩니다. #include int main(){ int ary[10] = {1, 3, 6, 2, 4, 5, 10, 8, 7, 9}; int len = sizeof(ary)/sizeof(int); int target = 0; scanf("%d", &target); int index = FirstFind(ary, len, t..

[Algorithm] 시간 복잡도(Time complexity)와 Big-O 표기법

무엇이 좋은 코드(Clean code)인가? 우리가 어떤 코드를 작성할 때, 이 코드가 좋은 코드인지를 판별할 수 있는 기준은 무엇이 있을까요? 누군가 우리에게 와서 좋은 코드를 작성해달라고 부탁한다면, 우리는 어떤 기준에 맞추어서 코드를 작성해야 할까요? 개발자들 사이에서, 좋은 코드를 판별하는 기준은 일반적으로 다음과 같은 두 가지 기준으로 설명합니다. 1. Readable (가독성) 다른 사람이 봤을 때, 일반적으로 깨끗하고 누구나 우리의 코드를 이해할 수 있는지에 대한 것입니다. 2. Scalable (확장성) 내부의 유지 보수가 쉽고 확장가능하며 좋은 생산성과 효율을 가지는 코드에 관한 추상적인 개념입니다. 우리는 Big-O를 이용해서 프로그램을 실행시키는데 걸리는 시간과 그 효율성의 측면에서 ..

[Algorithm] 최대공약수(Gcd) : 유클리드 호제법 원리

#유클리드 호제법 유클리드 호제법이란 두 자연수 사이의 최대공약수(Gcd)를 구하는 알고리즘 중 하나이다. 두 자연수 a, b(a>b)에 대하여 a를 b로 나눈 나머지를 r이라고 하자. 그러면 Gcd(a, b) = Gcd(b, r)와 같고, r = 0이 될때까지 이 과정을 반복했을때 b의 값이 두 수의 최대공약수가 된다. #예시 두 수 1248과 462의 최대공약수를 유클리드 호제법을 이용하여 구해보자. a = 1248, b = 462라 하면 1248 = 462 * 2 + 324 이때 Gcd(1248, 462) = Gcd(462, 324)이고, 다시 a= 462, b = 324라 하면 462 = 324 * 1 + 138 마찬가지로 Gcd(462, 324) = Gcd(324, 138)이다. 이 과정을 r ..