정의
알고리즘이란, 계산이나 문제 해결을 위한 유한한 갯수의 명확한 절차이다.
또 다른 정의들
- 명확하게 정의된 계산 절차로서, 하나 또는 여러 개의 값을 입력으로 받아, 하나 또는 여러 개의 값을 출력으로 생성하는 것
- 입력을 출력으로 변환하는 일련의 계산 단계
- 명확하게 정의된 계산 문제를 해결하기 위한 도구
예
유한한 정수 집합에서 최댓값을 찾는 알고리즘을 구현하라.
1. 임시 최대값을 수열의 첫 번째 정수로 설정한다.
2. 수열의 다음 정수를 임시 최대값과 비교한다.
- 만약 그것이 임시 최대값보다 크다면, 임시 최대값을 그 정수로 갱신한다.
3. 아직 비교할 정수가 남아 있다면, 이전 단계를 반복한다. 정수가 더 이상 없다면, 알고리즘을 종료한다.
4. 알고리즘이 종료되었을 때, 임시 최대값은 수열에서 가장 큰 정수가 된다.
알고리즘 구체화, 수도코드(Pseudocode)
수도코드란, 영어와 프로그래밍 언어 사이의 중간단계로, 알고리즘의 동작을 사람이 이해하기 쉬운 형태로 표현한 것이다.
자연어보다 구조화되어 있고, 코드보다는 이해하기 쉬운 표현 방식이다.
아래는 유한 집합에서 최댓값을 구하는 알고리즘을 수도코드로 표현한 예시이다.
알고리즘의 특성
- Input : 알고리즘은 0개 이상의 입력값을 받아들인다.
- Output : 출력은 결과로 나가는 정보 또는 데이터이다.
(적어도 하나 이상의 출력이 있어야 함)- Definiteness (명확성) : 계산 과정의 모든 단계는 명확하게 정의되어 있어야 한다.
- Correctness (정확성) : 모든 가능한 입력값에 대해 정확한 출력을 제공해야 한다.
- Finiteness (유한성) : 알고리즘은 유한한 횟수의 단계 후에 반드시 종료되어야 한다.
- Effectiveness (효율성) : 알고리즘의 각 단계는 현실적으로 실행 가능해야 하며, 주어진 입력을 사용해서 유한한 시간 안에 수행될 수 있어야 한다.
- Generality (일반성) : 알고리즘은 다양한 입력값에 대해 동작 가능해야 한다.
일부 예시 알고리즘 문제
- Searching Problems (탐색 문제)
→ 리스트에서 특정 원소의 위치를 찾는 문제
📌 예: 어떤 값이 리스트에 있는지, 있다면 몇 번째인지 찾는 것- Sorting Problems (정렬 문제)
→ 리스트 안의 원소들을 오름차순으로 정렬하는 문제
📌 예: 숫자 목록을 작은 값부터 큰 값으로 정렬
- Optimization Problems (최적화 문제)
→ 가능한 모든 입력 중에서, 특정 기준(최대/최소 등)에 따라 가장 좋은 값을 찾는 문제
📌 예: 최대값, 최소비용, 최단거리 등을 찾는 문제
Definition
An algorithm is a finite set of precise instructions for performing a computation or for solving a problem
Many other definitions
- a well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.
- A sequence of computational steps that transform the input into the output
- A tool for solving a well-specified computational problem
Example
Describe an algorithm for finding the maximum value in a finite sequence of integers.
Solution : Perform the following steps:
1. Set the temporary maximum equal to the first integer in the sequence.
2. Compare the next integer in the sequence to the temporary maximum.
– If it is larger than the temporary maximum, set the temporary maximum equal
to this integer.
3. Repeat the previous step if there are more integers. If not, stop.
4. When the algorithm terminates, the temporary maximum is the largest integer in the sequence.
Specifying Algorithms : Pseudocode
Pseudocode is an intermediate representation between natural language (like English) and a programming language.
It is more structured than plain language, but easier to read than actual code.
Below is an example pseudocode that finds the maximum value in a finite set.
Properties of algorithms
An algorithm must satisfy the following criteria. (Some important features)
- Input: An algorithm accepts zero or more inputs.
- Output: Information or data that goes out (produce at least one output).
- Definiteness: Every step in the computation defined precisely (unambiguous).
- Correctness: Correct output for every possible input
- Finiteness: An algorithm terminates after a finite number of steps.
- Effectiveness: Individual steps are all realizable (the instructions can be performed by using the given inputs in a finite amount of time)
- Generality: The algorithm should work correctly for many possible inputs.
It should not be limited to specific cases.
Some Example Algorithm Problems
- Searching Problems
→ Finding the position of a particular element in a list.
e.g., “Is the value 15 in the list? If yes, at which index?”
- Sorting Problems
→ Putting the elements of a list into a specific order (usually increasing).
e.g., Sort the list from smallest to largest.
- Optimization Problems
→ Determining the optimal value (maximum or minimum) of a particular quantity over all possible inputs.
e.g., Find the maximum score, shortest path, or minimum cost.
