2-1. Algorithms

Algorithms

알고리즘은 입력(Input)에서 받은 자료를 출력(Output형태로 만드는 처리 과정을 말합니다. 즉 알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열 입니다.

정확하고 효율적인 Algorithms

예를 들어 전화번호부에서 Mike Smith를 찾는다면 전화번호부의 처음 페이지부터 그 페이지에 Mike Smith가 있는지 찾은 후 없으면 그 다음페이지를 찾습니다. 

Mike Smith를 찾을 때까지 반복하다보면 만약 Mike Smith가 전화번호부에 있다면 언젠가는 Mike Smith를 찾을 수 있습니다. 

알고리즘을 평가할 때는 정확성도 중요하지만 효율성도 중요합니다. 효율성은 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 것입니다. 한페이지씩 넘겨서 찾는 것은 효율성 측면에서 매우 비효율적이고 시간도 오래걸립니다.

이번에는 전화번호부의 가운데를 열고 그 페이지에 Mike Smith가 있다면 알고리즘은 끝납니다. 하지만 없다면 전화번호부가 이름순으로 정렬되어 있으므로 Mike Smith가 현 페이지에서 앞부분에 있는지 뒷부준에 있는지 알 수 있습니다. 그러므로 책의 절반을 버릴 수 있게 되고 나머지 절반에 대해 똑같은 알고리즘을 수행합니다. 한 페이지가 남을 때 까지 계속 수행한다면 마지막 페이지에 Mike Smith가 존재하거나 없거나 둘 중 하나입니다. 이는 앞서 말한 방법보다 효율 적입니다. 

의사코드

의사코드는 필요한 행동이나 조건을 잘 설정하여 컴퓨터가 수행해야 하는 일을 절차적으로 파악할 수 있게 도와줍니다.

 

1    Pick up phone book

2    Open to middle of phone book

3    Look at page

4    If smith is on page

5        Call Mike

6    Else if Smith is earlier in book

7        Open to middle of left half of book

8        Go back to line 3

9    Else if Smith is later in book

10       Open to middle of right half of book

11       Go back to line 3

12   Else

13       Quit   

 

1     전화번호부를 든다

2.    전화번호부의 중간을 편다

3.    페이지를 본다

4.    만약 Mike Smith가 페이지에 있으면

5.        Mike Smith에게 전화한다

6.    그렇지 않고 만약 Mike Smith가 앞 페이지에 있으면

7.        앞 페이지의 절반을 핀다

8.        3번째 줄부터 다시 실행한다

9.    그렇지 않고 만약 Mike Smith가 뒷 페이지에 있으면

10.      뒷 페이지의 절반을 편다

11.      3번째 줄부터 다시 실행한다

12   그렇지 않으면 

13.      그만둔다

 

노란색 부분은 함수라고 불립니다. 함수는 컴퓨터에게 이 경우에는 사람에게 무엇을 할 지 알려주는 동사와 같습니다. 

 

1    Pick up phone book

2    Open to middle of phone book

3    Look at page

4    If smith is on page

5        Call Mike

6    Else if Smith is earlier in book

7        Open to middle of left half of book

8        Go back to line 3

9    Else if Smith is later in book

10       Open to middle of right half of book

11       Go back to line 3

12   Else

13       Quit  

 

다음 노란색으로 강조된 부분들은 조건이라고 부릅니다. 여러 선택지 중 하나를 고르는 것입니다. 

 

1    Pick up phone book

2    Open to middle of phone book

3    Look at page

4    If smith is on page

5        Call Mike

6    Else if Smith is earlier in book

7        Open to middle of left half of book

8        Go back to line 3

9    Else if Smith is later in book

10       Open to middle of right half of book

11       Go back to line 3

12   Else

13       Quit 

 

앞서 말한 결정을 내리기 위한 질문이 필요합니다. 이것을 불리언이라고 합니다. 답이 예, 아니오 혹은 참, 거짓으로 나오는 아니면 2진법에서 0또는 1로 나오는 질문을 뜻합니다. 

 

1    Pick up phone book

2    Open to middle of phone book

3    Look at page

4    If smith is on page

5        Call Mike

6    Else if Smith is earlier in book

7        Open to middle of left half of book

8        Go back to line 3

9    Else if Smith is later in book

10       Open to middle of right half of book

11       Go back to line 3

12   Else

13       Quit 

 

노란색으로 강조된 부분은 루프 입니다. 어떤것을 계속해서 반복하는 순환입니다.

 

1    Pick up phone book

2    Open to middle of phone book

3    Look at page

4    If smith is on page

5        Call Mike

6    Else if Smith is earlier in book

7        Open to middle of left half of book

8        Go back to line 3

9    Else if Smith is later in book

10       Open to middle of right half of book

11       Go back to line 3

12   Else

13       Quit