알고리즘은 수학적인 문제를 해결하기 위해 고안되었습니다. 대표적으로 사용되는 알고리즘은 다음과 같습니다.
각각의 알고리즘에 대해 알아보겠습니다.
<Fibonacci sequence>
정의
피보나치 수열은 처음의 두개의 수 0, 1 로 시작하며 그 다음부턴 앞의 두개의 숫자의 합을 요소로 가지는 수열을 말합니다.
피보나치 수열의 표기법과 결과는 다음과 같습니다.
fibonacci(2) = [0, 1]
fibonacci(3) = [0, 1, 1]
fibonacci(7) = [0, 1, 1, 2, 3, 5, 8]
code
위의 코드는 피보나치 수열을 구현한것 입니다.
Big-O
구현된 코드에서 for-loop가 사용되었고 시간복잡도는 O(n)에 해당합니다.
<Factorial of a number>
정의
팩토리얼수는 주어진 숫자에서부터 1까지의 곱을 나타냅니다.
팩토리얼의 표기법과 결과는 다음과 같습니다.
factorial(4) = 4*3*2*1 = 24
factorial(5) = 5*4*3*2*1 = 120
code
Big-O
for-loop가 한번 사용되었으므로 O(n)의 복잡도를 가집니다.
<Prime Number>
정의
소수는 1과 자신의 곱으로만 표현되는 수를 말합니다.
만약 어떤 숫자가 다른 숫자들의 곱으로 표현이 가능하면 그건 소수가 아닙니다.
isPrime(5) = true(1*5 or 5*1)
isPrime(4) = false(1*4 or 2*2 or 4*1)
code
Big-O
for-loop를 한번만 사용되었으므로 O(n)의 복잡도를 가집니다.
Optimized Primality Test
위 코드에서 해당 숫자가 소수인지 테스트하기 위해 n까지의 숫자를 모두 탐색하는 방법을 사용했습니다. 하지만 소수를 테스트하는 더 최적화된 방법이 있는데 optimized primality test 입니다.
소수를 판별하기 위해서 어떤 숫자로 나눠지는지 테스트 하는 범위로 해당 숫자의 제곱근보다 작은 숫자까지만 확인해보면 된다는 방법입니다.
만일 24가 소수인지 판별하기 위해선 24의 제곱근인 4.89.... 보다 작은 4까지만 확인해보면 된다는 이론입니다.
code
Big-O
같은 결과를 반환하고 있지만 for-loop는 기존보다 덜 동작합니다. O(sqrt(n)) 만큼의 복잡도를 가지게 됩니다.
<Power of Two>
어떤 숫자 n 이 주어졌을 때 해당 숫자가 2의 거듭제곱으로 표현할 수 있는지를 판단하는 문제입니다.
n이 2의 거듭제곱으로 표현할 수 없다면 false가 나와야 합니다.
isPowerOfTwo(1) = true(2^0)
isPowerOfTwo(2) = true(2^1)
isPowerOfTwo(5) = false
Pseudocode
n = 8
8/2 = 4 (remainder 0)
4/2 = 2 (remainder 0)
2/2 = 1 (remainder 0)
code
Big-O
코드상에 while-loop를 가지고 있어서 O(n)의 복잡도를 가지지만, while문 안에 n/2의 로직이 포함되면서 반복문의 횟수가 감소합니다. 이런식으로 반복문의 진행과 함께 횟수가 절반씩 줄어드는 경우 O(logn) 의 복잡도를 가지게 됩니다.
Bitwise Power of Two
power of two 를 해결하는 방법중에는 비트연산(bitwise)을 활용하는 방법도 있습니다.
2의 제곱수라면 2진수 표기법으론 맨 앞의 자리를 빼면 모두 0으로 표시됩니다.
예) 1 - 0001, 2 - 0010, 4 - 0100, 8 - 1000
따라서 2의 제곱수에서 1을 빼면 맨 앞자리를 제외한 모든 자리수가 1이되며, 두개의 숫자를 비트연산 할 경우 0이 나오게 됩니다.
code
<Recursion> 재귀
재귀는 솔루션이 동일한 문제의 더 작은 인스턴스에 대한 솔루션에 의존하는 문제 해결 기술입니다. 함수를 사용해서 자기 자신을 부르는 형식으로 사용됩니다.
보통 문제 안에 더 작은 형태로 문제가 반복되는 형태일 경우 유용하게 사용할 수 있습니다.
재귀의 주요 포인트
재귀는 종료가 되는 조건이 반드시 필요합니다.
재귀는 많은 문제를 간단히 해결할 수 있습니다. 하지만 항상 좋은 해결법이 되진 않습니다. 가끔 재귀보단 단순한 형태의 반복문이 더 빠를수도 있습니다.
재귀는 직관적으로는 이해하기 힘든 알고리즘 입니다. 따라서 이해가 힘들더라도 천천히 접근해보는걸 추천드립니다.
<Recursive Fibonacci sequence>
위의 피보나치 수열은 재귀를 통해서도 해결할 수 있습니다.
code
Big-O
피보나치 수열은 1차원적인 순환을 하지않습니다.
O(2^n)의 복잡도를 가집니다. 이 단계의 복잡도는 상당히 높은 복잡도이기 때문에 조심해서 사용해야 합니다.
<Recursive factorial of a number>
팩토리얼 수열 역시 재귀로 구현할 수 있습니다.
code
Big-O
1차원적인 순회를 하기 때문에 O(n) 의 시간복잡도를 가집니다.
