알고리즘[ Algorithm ]

[대한민국등소평]

1. 알고리즘

알고리즘, (표준어 알고리듬, 영어: algorithm, IPA: [ǽlɡərìðm])이란 어떠한 문제를 해결하기 위한 여러 동작들의 유한한 모임이다.

1)알고리즘의 사전적 정의는 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법입니다.
원래는 인도에서 아랍를 거쳐 유럽에 보급된 필산(筆算)을 뜻하며, 아랍의 수학자인 알콰리즈미의 이름에서 유래합니다. 또한, 알고리즘은 수학용어와 컴퓨터 용어로 쓰일 때 의미 차이를 둘 수 있으나 수학용어로서의 알고리즘은 잘 정의되고 명백한 규칙들의 집합 또는 유한 번의 단계 내에서 문제를 풀기 위한 과정입니다. 즉 빠르고 정확하게 문제를 해결하기 위한 전 과정을 알고리즘으로 정의할 수 있는 것입니다. 알고리즘은 문제를 해결하기 위한 절차나 방법을 말하는 데 그 단계는 유한합니다.

2)컴퓨터로 어떤 문제를 해결하기 위하여 필요한 자료들과 해결 절차를 알기 쉽게 기술하는 과정을 말한다. 즉, 문제 해결을 위한 인련의 논리적인 절차를 가리키는 말이다. 알고리즘은 프로그램을 작성하기 전에 반드시 설계 되어야 한다.

3)알고리즘이란 어떠한 주어진 문제를 풀기 위한 절차나 방법을 말하는데 컴퓨터 프로그램을 기술함에 있어 실행 명령어들의 순서를 의미한다. 아랍의 수학자인 알고리즈미(Al-Khowarizmi)의 이름에서 유래되었다. 알고리즘에서 가장 중요한 것은 효율성이라고 할 수 있는데 동일한 문제를 푸는 데 있어 결과는 같아도 해결방법에 따라 실행속도나 오차·오류 등에 차이가 있을 수 있기 때문이다. 또한, 알고리즘은 명확해야 하는데 이를 위해 프로그래머들은 주로 순서도나 의사코드(pseudocode) 등을 이용하고 있다.

2.  알고리즘의 표현 설명하기

입출력 설계는 데이터의 형식과 구조를 설계하는 것이고, 알고리즘은 이들 데이터의 구조를 이용하여 처리하는 절차라고 볼수 있다. 따라서 프로그램을 작성할 때에는 컴퓨터가 수행할 동작들의 순서를 알고리즘으로 나타내고, 이 알고리즘을 보다 쉽게 알아볼수 있도록 정해진 기호를 사용하여 작성해야 한다.

3. 순서도의 개요
  

   - 순서도(Flowchart)란:작성된 알고리즘을 알아보기 쉽게 그림으로 나타낸 것으로서, 문제를 분석하여 처리하는 순서를 논리적인 흐름에 따라 단계화시켜 상호간의 관계를 약속된 기호로 일관성 있게 나타낸것이다. 

   - 순서도의 역할과 의미는 ?프로그램의 코딩에 직접적인 자료가 되므로, 순서도가 얼마나 잘 작성되었느냐에 따라 프로글매의 품질이 달라지게 된다.
  

- 순서도의 기호는

.기본기호

     

.프로그래밍 관계 기호:

.시스템 관계기호

      
  

- 순서도의 종류
      .개략 순서도:프로그램의 전체적인 처리 과정의 흐름을 종합적이고 일반적으로 표현한 순서도로서, 전체적인 구조와 기능을 일목요연하게 파악할 수 있다. 

      .상세 순서도:개략 순서도를 기초로 각 처리 단계를 세분화 하여 데이터의 이동과 연산 및 처리, 그리고 입출력 등을 상세하게 나타낸 것이다.

 - 순서도의 작성 요령은?

1) 한국 공업 규격의 표준 기호를 사용한다.

2) 논리적인 흐름은 위에서 아래로, 왼쪽에서 오른쪽으로 작성하며, 특수한 경우에는 화살표로 표시한다.

3) 복잡한 문제는 여러 단계로 세분하여 기술하고, 한 쪽에 모두 작성할 수 없을 경우에는 연결 기호를 사용하여 표시한다.

