3.1 알고리즘의 개념

3.1 알고리즘의 개념
알고리즘(algorithm) - 주어진 문제를 해결하기 위한 단계적인 풀이 과정의 모임
: 컴퓨터과학을 알고리즘과 관련된 이슈를 다루는 학문

3.1.1 알고리즘의 정의
비정형적으로 알고리즘 - 주어진 문제를 풀기 위한 명령어들을 단계적으로 나열한 것

이론적인 측면으로 컴퓨터를 사용한 문제 해결의 가능성이므로 아래의 조건을 모두 만족해야 함

- 입출력(input & output): 0개 이상의 외부 입력과 하나 이상의 출력이 있어야 함.

- 명확성(definiteness): 각 명령은 모호하지 않고 단순 명확해야 함.

- 유한성(finiteness): 한정된 수의 단계를 거친 후에는 반드시 종료해야 함.

- 유효성(effectiveness): 모든 명령은 컴퓨터에서 실행 가능해야 함.

위의 조건을 종합하면 알고리즘 - 주어진 문제에 관한 결과를 생성하기 위해 모호함이 없는 간단하고 컴퓨터가 수행 가능한 일련의 유한개의 명령을 순서에 따라 구성한 것.

주어진 문제에 대해서 위의 조건을 만족하는 알고리즘이 존재한다는 것 - 유효한 입력에 대해서 유한 시간 내에 일련의 명령어들을 순서에 따라 적용하여 원하는 결과를 생성하는 프로그램이 존재한다는 것.

° 궁극적으로 주어진 문제를 컴퓨터로 해결할 수 있음을 나타냄.

한편, 이론적으로는 알고리즘이 처리 결과를 기다릴 수 없을 정도의 상당히 긴 처리 시간을 요구해서 현실적으로 해결할 수 없는 문제도 존재기 때문에 실용적인 관점에서는 알고리즘의 효율성이라는 것도 충분히 고려되고 만족해야 할 조건임.

3.1.2 알고리즘 생성 단계
주어진 문제를 해결하는 알고리즘을 생성하기 위해

알고리즘을 설계 -> 설계된 알고리즘을 적절한 방법으로 표현 -> 알고리즘의 정확성을 검증 -> 알고리즘의 효율을 분석

- 주어진 문제의 입출력 조건과 처리 조건 등을 고려해서 문제를 분석하고, 이 내용을 바탕으로 알고리즘의 설계를 수행.

설계가 완료된 내용은 적절한 방법을 통해 기술되어야 하고, 이를 위해 일상적인 언어(자연어), 순서도(flowchart), 프로그래밍 언어, 의사코드(pseudocode) 등과 같은 다양한 표현 방법이 사용됨.

자연어를 사용하는 것은 알고리즘을 표현하는 방법으로 적합하지 못함.

프로그래밍 언어는 각 단계가 바로 컴퓨터로 수행 가능한 명령어로 작성되는 장점이 있지만 프로그래밍 언어와 자료구조 등에 대해 알고 있어야 하고 특정 언어와 자료구조에 종속되는 문제점을 가짐.

순서도 - 도식을 사용해서 알고리즘을 표현하는 방법.
알고리즘의 상세한 부분을 언급하지 않고 처음부터 끝까지의 명령의 흐름을 명확히 나타낼 수 있지만, 큰 프로그램이나 구조적 프로그래밍에는 적용하기 어려운 단점이 있음.

의사코드 - 일상에서 사용하는 언어와 프로그래밍 언어를 적절히 혼합해서 알고리즘을 표현.
표준적인 방법이 없으므로 작업하는 사람에 따라 세부적인 내용을 표현하기도 하고, 자연어에 더 가까운 표현을 사용하기도 하며, 프로그래밍 언어의 구성요소를 직접 사용하는 등 다양한 형태로 표현될 수 있음.

설계된 알고리즘이 문제 해결 과정에서 실제로 사용되려면 정확성과 효율성을 검증하고 분석하는 단계 필요.

이런 단계를 통과한 알고리즘만이 주어진 문제에 적합한 프로그래밍 언어를 사용해서 프로그램으로 코딩되고, 이 프로그램을 컴퓨터에서 수행시켜 주어진 문제를 해결함.

3.1.3 자료구조와 알고리즘의 관계

효율적인 프로그램을 작성하기 위해서는 자료구조와 알고리즘에 대한 충분한 이해가 선행될 필요가 있음.

자료구조 - 처리 대상인 데이터 사이의 논리적 관계를 표현하고 조직화하는 방법.
어떤 구조를 사용하느냐에 따라 작성된 프로그램의 효율성이 달라짐.

문제 해결을 위해 어떤 과정과 방법을 사용하느냐 역시 프로그램의 성능에 직접적인영향을 미치므로 보다 효율적인 알고리즘을 개발하는 것이 중요한 이슈.

자료구조와 알고리즘은 아주 밀접한 관계.

자료구조에 적합한 알고리즘, 알고리즘에 적합한 자료구조를 선정하는 것이 더 효율적인 프로그램을 작성하기 위한 기초가 됨.