1. 알고리즘
컴퓨팅은 입력을 받아 그 입력을 처리한 후 출력하는 과정임.
알고리즘은 입력에서 받은 자료를 출력형태로 만드는 처리 과정을 뜻함.
즉 알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한
규칙들의 순서적 나열임. 이러한 일련의 순서적 규칙들의 나열 방법에 따라 알고리즘의 종류가 달라짐.
같은 출력값이라도 알고리즘적 순서 나열에 따라 출력값에 도달하는 시간은 서로 다를 수 있음.
2. 정확한 알고리즘
2-1) 정확한 알고리즘 개념
알고리즘은 입력을 출력으로 바꾸기 위해 컴퓨터가 따르는 일련의 절차임.
알고리즘은 우리의 일상생활 언어로도 표현할 수 있음. 절차를 순서대로 나열한 목록처럼.
2-2) 정확한 알고리즘 과정
예를 들어, 전화번호부에서 Mike Smith를 찾는 일을 한다고 합시다.
아래 알고리즘을 살펴보면, 전화번호부를 집어 들고 첫 페이지를 펼친 후
Mike Smith가 그 페이지에 있는지 찾습니다. 없으면 그 다음 페이지에서 찾습니다.
Mike Smith 를 찾을 때까지 혹은 전화번호부가 끝날 때까지 이것을 반복합니다.
이 알고리즘은 정확합니다. 만약 Mike Smith가 전화번호부에 있다면
이 알고리즘을 사용한 사람은 Mike Smith 를 찾아내는 데 성공할 것입니다.
2-3) 코드 예시
3**. 효율적인 알고리즘**
3-1) 효율적인 알고리즘 개념
아래 알고리즘을 적용하여 Mike Smith를 찾아봅시다. 먼저, 전화번호부 가운데를 폅니다.
만약 Mike Smith가 그 페이지에 있다면 우리 알고리즘은 끝납니다.
없다면, 전화번호부가 이름순으로 정렬되어 있으므로
우리는 Mike Smith가 지금 페이지보다 앞부분에 있는지 뒷부분에 있는지 알고 있습니다.
그러므로 책의 절반을 버릴 수 있게 되고 나머지 절반에 대해 똑같은 알고리즘을 수행합니다.
한 페이지가 남을 때까지 계속 수행합니다.
마지막에 남은 한 페이지에는 Mike Smith의 이름이 있거나 없거나 둘 중 하나일 겁니다.
3-2) 코드 예시
→ 이 알고리즘은 기존 알고리즘보다 더 효율적입니다.
→ 만약 500페이지가 추가되었다고 가정해 봅시다.
→ 첫 번째 알고리즘을 사용한다면, 추가된 500페이지에 대해 절차가 500번 더 수행될 것입니다.
→ 하지만 두 번째 알고리즘을 사용한다면, 단 1번만 추가로 수행하면 됩니다.
4. Pseudocode(의사 코드)
4-1) 의사코드 개념
컴퓨터 프로그램은 프로그래밍 언어로 작성됨.
프로그래밍 언어는 일반적으로 기계가 알아들을 수 있도록 명령을 내리기 위해 사용되는 언어임.
프로그래밍 언어는 특정한 문법에 의해 작성된 코드를 요구함.
알고리즘을 표현하는 방법으로는 자연어(natural language),
의사 코드(Pseudocode), 순서도(flowchart )등이 있습니다.
의사 코드는 프로그래밍 언어보다 문법적 제약을 적게 받으므로 알고리즘 표현에 많이 사용됨.
4-2) 의사코드 예시
4-2)-1. 문제
방 안에 있는 사람의 수를 세기 위한 알고리즘을 만들어야 한다고 가정했을 때
우리는 숫자 0부터 시작할 것이고 방 안에 있는 각각의 사람을 셀 때마다 1씩 더할 것입니다.
4-2)-2. 의사코드
왼쪽의 의사 코드에서 첫 번째 블록이 이 개념을 표현하고 있습니다.
프로그래밍 언어로 작성된 것이 아니지만 형식에 잘 맞추어져 있기 때문에 진행 순서가 정확해야 함.
<코드 1>의 1번 줄처럼 n 이라는 이름을 부여하고 0 값을 넣어주는 것으로 시작합니다.
이 과정은 ‘할당’이라고 불리는데, 이렇게 함으로써 우리가 만드는 코드 내에서
값을 저장할 수 있는 공간 n 이 마련되고 거기에 0이라는 값이 초기값으로 들어가게 됩니다.
이제 방에 있는 각각의 사람을 위해 우리는 n 이 n+1 이 되도록 다시 할당할 수 있습니다.
그래서 한 사람씩 늘어날 때마다 1씩 증가시켜줄 수 있습니다.
알고리즘의 마지막에서 n은 방 안에 있는 사람 수가 됩니다.
4-2)-3. 의사코드 Image
4-3) 좀 더 효율적인 의사코드
4-3)-1. 문제
더 복잡하지만 효율적인 의사 코드를 보여주기 위해 다른 방법을 사용할 수도 있습니다.
방 안의 모든 사람을 일으켜 세우고 그들에게 숫자 1을 부여합니다.
이제 일어서 있는 다른 사람과 짝을 짓고 그들이 갖고 있던 숫자를 더한 후 한 사람씩 앉습니다.
이 과정을 한 사람이 남을 때까지 반복하면 마지막 남은 사람에게
할당된 숫자는 방 안의 총 인원 수가 될 것입니다.
4-3)-2. 좀더 효율적인 의사코드 Image