4) 처음과 끝 또는 부 프로그램에서는 터미널 기호를 이용하여 포시하고, 반복 처리의 내용은 명확히 한다.

- 순서도의 기본 유형은 ?
     .직선형 순서도:업무 내용을 처리할 때 조건에 따라서 분기되거나, 또는 일정한 내용을 반복 처리함이 없이 단순히 한번 순차적으로 처리하고 끝나게 되는 형태의 순서도.

     .분기형 순서도:주어진 조건의 만족 여부에 따라 실행 내용이나 순서를 달리하고자 할 때 작성하는 순서도. 

     .반복형 순서도:특정 조건이 만족될 때 까지 일정한 내용을 반복하여 실행 하도록 그려진 형태의 순서도.

4. 알고리듬의 조건

알고리듬은 일반적으로 다음의 조건을 만족해야 한다.

• 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
• 출력 : 적어도 1개 이상의 결과를 내어야 한다.
• 명확성 : 각 명령어들은 명확하고 모호하지 않아야 한다.
• 유한성 : 알고리듬의 명령어들은 유한번의 수행후에 종료되어야 한다. 이것은 수행 시간의 현실적인 유한성을 의미한다.
• 효과성 : 모든 명령어들은 원칙적으로 종이와 연필만으로 수행될 수 있는 기본적인 것이어야 한다.

5. 알고리듬의 연구 분야

• 고안 : 완벽한 자동화를 통한 알고리듬의 개발은 거의 불가능하다. 따라서 이미 증명된 유용한 알고리듬들을 습득함으로써 보다 유용한 알고리듬을 개발하는 데 그 의미가 있다.
• 검증 : 고안된 알고리듬이 합당한 입력값에 대하여 올바른 결과를 계산해 내는지를 밝히는 절차가 필요하다. 알고리듬 검증은 고안된 알고리듬이 프로그래밍 언어와는 독립적으로 올바르게 작동할 수 있음을 보여주는 데 그 목적이 있다.
• 분석 : 고안된 알고리듬을 실행하기 위해 필요한 실행시간과 필요로 하는 기억장치를 결정하는 것이다.
• 테스트 : 디버깅, 성능분석

6. 알고리듬의 분석 기준

• 정확성 : 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단.
• 작업량 : 전체 알고리듬에서 수행되는 가장 중요한 연산들만으로 작업량을 측정. 해결하고자 하는 문제의 중요 연산이 여러개인 경우에는 각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산
• 기억 장소 사용량
• 단순성
• 최적성 : 그 알고리듬보다 더 적은 중요 연산을 수행하는 알고리듬은 없는가? 최적이란 가장 '잘 알려진' 이 아니라 '가장 좋은'의 의미이다

7. 평균과 최악의 경우 분석

• O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리듬
• O(log N) : 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형
• O(N) : 입력 자료에 따라 선형적으로 실행 시간이 걸리는 경우
• O(N log N) : 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 경우에 나타남.
• O(N²) : 이중 루프 내에서 입력 자료를 처리하는 경우에 나타남.그러나 N의 크기가 작을 때에는 N²이 N log N보다 작을 수 있음.
• O(N³) : 삼중 루프.
• O(2ⁿ) : 가끔씩 알고리듬을 처음 개발할 때 나타날 수 있는 수행시간.
• O(lg n) : 정렬된 배열에서 이분검색
• O(n!) : 외판원 문제(TSP)의 기본적인 해법

8. 알고리즘의 개발과 분석

알고리즘은 유한 개의 명확한 명령들의 집합으로서, 지정된 종류의 입력을 받아 문제의 해(解)가 되는 미리 정해진 출력을 산출하는 것이다.

컴퓨터 프로그램은 알고리즘이 특정한 프로그래밍 언어로 부호화된 것이다. 알고리즘은 컴퓨터 과학의 중심 관심사이기 때문에 많은 이론가들이 효율적인 알고리즘의 개발과 분석에 관심을 갖는다. 중요한 알고리즘들로는 목록 정렬, 데이터 검색, 형상 인식(본문에서 특정한 단어나 구절을 찾는 것), 난수 발생(모의실험 등에서 사용됨) 등이 있다.

