안녕하세요 .. 개강하고 나서 글을 아무것도 못 썼네요 ..... 너무 바빠서 ..
이제부터 수업 듣는거 정리하는 겸 공부할 겸 글 다시 쓰려구요..
1. 알고리즘이란?
알고리즘은 step-by-step precedure for solving a problem 이라고 합니다.
즉 문제를 해결하는 단계별 절차라고 해석할 수 있습니다.
그러면 저희는 왜 알고리즘을 알아야할까요?
단어장에서 hello 라는 단어를 찾는다고 가정해봅시다. 이 때, a부터 시작하면 너무 비효율적이겠죠??
당연히 h부터 시작하는 페이지를 열고, 그 다음 he로 시작하는 단어를 찾고 이런 식으로 찾지 않을까요?
이처럼 문제를 해결하는 절차는 너무나도 중요합니다.
하지만 컴퓨터는 너무나도 빠르고, 메모리는 갈수록 가격이 싸지고 있는데 왜 굳이? 그냥 힘으로 밀어부치면 안 되나? 라는 생각이 들 수 있습니다.
저희가 컴퓨터를 이용해서 계산을 할 때, 어떤 행렬을 계산한다고 생각해봅시다.
3x3 행렬 A, B가 있다고 생각할 때, A행렬의 1행을 B행렬의 1열과 곱하고,,, A행렬의 1행을 B행렬의 2열과 곱하고 ...
이런 식으로 쭉 순차적으로 하다보면 for문을 세 번이나 돌려야겠죠? 지금은 n(행렬의 길이)가 3이라서 27번만 하면 되지만, 만약 n이 1000이라면? 1억이라면?? 상상도 못하겠네요... 정말 빠른 컴퓨터로 돌려도 n이 높아질 수록 시간은 정말 많이 걸릴겁니다.
이처럼 n^3 시간이 걸리는 문제를 만약에 n^2.5로 줄이기만해도 정말 속도 차이가 어마어마할 겁니다.
이렇게 효율 또한 매우 중요합니다.
따라서 알고리즘은 어떤 문제를 해결하는 단계별 절차이고,
저희는 이 알고리즘 이용해서 기존의 문제를 좀 더 효율적이게 헤쳐나가야합니다.
2. 예시, 용어
Problem : a question to which we seek an answer, to say, a solution, 즉 문제는 저희가 정답을 찾기 위한 질문, 해결책을 찾는 것입니다.
Instance of Problem
Parameter : 문제에서 값이 정해지지 않은 변수를 파라미터라고 합니다.
Instance : 이때 파라미터에 지정할 값을 instance라고 합니다. 즉 parameter에 값을 대입한 집합이라고 할 수 있겠네요.
output : Instance가 알고리즘을 통해서 나온 값을 output이라고 합니다.
Solution : 이 Problem을 해결했을 때, 즉 Instance가 들어가서 올바른 algorithm을 통해 나온 output이 원하는 값일 때, 우리는 이 값을 Solution이라고 합니다.
당연히 올바른 algorithm은 어떤 Instance가 들어와도 올바른 output을 내놓겠죠? ㅎㅎ
다른 말로는 어떤 Problem이든 제대로 된 Solution을 찾는 것이 algorithm이라 할 수 있겠습니다!
이 때 알고리즘적의 Instance는 complete set of instances and properties the output must have as a result로 말할 수 있습니다.
예를 들어보겠습니다.
problem : n개의 원소를 가진 S 리스트를 내림차순으로 Sort해라
Solution of this problem : the numbers in sorted sequence
Parameter는 과연 무엇일까요?
Parameter는 n과 S입니다. 왜냐면 n과 S는 정해지지 않았기 때문이죠.
n은 6이 될 수도, 4가 될 수도 있습니다. 마찬가지로 S도 [1,2,3], [6,3,10,8] 등 많은 것들이 있죠
Instance가 n = 6이고, S = [10, 7, 11, 5, 13, 8] 일 때,
Solution of this problem은 S` = [5, 7, 8, 10, 11, 13]이 되겠습니다.
또 다른 예시를 들겠습니다.
problem : Determine wheter the number x is in the list S of n numbers
Solution of this problem : yes if x is in S, and no if it is not in S
일 때,
parameter은 당연히 x, S, n이 되겠죠?
instance : n = 6, S = [10, 7, 11, 5, 13, 8], x = 5라고 했을 때,
Solution은 yes, x is in S and location = 3이 되겠죠
3. 알고리즘과 코드 (Algorithm and code)
위의 두 번째 예시에서 한 번 알고리즘 (문제 해결 전략)을 생각해봅시다.
1. S의 첫 번째 item부터 시작한다.
2. 이 때, item과 x와 비교한다
3. S가 끝나거나 x를 찾을 때까지 1번, 2번을 반복한다
4. 이 때, x를 찾으면 yes를 답하고, x의 위치를 return한다.
만약 찾지 못했다면 no라고 답하고 -1을 return한다.
코드로 한 번 작성해보겠습니다.
원래는 c++이 기준이긴한데, 저는 이번 학기에 python이 너무 많아서 ㅎㅎ...
암튼 둘 다 작성할 수 있으니까 여유가 되면 둘 다 작성할게요. 하지만 default는 python입니다!
n = int(input()) # 변수가 몇개인지 입력 받음
S = list(map(int, input().split())) # 리스트를 입력 받음
x = int(input()) # 찾으려는 수를 입력 받음
location = 0
while location < n and S[location] != x: # S를 벗어나거나, x를 찾으면 종료됨
location += 1
if location < n: # location이 n을 넘기 전에 종료, 즉 x를 찾음
print('Yes', location)
else: # x를 찾지 못함
print('No', -1)이렇게 되겠네요.
Python에 관한 글은 Python 카테고리에 따로 정리할 수 있다면 정리하겠습니다.
하여튼 위처럼 저희가 글로 쓴 문제 해결 전략을 코드로 옮기는데 성공했네요.
이를 좀 더 함수화 시켜보면,
def search(n, S, x):
location = 0
while location < n and S[location] != x: # S를 벗어나거나, x를 찾으면 종료됨
location += 1
return location이렇게 함수화 시킬 수도 있습니다.
정상 작동하는지 한 번 볼까요?
6
10 7 11 5 13 8
5
>>> Yes 3
6
10 7 11 5 13 8
9
>>> No -1제대로 작동하네요 ㅎㅎ
다른 예시로 리스트 S의 모든 원소를 더하는 코드를 한 번 작성해볼까요? 이 부분은 c++로 작성하겠습니다.
int sum (int n, vector<int>& S){
int result = 0;
for (int i = 0; i < n; i++)
result += S[i];
return result;
}간단히 함수로 작성했습니다.
이 함수는 이 문제의 해결책을 찾기 위한 코드일까요? (이제부터 줄여서 솔루션이라고 하겠습니다)
정답은 아닙니다.
왜 아닐까요? ㅎㅎ 한 번 생각해보세요. 왜 아닌지는 다음 글에서 알려드리겠습니다!
4. 요약
암튼 오늘은 알고리즘이 왜 필요한지, 왜 효율적이어야하는지에 대해 알아봤습니다.
parameter은 값이 정해지지 않은 변수이고, instance는 이 parameter들의 집합, 그리고 solution은 우리가 원하는 output이라고 요약할 수 있겠습니다.
결국 알고리즘이란 어떤 문제에 대해서 해결하는 단계적 절차입니다.
이 때, 알고리즘 모든 instance에 대해서 올바른 solution를 내는 절차이고,
이 절차는 효율적이게 되어야합니다.
감사합니다.
다음 글에는 슈도코드, 알고리즘의 속성, 효율적인 알고리즘 개발의 중요성에 대해 알아보겠습니다.
지적 환영합니다!
출처 : 알고리즘 기초, 대학교 강의