알고리즘을 기술할 수 있는 방법

알고리즘이란?

어떤 문제를 해결하는 절차를 알고리즘(algorithm)이라고 한다.

알고리즘에 관해 자세한 정보를 알고 싶다면 알고리즘 시리즈를 참고해보기 바란다.

프로그램 = 자료구조 + 알고리즘

대부분의 프로그램은 데이터를 처리하고 있고 이들 자료는 자료구조를 사용하여 표현되고 저장된다. 또한 주어진 문제를 처리하는 정차, 즉 알고리즘이 필요하다. 따라서 프로그램은 자료구조와 알고리즘으로 구성되어 있다고 볼 수 있다.

자료구조와 알고리즘은 밀접한 관계가 있어서 자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정된다. 컴퓨터가 복잡한 자료들을 빠르게 저장, 분석, 전송, 갱신하기 위해서는 자료구조가 효율적으로 조작화되어 있어야 한다. 또한 응용 프로그램에 가장 적합한 자료구조와 알고리즘을 선택해야한다.

알고리즘은 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 장치가 이해할 수 있는 언어로 정밀하게 기술한 것이다. 따라서 알고리즘은 특정한 일을 수행하는 명령어들의 집합이다. 여기서 명령어란 컴퓨터에서 수행되는 문장들을 의미한다. 그렇다고 모든 명령어들의 집합이 알고리즘이 되는 것은 아니다.

알고리즘은 다음과 같은 조건들을 만족해야한다.

· 입력 : 0개 이상의 입력이 존재하여야 한다.
· 출력 : 1개 이상의 출력이 존재하여야 한다.
· 명확성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.
· 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.
· 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다.

알고리즘 기술 방법

알고리즘을 기술하는 방법은 다음과 같이 4가지가 있다.

1. 영어나 한국어와 같은 자연어

이 방법은 자연어를 사용하므로 기술이 편리하지만 모호성을 제거하기 위하여 명령어로 쓰이는 단어들을 명백하게 해야만 알고리즘이 될 수 있다.

ArrayMax(A, n)
1. 배열 A의 첫 번째 요소를 변수 tmp에 복사한다.
2. 요소들을 차례대로 tmp와 비교 후, 더 크면 그 값을 tmp로 복사한다.
3. 배열 A으 모든 요소를 비교 했으면 tmp를 반환한다.

2. 흐름도(flowchart)

흐름도(flowchart)는 명확하게 표현할 수 있다는 잠점이 있어 특허 명세서 등에서 많이 사용된다. 그러나 알고리즘이 조금만 복잡해져도 흐름도가 매우 복잡하게 표시되는 단점이 있다.

3. 유사 코드(pseudo-code)

유사 코드(pseudo-code)는 자연어 보다는 더 쳬계적이지만 프로그래밍 언어보다는 덜 엄격한 언어로서 알고리즘의 표현에 흔히 사용되는 방법이다. 유사 코드의 문법은 보통 실제 프로그래밍 언어와 비슷하여 쉽게 이해가 가능하면서도 특정 프로그래밍 언어로 구현할 때의 여러 가지 문제들을 감출 수 있고, 알고리즘의 핵심적인 내용에 대한 집중할 수 있어 알고리즘의 기술에 많이 사용되고 있다.

ArrayMax(A, n)
tmp <- A[0];
for i<-1 to n-1 do
   if tmp < A[i] then
      tmp <- A[i];
return tmp;

4. 특정한 프로그래밍 언어

이 방법은 특정한 프로그래밍 언어를 사용하여 알고리즘을 기술하는 방법이다. 이것은 알고리즘의 가장 정확한 표현이지만, 구현을 위해 구제적인 사항들을 표함하고 있어 알고리즘의 핵심적인 내용 이해를 방해할 수 있다.

int ArrayMax(int score[], int n)
{
   int tmp = score[0];
   for(int i = 1 ; i < n ; i++)
   {
      if(score[i] > tmp)
      {
         tmp = score[i];
      }
   }
   return tmp;
}

[생능출판] 쉽게 풀어쓴 C언어 Express (개정판) _ 저자: 천인국

제 1장 프로그래밍의 개념

Exercise (p45~p47)

p45

1. 컴퓨터가 사용하는 진법은?

① 2진법    ② 8진법    ③ 10진법    ④ 16진법

2. 고급 언어로 작성된 프로그램을 기계어로 바꾸어주는 도구는 무엇인가?

① 링커    ② 컴파일러    ③ 에디터    ④ 디버거

3. 문제를 해결하는 절차를 시각적으로 표현한 것은 무엇인가?

① 구조도    ② 순서도    ③ 의사코드    ④ 설명도

4. 프로그램 개발 과정을 순서대로 적어라.

① 컴파일과 링크    ② 알고리즘의 개발    ③ 요구 사항 분석    ④ 유지보수

⑤ 코딩    ⑥ 프로그램 실행과 디버깅

③ - ② - ⑤ - ① - ⑥ - ④

5. 다음 중 C언어의 특징으로 적합하지 않은 것은?

① 간결한 프로그래밍이 가능하다.

② 객체지향 프로그래밍이 가능하다.

③ 실행 속도가 빠르다.

④ 저수준의 프로그래밍이 가능하다.

6. 컴퓨터를 이용하여 문제를 해결하기 위한 절차를 무엇이라고 하는가?

① 알고리즘    ② 객체지향    ③ 구조적 방법    ④ 자료 구조

7. 알고리즘을 기술할 수 있는 방법을 모두 골라라.