알고리즘의 효율성은 대개 특정한 크기의 문제를 해결하기 위해 필요한 시간으로 측정한다. 예를 들어 목록 정렬 문제에 있어서 문제의 크기는 정렬될 대상의 개수이고 정렬 알고리즘의 효율성은 대상 개수의 함수로 표현한다. 알고리즘의 효율성을 논할 때 대개의 경우 알고리즘에 기초한 프로그램을 실행하기 위해 필요한 기억공간의 크기는 부차적인 것으로 취급한다.

효율적 알고리즘은 종종 데이터를 적절한 데이터 구조로 조직하여 얻을 수 있다. 예를 들어 많은 시간이 소요되는 검색의 경우를 살펴보면, 무작위적으로 배열된 N개의 대상에서 특정한 대상을 찾기 위해서는 순차적 검색 알고리즘을 사용해야 하는데, 이때 평균검색 시간은 N에 비례한다.

그러나 만일 대상이 인식번호순으로 정렬되어 있으면 검색시간이 log₂N에 비례하는 2진 검색 알고리즘을 사용할 수 있다. 이때 만일 N이 1,000에서 100만으로 증가하면 순차적 알고리즘이 요구하는 시간은 1,000배로 증가하지만 2진 알고리즘이 요구하는 시간은 단지 2배가 된다.

간결한 알고리즘을 개발하는 강력한 기법으로는 알고리즘 자신이 수행과정에서 자기 자신을 다시 호출하는 재귀(recursion)가 있다. 앞서 예를 든 2진 검색 알고리즘이 재귀적 알고리즘의 대표적인 예이다.

컴퓨터 과학자들이 개발한 알고리즘 설계기법으로서 대표적인 '각개격파'(divide and rule) 기법은 문제를 하위문제들로 나누는 방법인데, 만일 하위문제가 원래 문제와 같은 성질을 지니면 전체 알고리즘을 재귀적으로 표현할 수 있다.

v • d • e 컴퓨터 과학의 주요 분야
수학적 기초	수리논리학 · 집합론 · 정수론 · 그래프 이론 · 형 이론 · 범주론 · 수치 해석 · 이산수학
계산 이론	오토마타 이론 · 계산 가능성 이론 · 계산 복잡도 이론 · 양자 계산 이론
알고리즘 & 자료 구조	알고리즘 · 자료 구조 · 계산기하학
프로그래밍 언어 & 컴파일러	구문 분석 · 컴파일러 · 인터프리터 · 프로그래밍 언어 · 구조적 프로그래밍 · 객체 지향 프로그래밍
병렬 & 분산 시스템	병렬 컴퓨팅 · 컴퓨터 클러스터 · 분산 컴퓨팅 · 그리드 컴퓨팅 · 클라우드 컴퓨팅 · IaaS · PaaS · SaaS
소프트웨어 공학	요구 분석 · 소프트웨어 설계 · 컴퓨터 프로그래밍 · 형식수법 · 소프트웨어 테스트 · 소프트웨어 개발
시스템 아키텍처	컴퓨터 아키텍처 · 마이크로아키텍처 · 운영 체계
통신 & 네트워크	컴퓨터 오디오 · 라우팅 · 네트워크 토폴로지 · 암호학 · 차세대 통신망
데이터베이스	데이터 마이닝 · RDBMS · SQL
인공 지능	자동추론 · 전산언어학 · 컴퓨터 비전 · 진화 연산 · 기계 학습 · 자연 언어 처리 · 로봇학
컴퓨터 그래픽	시각화 · 영상 처리
인간과 컴퓨터 상호 작용	Computer accessibility · 사용자 인터페이스 · 착용 컴퓨터 · 유비쿼터스 컴퓨팅 · 가상현실
계산과학	인공생명 · 생물정보학 · 인지과학 · 계산화학 · 계산론적 신경과학 · 계산물리학 · 수치 해석 · Symbolic mathematics
정보보호	암호학 · 물리 보안 · 소프트웨어 보안 · 인터넷 보안 · 네트워크 보안 · 해킹 · 크래킹