알고리즘의 개념, 표현 방법

Algorithm

알고리즘

• 주어진 문제의 해결을 위해 논리 정연한 절차에 의해 계획한 해결방안을 정형적이고 체계적으로 기술한 것
• 어떤 문제를 해결하기 위해 나열한 계산적인 절차
• 절차 실행 후 주어진 문제에서 요구하는 결과 출력
• 어떤 구조와 방법으로 구성해갈 것인지를 생각하는 기본적인 설계
• 문제를 해결하기 위해 단계별로 명확히 기술하여 나열한 일련의 명령어들의 모임
• 왜 필요한가?
  • 주어진 문제를 해결하기 위함
  • 구체적인 작업에 들어가기 전에 사용

알고리즘의 유래

• 19세기 아랍의 유명한 수학자인 al-Khowarizmi에 의해 알고리즘으로 명명
• 수작업이나 좀 더 유용한 기계로 약간의 계산을 위한 간단한 규칙의 집합
• 숫자를 더하고, 곱하고, 나누는 것들도 알고리즘

알고리즘 종류

• 재귀적 알고리즘
• 탐색 및 정렬 알고리즘
• 그래프 알고리즘
• 확률적 알고리즘
• 경험적 알고리즘
• 병렬 알고리즘
• 분산 알고리즘

알고리즘 수행 절차

• 입력 -> 알고리즘 수행 -> 출력
• 입력: 문제의 각 사례에서 포함하고 있는 숫자 또는 문자들
• 출력: 알고리즘이 수행된 후에 얻을 수 있는 결과로 문제에 대한 해답

알고리즘 문제 예시

• 문제: 순서에 관계없이 나열된 친구들의 이름을 가나다 순에 의해 정렬하여 다시 작성하여라
• 입력: 무작위 순으로 나열된 친구들의 이름 리스트
• 알고리즘: 정렬 알고리즘
• 출력: 가나다 순으로 정렬된 친구들의 이름 리스트

알고리즘의 요건

• 문제를 해결하기 위해 설계된 알고리즘이 작성할 프로그램의 기반으로 제대로 사용되기 위해서는 조건을 만족해야 한다.
  • 입력과 출력(Input / Output)
  • 정확성 (Correctness)
  • 유한성 (Finiteness)
  • 명확성 (Definiteness)
  • 유효성 (Effectiveness)

입력과 출력(Input / Output)

• 외부로부터 0개 이상의 입력을 받아들이고 1개 이상의 결과 출력
• 별도로 외부에서 받은 입력이 없는 경우에는 알고리즘 내부에서 자체적으로 생성

정확성 (Correctness)

• 문제에서 허용하는 범위 내에서는 모든 경우의 가능한 입력에 대해 정확한 출력을 생성해야 된다는 의미
• 문제점
  • 문제가 복잡한 경우 증명 과정이 난해하고 방대함
  • 모든 입력에 대한 테스트를 할 수 없다 => 오류를 완전히 배제할 수 없음

유한성 (Finiteness)

• 알고리즘은 유한한 단계가 실행된 후에는 반드시 종료해야 한다는 의미
• 알고리즘 자체에서 예기치 못한 데이터나 상황에 의해 무한히 반복, 실행되어서는 안 됨

명확성 (Definiteness)

• 알고리즘에 포함된 모든 명령어들과 절차는 정확하고 명료하게 나타나 있어야 한다는 의미
• 즉, 기본적으로 컴퓨터의 작동 원리에 기반한 것이어야 하므로 인간의 처리 방법에 의존한 애매모호한 표현은 처리될 수 없음

ex) n이 10에 가까운 숫자
-> 9.9
-> 9.999
-> 10.000001

유효성 (Effectiveness)

• 알고리즘에서 요구하는 연산은 이산적인 컴퓨터에서 처리될 수 있는 계산이어야 한다

ex) 정수에서 현재 정수보다 한 단계 더 큰 정수를 구하는 연산
-> 현재의 수에 +1을 하면 얻을 수 있으나, 실수에서는 현재의 수보다 큰 다음 수를 요구하는 연산
-> 알고리즘에 표현되어 있다고 할지라도 이를 정확히 처리할 수 있는 방법이 없으므로 사용될 수 없음

알고리즘의 표현 방법

• 알고리즘을 표현하는 방법은 여러 가지
• 처리할 내용을 전달할 수 있는 방법이면 어떤 형태든 가능
• 중요한 것은 기술하는 내용이 알고리즘 내에서 처리할 절차와 데이터 및 명령을 명확히 나타낼 수 있어야 함

알고리즘 표현 예시

문제: n개의 숫자 오름차순 정렬

• 자연어 표현
  • 리스트 ~번째 ~째의 위치를 바꾸고....
  • 두 번째...
  • 반복하여 리스트의 모든 데이터가 정렬할 때까지 수행한 후 종료
• 자연어 표현의 문제점
  • 모호한 부분이 존재
  • 모호함의 반복
    • 개인적 해석에 따라 다음 단계에서 처리할 부분을 서로 다르게 추리할 수 있는 소지가 충분히 존재
  • 리스트
    • 리스트의 구조 및 내부 데이터 저장 방식이 나타나 있지 않음
  • 결과 저장
    • 정렬된 결과를 어디에 어떻게 저장해야 하는지 나타나 있지 않음

알고리즘 표현법

• 기호로 표현
• 프로그래밍 언어로 표현
• 수학적 수식으로 표현