알고리즘

알고리즘 문제를 해결하기 위한 절차를 기술한 것 누구나 정해진 절차대로 실행할 수 있어야 한다. 누구나 동일한 입력값이 주어지면 이 절차대로 실행하면 동일한 출력값을 얻을 수 있어야 한다. 일정한 시간안에 출력값을 구할 수 있어야 한다.

Formal하게 정의해 보면 순서대로 정의된 절차 명확성 반드시 원하는 결과가 나와야 한다. 분명한 순서가 있어야 한다. 한 동작을 실행하면 다음에 실행할 동작이 무엇인지 분명해야 한다. 명확성 모든 동작은 명확하게 정의되어야 한다. 모든 동작은 실행 가능해야 한다. 반드시 원하는 결과가 나와야 한다. 일정한 시간 안에 실행되어야 한다.

유사한 알고리즘 요리법 길찾기 …

두부야채땅콩소스볶음 요리법 재료 요리법 인분 : 4 준비시간: 10분 › 조리시간: 10분 › 요리시간:20분 땅콩유 1큰술 인분 : 4  땅콩유 1큰술 홍피망 1개 두부 1모 뜨거운물 1/2컵 간장 2큰술 카옌페퍼 약간 요리법 준비시간: 10분  ›  조리시간: 10분  ›  요리시간:20분   1. 브로콜리와 홍피망은 먹기 좋은 크기로 작게 썰어두세요. 버섯은 슬라이스하고 두부도 작게 깍둑썰기 해두세요. 2. 큰 후라이팬이나 중화냄비를 중간 센불로 달구고 땅콩유를 두른 뒤, 브로콜리, 피망, 버섯을 넣고 약 5분간 볶아주세요. 따로 두세요. 3. 같은 팬에 땅콩유를 두르고 두부를 넣고 노릇하게 볶아주세요. 4. 작은 볼에 땅콩버터, 뜨거운물, 식초, 간장, 당밀, 카옌페퍼를 넣고 잘 섞어준 뒤, 두부를 볶고 있는 팬에 넣고 섞어주세요. 여기에 볶아둔 야채도 넣고 같이 섞어주세요. 5. 약 5분간 땅콩소스가 야채와 두부에 잘 스며들도록 끓여준 뒤, 뜨거울 때 바로 내세요. (자료: allrecipes.kr)

이 요리법은 왜 알고리즘이라고 할 수 없을까?

알고리즘을 어떻게 적을까? 보통 사용하는 일반 언어로 적어 본다.

좀더 알기쉽게 적을 수는 없을까 알고리즘에 일정한 구조(structure)는 없는가? 1. 순차적 구조(sequential structure) S1 S2 S3 S4

2. 분기 구조(branch) true false S1 S’1 S1 S’1 S2 S’2 S2 S’2 S3 S’3 S3 S’3

3. 반복 구조(repetition) S1 S2 S3 S4 S’1

4. 점프 구조(jump) S1 S1 S2 S2 S3 S3 S4 S4 S5 S’1 S’1 S’2

이것 이외에 다른 구조는 없을까???

알고리즘 적기 그렇다면 우리는 알고리즘의 구조를 반영하여 적는다면 이해하기 쉬울 것이다. 알고리즘 기술 방법 플로우차트(flowchart) 프로그램 언어의 코드 - 이것은 특정 프로그램 언어의 문법을 알아야 된다. - 또 코드 수준으로 자세히 적을 필요는 없다. Pseudocode - 프로그램 언어의 코드 전 단계로 프로그램 언어들이 사용하는 구조를 그대로 이용한다.

그렇다면, 앞에서 적었던 알고리즘을 다시 pseudocode로 적어보면,

예1 “Given two nonnegative integer values, a ≥ 0, b ≥ 0, compute and output the product (a × b) using the technique of repeated addition. That is, determine the value of the sum a + a + a + . . . + a (b times).”

예1: 알고리즘(1) Loop b times, adding each time Set the value of count to 0 Set the value of product to 0 While (count < b) do Set the value of product to (product + a) Set the value of count to count + 1 End of loop Output the result Print the value of product

예1: 알고리즘(2)

예2 “Assume that we have a list of 10,000 names that we define as N1, N2, N3, . . . , N10,000, along with the 10,000 telephone numbers of those individuals, denoted as T1, T2, T3, . . . , T10,000. To simplify the problem, we initially assume that all names in the book are unique and that the names need not be in alphabetical order.” Then, input a name and find his or her telephone number.”

예2: 알고리즘(1)

예2: 알고리즘(2)