Tip:
Highlight text to annotate it
X
알고리즘이란 무엇일까요?
컴퓨터공학에서
알고리즘이란 순서대로 문제를 풀기 위한
지시 절차의 모음입니다.
일반적으로 알고리즘은 컴퓨터에 의해 실행됩니다.
하지만 우리 인간도 알고리즘을 갖고 있습니다.
예를 들어,
방에 있는 사람들의 수를 어떻게 세나요?
음, 만약에 여러분이 저와 같다면
여러분은 아마도 각각의 사람들 가리키며
한 번에 한 명씩,
0부터 세기 시작할 것입니다.
1,2,3,4...처럼요.
음, 이게 바로 알고리즘입니다.
자, 이제 조금 더 공식적으로
유사 부호에 관해 이야기 해볼게요.
유사 부호는 프로그래밍 언어와 유사한
영어와 같은 문법 언어입니다.
n을 0과 같다고 둬봅시다.
방 안에 있는 각각의 사람에 대해 n=n+1이라 설정합니다.
어떻게 이 기호를 해석할까요?
첫 줄이 나타내는 것을 보면
n이라 불리는 변수를 정하고
그 초기값을 0으로 설정합니다.
이는 이 알고리즘에서
우리가 처음으로 셀 것은
0의 값을 갖고 있다는 겁니다.
결국, 숫자를 세기 전에는
아직 아무것도 세지 않은 셈이지요.
이 변수를 n이라 부르는 것은 관례일 뿐입니다.
이것은 어떤 다른 것으로도 부를 수 있습니다.
두 번째 줄은 루프(순환)의 시작을 나타내는데
루프(순환)란 연속적인 절차를 여러 번 반복하는 것입니다.
그래서, 위의 예시에서, 우리가 택하는 단계는
방 안의 사람을 세는 것이지요.
둘 째 줄 밑에 세 번째 줄이 있는데
이것이 우리가 수를 어떻게 세어 나갈 것인지 정확히 설명해줍니다.
이 들여쓰기는 세 번째 줄이
반복될 것임을 의미하지요.
따라서 이 유사 부호가 의미하는 바는
0에서 시작하여
방 안에 있는 각각의 사람들에 대하여
n을 1씩 증가시킨다는 것이지요.
이 알고리즘은 정확한가요?
자, 계속 탐구해 봅시다.
방에 두 사람이 있을 때에도 이 알고리즘이 적용될까요?
한 번 봅시다.
첫 줄에서 n을 0으로 두고
두 사람 각각에 대해
n을 1씩 증가시킵니다.
순환 고리의 첫 번째 과정에서
우리는 n을 0에서 1로 업데이트 하지요.
같은 순환의 두 번째 과정에서
우리는 n을 1에서 2로 업데이트합니다.
그래서 이 알고리즘의 마지막 값은 n=2가 됩니다.
이 숫자 2는 방 안의 사람의 수와 일치합니다.
지금까지는 괜찮지요.
그렇다면 특이한 경우라면 어떤가요?
방 안에 한 사람도 없다고 가정해봅시다.
수를 세는 저를 제외하고요.
첫 줄에서 n을 역시 0으로 시작합니다.
이번에는, 세 번째 줄이 전혀 실행되지 않아요.
이는 방 안에 사람이 아무도 없어서
n은 여전히 0으로 남아있기 때문이지요.
0은 방 안의 사람 수와 여전히 정확히 일치합니다.
꽤 간단합니다. 그렇죠?
하지만, 한 번에 한 명씩 세어나가는 것은 꽤 비효율적이지요?
물론, 좀 더 나은 방법이 있습니다!
한 번에 두 명씩 세어 보는건 어떤가요?
1,2,3,4,5,6,7.8.... 이렇게 세는 것 대신에
이렇게는 어때요?
2,4,6,8...등 으로요.
언뜻 보기에도 훨씬 빨라보이는데, 확실히 빠릅니다.
그럼 이 최적화를 유사 부호로 나타내 볼까요?
n을 0이라 둡시다.
방 안에 있는 사람들 각각의 쌍에 대하여
n = n+2로 설정합니다.
꽤 단순한 변화네요. 그렇죠?
한 번에 한 명을 세는 것 대신에
한 번에 두 명씩 세어 보겠습니다.
따라서 이 알고리즘은 이전 것보다 두 배나 빠르네요.
하지만, 이게 정확할까요?
한 번 봅시다.
만약 방 안에 두 사람이 있다면 이 알고리즘이 적용될까요?
첫 줄에서 n을 0이라 둡시다.
한 쌍(두 명)의 사람들이므로 n을 2씩 증가시켰습니다.
결과적으로 이 알고리즘의 마지막 값은
n=2가 되고 이것은 방 안의 사람 수와 일치하네요.
다음으로 방 안에 사람이 한 명도 없다고 가정해 봅시다.
첫 줄에서 n을 0으로 둡시다.
그래서 세 번째 줄은 전혀 실행되지 않습니다.
방 안에 남은 사람이 없어서
n은 여전히 0으로 남기 때문이지요.
여전히 방 안의 사람 수와 같군요.
그런데 방 안에 3명의 사람이 있으면 어떻게 될까요?
이 알고리즘은 적용될까요?
살펴 봅시다.
첫 줄을 n을 0으로 시작합니다.
한 쌍의 사람들에 대해
n을 2만큼 증가시킵니다.
하지만 그 다음은요?
방 안에 또 다른 한 쌍(두 명)의 사람이 없기 때문에,
더이상 두 번째 줄은 적용될 수 없지요.
그래서 이 알고리즘의 마지막 값인
n은 여전히 2가 됩니다. 즉, 방 안의 사람 수와는 같지 않게 되네요.
사실, 이 알고리즘에는 결함이 있습니다.
왜냐하면 실수가 있었기 때문이지요.
그럼, 새로운 유사 코드로 바로 잡아봅시다.
n을 0으로 놓고
방 안에 있는 사람 한 쌍에 대해
n = n+2로 둡시다.
만약에 쌍을 이루지 못한 한 사람이 남으면,
n을 n+1로 설정합니다.
이 특정한 문제를 해결하기 위해
네 번째 줄에 하나의 조건을 도입했습니다.
다른 표현으로 곁가지(branch)라고 하는데,
쌍을 이루지 못한 한 사람이 있을 때에만 실행되는
조건이지요.
그럼 이제, 1명이 있든 3명이 있든,
혹은 다른 홀수의 사람들이 있든,
이 알고리즘은 그 사람들을 셀 수 있을 것입니다.
좀 더 낫게 만들 수 있을까요?
글쎄요, 우리는 3, 4, 5, 10의 배수로 셀 수 있을 것입니다.
하지만, 그 이상의 수로는
숫자를 세기에 약간 힘든 점이 있지요.
결국 가장 중요한 것은
컴퓨터나 사람에 의해 알고리즘이 실행되면
알고리즘은 단지
문제를 풀기 위한 지시의 모임이라는 것입니다.
이는 단지 세 가지 뿐이지요.
여러분은 알고리즘으로 어떤 문제를 해결하고 싶으신가요?