Computer Science - 알고리즘

1. 정의

컴퓨터는 2진법으로 숫자, 글자, 색깔 등을 입력(input)한다.
그리고 출력(output)을 해야 하는데 그 중간 과정에 알고리즘이라는 것이 있다.
알고리즘은 입력(input)에서 받은 자료를 출력(output)형태로 만드는 처리 과정을 뜻한다.

즉, 알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열이다.

다음의 예시를 통해 알고리즘에 대해 이해해보자.

2-1. 정확한 알고리즘 (정확성)

전화번호부에서 Mike Smith를 찾는 일을 한다고 치자.

위 코드는 Mike Smith라는 이름이 나올 때까지 전화번호부를 한 장씩 넘기며 찾는 과정이다. 정확하게 찾을 순 있겠지만 효율성 측면에서 좋지 못한 방법이다.

2-2. 효율적인 알고리즘 (효율성)

위 코드는 책의 절반을 펼친 다음 Mike Smith의 이름을 찾아본 후, 있으면 알고리즘이 끝난다.
만약 없다면, 전화번호부는 이름순으로 정렬되어 있으므로 우리는 Mike Smith가 지금 페이지보다 앞부분에 있는지 뒷부분에 있는지 알고 있다. 그러므로 책의 절반을 버릴 수 있게 되고 나머지 절반에 대해 계속 똑같은 알고리즘을 수행한다.
한 페이지가 남을 때까지 계속 수행한다.
마지막에 남은 한 페이지는 Mike Smith의 이름이 있거나 없거나 둘 중 하나일 것이다.

이 알고리즘은 기존 알고리즘보다 더 효율적이다. 만약 500페이지가 추가되었다고 가정해보자. 첫 번째 알고리즘을 사용한다면, 추가된 500페이지에 대해 절차가 500번 더 수행될 것이다. 하지만 두 번째 알고리즘을 사용한다면, 단 1번만 추가로 수행하면 된다.

3. 예제

다음은 boost course의 '생각해보기'에 제시된 문제다.

친구와 1부터 100까지 숫자 중 1가지 숫자를 맞추는 스무고개 게임을 하려고 합니다. 이 때 사용할 알고리즘을 의사코드로 표현하면 어떻게 될까요?

나름대로 아래와 같이 의사코드를 작성해봤다.

1. Choose a number from 1 to 100.
2. Ask your friend if the answer is right.
3. if correct
4.      game end.
5. else if wrong
6.      Ask your friend if this number is below or above the correct answer. 
7.      if below
8.          delete all numbers above the number you choose.
9.          Choose a random number except for the numbers you delete.
10.         go to line 2. 
10.     else if above
11.         delete all numbers below the number you choose.
12.         Choose a random number except for the numbers you delete.
13.         go to line 2.

1부터 100까지의 숫자 중 랜덤한 숫자 하나를 선택한다.
친구에게 정답이 맞는지 물어본다.
정답이 맞다면 게임이 끝나고,
아니면 선택한 숫자가 정답 숫자 아래에 있는지, 위에 있는지 친구에게 물어본다.

1. 만약 아래에 있다면, 당신이 선택한 숫자 위에 있는 숫자들을 모두 제거한다.
   당신이 제거한 숫자들을 제외한 랜덤한 숫자 중 하나를 선택한다.
   line 2번으로 돌아간다.

2. 만약 위에 있다면, 당신이 선택한 숫자 아래에 있는 숫자들을 모두 제거한다.
   당신이 제거한 숫자들을 제외한 랜덤한 숫자 중 하나를 선택한다.
   line 2번으로 돌아간다.

틀린 부분이 있을 시 댓글 남겨주시면 감사하겠습니다~!

Ref.
Edwith_boost course