1. 슈도코드
앞선 시간에는 리스트 S안에 x가 있는지 해결해봤습니다.
하지만 현실의 문제는 이렇게 단순하지 않고, 점점 더 복잡합니다.
모든 문제 해결 전략을 말로 설명할 수도 없고,,,그렇다고 코드로 다 짜자니 복잡하고,,
이때 중요한 것이 슈도코드(pseudo-code)입니다. 말 그대로 가짜 코드입니다.
코드와 말을 적절히 섞어가며 모두가 이해할 수 있는 코드이죠.
물론 실행은 안 됩니다 ㅎㅎ
한 번 직접 해봅시다.
예시)
Problem : Add all the numbers in the array S of n numbers
Inputs : positive integer n, array of numbers S indexed from 0 to n-1
Outputs : sum, the sum of the numbers in S
첫 번째 글에서의 마지막 예시와 같습니다.
모두가 이해할 수 있는 pseudo-code를 한 번 작성해봅시다.
fuction sumto(list S): # add number in list S
sum = 0
for(i = 0; i < n; i++)
add S[i] to sum
return sum이해가 되시나요? 저도 아직 pseudo-code를 많이 써본 적이 없어서 이게 맞다 아니다를 설명드릴 수가 없네요 ㅎㅎ..
하지만 이해가 되고 의사소통이 된다면 슈도 코드라고 생각합니다.
하여튼 이처럼 슈도코드는 의사소통을 위해 쓰는 간단한 코드라고 생각하시면 됩니다!!
이렇게 슈도코드로 작성하시고, 내가 어떤 문제 해결 전략을 썼는지, 어떻게 해결해야하는지를 그대로 코드에 옮겨쓰시면 됩니다.
즉, Input과 Solution을 파악한다 -> 어떤 문제 해결 전략을 써야하는지 판단한다
-> pseudo-code나 자신이 편한 방법으로 우선 정리한다. -> 정리한 내용을 코드로 그대로 옮겨쓴다. 가 되겠습니다 !
근데 이전 글에서 이 문제에 대한 솔루션(솔루션을 찾는 알고리즘)은 틀렸습니다. c++입니다.
int sum(int n, vector<int>& S){
int result = 0;
for (int i = 0; i < n; i++)
result += S[i];
return result;
}이것은 틀렸다고 말씀드렸습니다. 왜일까요?
분명 슈도코드랑 다를게 없는데? 라고 생각하시겠죠
왜 틀렸냐면, 숫자가 2^32를 넘어가면 더 이상 int는 2^32 이상의 수를 저장할 수 없습니다.
그러면 자연스럽게 오버플로우가 나면서 답은 틀리게 나오겠죠.
저는 Input, Instance의 범위를 지정하지 않았습니다.
당연히 Python이라면 오버 플로우가 나지 않겠죠 ㅎㅎ 그래서 일부로 c++을 썼습니다.
그러면 이 코드가 솔루션이 되게하려면 어떤 조건을 걸어야 하느냐?
단, S의 크기는 메모리를 초과하지 않으며, result는 2^32-1보다 낮게 나온다.
라고 명확히 해줘야합니다. 그러면 답은 제대로 나오겠죠?
그러면 이제 알고리즘의 속성들에 대해 알아봅시다!
2. 알고리즘의 속성
- Zero or more Inputs
- One or more Outputs
- Unambiguity
- Each instruction is an algorithm must be clear enough to follow
- Finiteness
- An algorithm must terminate after a finite numbers of steps
- Feasibility
- An algorithm must be feasible enough to be carried out
input은 0개 이상이어야 합니다. 아무것도 들어가지 않아도, 답이 나올 수 있습니다.
output은 input과 반대로 1개 이상이어야 합니다. input이 들어갔는데 아무런 output을 내놓지 않는다면 무슨 의미가 있을까요?
그리고 Unambiguity, 즉 모호하지 않아야 합니다. 각각의 명령어는 알고리즘을 수행하기 위해 명확해야합니다.
또 유한해야합니다. 정해진 step 혹은 시간 안에 끝내야 합니다. 그렇지 않다면 평생 실행할지도 모릅니다.
마지막으로 실행 가능해야합니다. 실행할 수 없다면 당연히 알고리즘이 아니죠
3. 효율적인 알고리즘 개발의 중요성
전 글에서 말했듯이 컴퓨터는 빨라지고, 메모리 가격은 싸지더라도 알고리즘 효율성은 언제나 중요하게 고려되어야 합니다.
같은 문제를 해결하는 두 개의 알고리즘을 한 번 비교해보도록 하죠!
Problem : Determine whether x is in the sorted array S of n keys
Inputs : positive number n, a key x
sorted(nondecreasing order) array of keys S indexed from 0 to n -1
Outputs : location, the location of x in S (-1 if x is not in S)
라고 문제가 정의되어 있습니다.
이때 알고리즘은 순차 검색과 이분 검색입니다. (Sequential Search, Binary Search)
순차 검색은 앞 글에서 이미 작성한 코드가 있습니다. (Python)
def search(n, S, x):
location = 0
while location < n and S[location] != x: # S를 벗어나거나, x를 찾으면 종료됨
location += 1
return location이고,
이분 검색도 보여드리겠습니다. (Python)
def Binary_search(n, S, x):
low = 0; high = n-1
while low <= high:
mid = (low + high) // 2
if x == S[mid]:
return mid # 찾으면 반환
elif x > S[mid]:
low = mid + 1
else: # x < S[mid]:
high = mid - 1
return -1 # 찾지 못하면 -1 반환위의 코드와 리턴 값이 좀 다르긴한데 아무튼 찾으면 제대로 된 location을 못 찾으면 -1을 프린트합니다.
한 번 확인해보죠
10
1 2 3 4 5 6 7 8 9 10
5
>>> Yes 4 # Sequential Search
>>> Yes 4 # Binary Search
10
1 2 3 4 5 6 7 8 9 10
100
>>> No -1 # Sequential Search
>>> No -1 # Binary Search둘 다 값은 제대로 나오는데... 왜 효율적이어야 하지 라는 생각이 들 수도 있습니다.
한 번 시간을 비교해보겠습니다.
10
1 2 3 4 5 6 7 8 9 10
11
>>> 6.198883056640625e-06 # Sequential Search의 시간
>>> 3.817265625e-06 # Binary Search의 시간한 번 틀린 값을 넣었는데, 두 배의 시간 차이가 나네요.
만약 n이 10이 아니라 100이면? 100이면? 2^32면? 차이는 더더욱 벌어지겠죠
나중에 배우겠지만, 이진 검색의 시간 복잡도는 O(log n)이고, 선형 검색의 시간 복잡도는 O(n)입니다.
쉽게 설명해서 n이 128이면 이진 검색은 8번 비교하고, 선형 검색은 128번 비교합니다.
만약 n이 2^32이면 이진 검색은 33번 비교로 끝나지만, 선형 검색은 2^32번을 비교합니다.
참고로 x가 S안에 없을 때의 얘기입니다. 심지어 이진 검색은 '많아야' 8번, 33번 비교입니다.
일반적으로, n이 2의 제곱인 수일 때,
Sequential Search는 비교를 n번
Binary Search는 비교를 많아야 log_(2)n + 1 입니다. log_(2)n을 이제부터 lg n이라고 하겠습니다.
차이가 상당합니다...
하지만 만약에 list가 정렬되어 있지 않다면? 오히려 Sequential Search가 나을지도 모릅니다 ㅎㅎ
두 번째 예시
사실 검색은 컴퓨터가 워낙 빠르기 때문에 별 생각이 없으실 수도 있습니다.
하지만 이번 예시는 확연이 비교가 드러나기 때문에 한 번 주의깊게 보시길 바랍니다.
Problem : Compute the nTh term of the Fibonacci sequence
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
The Fibonacci sequence is defined by resulsively:
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)
입니다.
이 때, 피보나치 수열을 재귀적으로 정의할 수 있으므로, 한 번 재귀 알고리즘을 이용해 풀어보겠습니다. (Python)
def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
굉장히 쉬워보이죠? 이 때, 50번째 항을 찾아보겠습니다!
시간이 엄청 많이 걸리네요 ...
10분 정도 나뒀는데 아직도 해결을 못해서 그냥 껐습니다......
그냥 20이랑 30을 비교해보겠습니다!
20
>>> 6765
>>> 0.001382589340209961
30
>>> 832040
>>> 0.22245025634765625단순히 10 증가했을 뿐인데, 시간은 200배나 증가해버렸네요..
보시다시피 재귀를 이용한 피보나치 수열은 너무나도 비효율적입니다. 왜냐?
한 번 fib(5)를 손으로 직접 그려보세요.
단순히 fib(5)를 계산하는데, fib(2)를 3번이나 중복으로 계산하고 있습니다.
마찬가지로 n이 커지면 커질수록 중복 계산 부분은 기하 급수적으로 늘어날 것입니다.
T(n)을 recursion tree의 노드 개수라고 했을 때, T(n) > 2^(n/2)입니다. (0, 1은 계산하지 않으므로)
n이 2배 늘어나면 트리의 노드 개수는 배로 늘어납니다. 그리고 중복 계산 또한 배로 늘어나겠죠
즉, 우리는 이 알고리즘을 효율적이게 만들기 위해 어떤 조작이 필요합니다.
- 한 번 계산 했으면, 두 번이상 계산할 필요가 없다.
- 이미 계산한 값은 array에 저장해놓자.
따라서 저희는 이미 계산한 값을 다시 계산할 필요 없이 재사용할 수 있습니다.
그러면 해당 코드를 작성해보겠습니다. (Python)
def fib2(n):
lst = list()
if n <= 1:
return n
else:
lst.append(0)
lst.append(1)
for i in range(2, n+1):
lst.append(lst[i-1] + lst[i-2])
return lst[n]
이번에도 20과 30을 넣어보겠습니다.
20
>>> 6765
>>> 5.91278076171875e-05
30
>>> 832040
>>> 4.792213439941406e-05뒤에 e-05가 있으므로 소숫점을 뒤로 5칸 당기면 됩니다.
그러면 20일때는 약 0.000059~이고, 30일 때는 약 0.000047~ 이네요
단순히 재귀 알고리즘이랑 비교해서 시간 차이만 지금 어마어마하게 차이가 납니다.
그러면 아까 실패한 50도 한 번 도전해봅시다.
50
>>> 12586269025
>>> 4.9114227294921875e-05바로 나오네요 .. 정말 빠르네요 ..
즉, 재귀 알고리즘을 썼을 때는 10분 걸려도 안 나온 값이
메모이제이션 알고리즘을 쓰니까 0.00004초만에 나와버렸습니다.
왜 알고리즘을 효율적으로 짜야하는지 아시겠죠? ㅎㅎ
참고로 여기서 더 줄이는 방법도 있습니다 ㅎㅎ
4. 요약
이번에는 슈도코드, 속성, 효율의 중요성에 대해 알아봤습니다.
슈도 코드는 말 그대로 의사소통을 위한 코드이므로 execute보다는 의사소통에 중점을 두는 코드입니다.
속성은 다섯 가지가 있습니다.
0 이상의 input, 1 이상의 output, 모호하지 말아야하고, 실행 가능해야하고, 유한해야한다.
마지막으로 가장 중요한 효율의 중요성입니다.
알고리즘이라고 중요한게 아닙니다. 중요한건 효율적인 알고리즘입니다.
다음 글에는 알고리즘의 분석과 효율성 증명에 대해 알아보겠습니다.
감사합니다.
지적 환영합니다.