① 순서도    ② 의사코드    ③ 자연어    ④ 디버깅

8. 순서도(flowchart)에서 처리를 나타내는 기호는?

① 

    ② 

    ③ 

    ④ 

9. 다음 중 C언어를 개발한 사람은 누구인가?

① Dennis Ritchie    ② Kernighan    ③ Niklaus Wirth    ④ Bjarne Stroustrup

11. 아날로그 방식과 디지털 방식의 장단점을 비교하라.

아날로그 방식의 장점: 대용량 저장이 가능하다.

아날로그 방식의 단점: 잡음이나 왜곡에 약하다. 조작이나 변경이 어렵다.

디지털 방식의 장점: 잡음에 강하다. 고기능의 추구가 가능하다. 소형화, 저가격화가 가능하다. 멀티미디어가 가능하게 되었다.

디지털 방식의 단점: 값을 표현하는 비트의 개수가 적은 경우에, 화질이나 음질이 떨어진다.

13. 인텔의 CPU에서 사용되는 명령어 중에서 3가지를 선택하여 무슨 일을 하는 명령어인지를 조사하여 보라.

MOV(Move): 데이터 이동 (전송)

XCHG(Exchange Register/memory with Register): 첫번째 오퍼랜드와 두번째 오퍼랜드 교환

IN(Input from AL/AX to Fixed port): 오퍼랜드로 지시된 포트로부터 AX에 데이터 입력.

p46

15. 컴퓨터 부품을 판매하는 인터넷 쇼핑몰을 방문하여서 컴퓨터의 부품에는 어떤 것들이 있고 어떻게 분류할 수 있는지를 조사하라.

컴퓨터 내부 부품: CPU, RAM, 마더보드, 하드디스크, 그래픽카드, 케이스/파워서플라이, 시디롬, 사운드카드, 네트워크카드(랜카드)

컴퓨터 외부 부품: 모니터, 키보드, 마우스, 스캐너, 프린터

17. 기계어, 어셈블리어, 고급 언어의 차이점을 정리하여 보라.

기계어: 특정 컴퓨터의 명령어를 이진수로 표시한 것이며 컴퓨터 하드에워를 설계할 때 결정된다.

어셈블리어: CPU의 명령어들을 이진수가 아닌 영어의 약자로 표기한 것이다.

고급 언어: 특정한 컴퓨터의 구조나 프로세서에 무관하게 독립적으로 프로그램을 작성할 수 있는 언어.

19. 엠베디드 시스템이란 어떤 것인가? 인터넷에서 자료를 찾아서 정리하여 보라.

미리 정해진 특정 시능을 수행하기 위해 컴퓨터의 하드웨어와 소프트웨어가 조합된 전자제어 시스템을 말한다.

21. 다음과 같은 일상적인 행위에 대한 알고리즘을 작성하여 보라.

(a) 프린터를 이용하여 인쇄를 한다.

프린터의 전원을 켠다. -> 종이를 넣는다. -> 인쇄 버튼을 누른다.

(b) 인터넷 쇼핑몰에서 상품을 구입한다.

상품을 선택한다. -> 배송지를 입력한다. -> 결제를 한다.

23. 사용자로부터 원의 반지름을 입력받고 반지름에 2를 곱하여 지름을 구하고 여기에 3.14를 곱하여 원주를 구하는 알고리즘을 순서도를 이용하여 기술하라.

24. 0부터 10까지 적혀있는 카드를 가지고 두사람이 하는 게임이 있다. 한 사람당 2장씩 카드를 뽑아서 가장 큰 숫자의 카드를 가진 사람이 승리한다. 이 게임의 승패를 판정하는 알고리즘을 작성하여 보자. 만약 가장 큰 숫자의 카드가 동일하다면 나머지 카드를 비교하여 승패를 결정한다.

25. 1부터 10까지의 숫자들이 있다. 이들 숫자들은 순서대로 되어있지 않다. 이들 숫자들을 크기 순서대로 정렬시키는 알고리즘을 생각할 수 있는가? 알고리즘을 3가지의 표현 방법 중에서 하나를 선택하여 기술하여 보라.

26. 두 개의 숫자 중에서 큰 수를 반환하는 연산만 지원되는 컴퓨터가 있다. 이 컴퓨터에서 3개의 숫자 중에서 제일 큰 수를 찾으려고 하면 어떤 알고리즘을 사용해야 하는가?

p47

28. 두 개의 컵에 우유와 주스가 각각 담겨있다. 우유와 주스를 교환하기 위한 알고리즘을 고안하라. 사용 가능한 세 번째 컵이 있다고 가정하라.

29-(a). 만약 숫자들의 리스트가 주어지고 이중에서 특정한 숫자를 찾는 알고리즘을 구상하여라. 숫자들은 정렬되어 있지 않다고 가정하라.

29-(b). 만약 숫자들이 크기순으로 정렬되어 있다면 특정한 숫자를 찾는 알고리즘을 어떻게 개선시킬 수 있는가?

(a)번에서는 크기순으로 정렬되어 있지 않기 때문에

처음부터 모든 숫자들의 리스트에서 찾고자 하는 숫자와 비교해야 한다.

즉, 찾고자 하는 숫자가 뒤에 있다면 비효율적.

그러나 크기순으로 정렬되어 있다면 범위를 지정해주면 효율적으로 찾을 수 있다.

31. 소프트웨어의 유지보수에는 어떤 것들이 있는가?

차후에 생길지도 모르는 버그 수정, 사용자의 추가 요구 사항 충족