포털:고등학교/정보·통신 계열 전문 교과(2015)/프로그래밍/알고리즘

알고리즘

알고리즘은 어떤 일은 해결하기 위한 방법이나 문제를 해결하기 위한 절차 등을 단계적으로 나열할 것을 의미한다. 우리는 일상생활에서 많은 알고리즘을 쓰고 있는데 라면을 끓이는 것을 예로 들 수 있다.

면을 익힐 물을 끓이고 그 물에 라면 소스와 건더기를 넣는다.
물이 끓을 때 면을 넣어 익힌다.
국물과 면을 그릇으로 옮긴 다음 맛있게 먹는다.

이런 것들도 모두 알고리즘이라 할 수 있다.

알고리즘의 조건

입력: 알고리즘에 필요한 자료를 외부로부터 받아들인다. 경우에 따라서는 자료가 외부로부터 입력되지 않고 내부에서 생성될 수도 있다.
출력: 알고리즘을 통해 문제를 처리하면 적어도 하나 이상의 결괏값이 나와야 한다.
명확성: 알고리즘의 각 단계는 무엇을 하기 위한 것인지 명확하게 표현되어야 한다.
수행 가능성: 알고리즘의 각 명령어는 수행이 가능하도록 논리적이어야 한다.
유한성: 알고리즘을 절차대로 실행하면 주어진 과정을 처리한 후 반드시 종료되어야 한다.

알고리즘의 표현 방법

자연어

일상생활에서 사용하는 언어(ex)국어,영어)를 이용하여 알고리즘을 나타내는 방법으로 우리가 일상생활에서 쓰는 언어인 만큼 이해하기는 쉽지만 글로 표현하기 때문에 한눈에 알아보기 어렵고 표현이 명확하지 않거나 쓰인 언어의 사용자가 아닌 경우 이해하기 어렵다는 한계가 있다.

순서도

주어진 문제를 해결하는 과정을 각 단계로 구분하여 약속된 도형으로 규칙과 과정에 맞개 배열하여 표현한 그림으로 다른 표현방법보다 비교적 이해하기 쉽다. 또 프로그래밍언어같은 경우에는 작성해 놓고 시간이 지나면 이해하기 어려울 수 있지만 순서도는 한 번 작성하면 일정 시간이 지나도 프로그램을 이해하기 쉽다는 장점이 있다. 순서도 기호

순서도 작성

순서도는 약속된 기호를 사용하는 만큼 표준화된 기호를 사용하고 누구나 쉽게 알아볼 수 있도록 간단하고 명료하게 작성해야 한다. 순서도 작성 예시

순서도 작성 규칙

터미널 기호로 시작과 끝을 표시하며, 흐름선을 이용하여 논리적인 작업 순서를 표현한다.
처리 순서는 위에서 아래로, 왼쪽에서 오른쪽으로 서로 교차되지 않도록 하고, 화살표로 표시한다.
논리적인 흐름이 복잡하고 어려울 때에는 여러 단계로 구분하여 작성한다.
순서도 기호 내부에 처리할 내용을 간단히 기술한다.

의사 코드

자연어로 표현한 것을 연상 기호 등을 사용하여 쉽고 간단하게 문제의 처리과정을 나타낸 것으로 프로그래밍 언보다 쉬운 연상기호를 사용하였기 때문에 비교적 자세하고 읽기도 쉽기 때문에 나중에 실제 프로그램을 만들었을 때 설계대로 잘 코딩되었는지 확인하기 위한 수단으로 사용되기도한다. 또한 프로그래밍 언어로 전환하기 쉽다는 장점이 있지만 순서도처럼 한눈에 이해하기에는 어려움이 있을 수 있다.

자연어와 의사 코드 표현의 예
자연어	의사 코드
A에 1을 저장한다. A와 B를 더한 결과를 S에 저장한다.	A←1 S←A+B
A가 B보다 크면 A에 1을 저장한다. 그렇지 않으면 B에 2를 저장한다.	if(A>B) then A←1 else B←2
A가 5보다 작거나 같을 동안에는 S와 A 값을 더하여 S에 저장한다.	while (A＜＝5) do S←S+A
A값을 출력한다. "정보"라는 문자를 출력한다.	print A print "정보"

프로그래밍 언어

프로그래밍언어(ex) C언어,자바,파이썬 등)를 사용하여 알고리즘을 표현하는 것으로 프로그래밍 언어로 작성한 알고리즘을 바로 실행하여 결과를 볼 수 있다는 장점이 있다. 하지만 프로그래밍 언어로 작성하는 만큼 문제에 대해 이해하지 않거나 사용하는 프로그래밍언어에 대해 잘 모른다면 작성하면 오류가 발생하기 쉽다.

  #include <stdio.h>
  void main(void)
  {
      float su, res; 
      scanf(“%f”, &su);    ←입력
      res=su; 
      printf(“%6.2f\n”, res);    ←출력
  }

알고리즘 설계

알고리즘 설계는 문제 해결 방법을 찾는 과정을 나타내는 것으로, 문제를 이해하여 체계적이면서 논리적으로 결과를 얻을 수 있는 방법들을 생각하는 단계이다.

고려해야할 사항

문제를 해결하는 알고리즘을 찾기 전에 문제를 완벽하게 이해해야 한다. 이를 위해 문제가 요구하는 결과와 주어진 조건에 대해 명확하게 파악하고 분석해야한다.
해결하려는 문제와 같은 유형의 문제를 해결할 수 있는 일반적인 알고리즘을 익혀야 한다. 이는 유용한 알고리즘들을 보다 쉽게 설계하고 조합하는데 밑바탕이 된다.
주어진 문제를 해결하는 과정이 복잡한 경우에는 이를 여러 개의 작은 단위로 나누어 작성하는 것이 좋다. 이 방법을 서브 알고리즘이라 한다. 복잡한 문제를 해결할 때 이해하기 쉽고 관리하기 편리한 프로그램을 만들기 위하여 사용된다.

알고리즘 기본 구조

알고리즘의 기본적인 구조로는 순차, 선택, 반복 구조가 있으며 상황에 맞게 선택되거나 융합되어 사용된다.

순차 구조: 시간적 순서에 따라 차례대로 수행되는 구조이다.
선택 구조: 주어진 조건에 따라 실행 내용이 다르게 진행되는 구조이다.
반복 구조: 주어진 조건에 따라 특정 부분을 반복하여 실행하는 구조이다.

알고리즘 기본 구조 예시

알고리즘 구현

순차형 알고리즘: 위에서 아래의 순서대로 작업을 진행하는 구조로 가장 단순한 형태이다.

선택형(조건형) 알고리즘: 주어진 조건의 반족 여부에 따라 실행 내용이나 순서를 다르게 처리할 때 사용한다.

반복형 알고리즘: 특정 조건을 만족하는 동안 일정한 내용을 반복하여 실행하다가 조건이 만족되지 않을 때 반복을 중단하는 구조이다.