알고리즘 _ 1주차 정리

Meaning of Algorithms

- a set of instructions for solving a problem

 

 

Why we use algorithms?

• Algorithms are especially important to computers because computers are general purpose machines for solving problems.
• In order for a computer to be useful, we must give it a problem to solve and a technique for solving the problem.
• Through the use of algorithms, we can make computers intelligent by programming them with various algorithms to solve problems.

 

Algorithms' Characteristics

• Name
• Description
• Input (입력) : Algorithm receives input
  외부에서 제공되는 자료가 0개 이상 있어야 한다. (입력할 수 없는 경우도 있음.)
• Output (출력) : Produces output
  적어도 1개 이상의 결과를 만들어야 한다.
• Generality(일반성) : The algorithm applies to set of inputs
  같은 유형의 문제에 대해 항상 적용될 수 있어야 합니다.
  
• Order of Operations (명령어의 순서) : Exact order of steps to perform
  설명: 알고리즘은 단계별로 순서가 정확하게 정의되어 있어야 합니다. 이 순서가 바뀌면 원하는 결과를 얻지 못할 수 있기 때문에 명령어의 순서는 매우 중요합니다.
  예시: 버블 정렬에서 인접한 두 수를 비교하고, 그 결과에 따라 위치를 바꾸는 과정이 순차적으로 이루어져야 합니다. 만약 순서가 잘못되면 정렬이 되지 않습니다.
  
• Precision(정확성) : The steps are precisely stated
  설명: 알고리즘의 단계는 명확하고 구체적이어야 하며, 애매하거나 불확실한 명령은 없어야 합니다. 알고리즘을 수행하는 사람이든 컴퓨터든, 각 단계를 정확하게 수행할 수 있어야 합니다.
  예시: "숫자를 비교한다"는 구체적인 단계입니다. 반면 "필요한 작업을 수행한다"는 모호한 지시입니다. 정확한 단계가 없으면 알고리즘이 제대로 실행될 수 없습니다.
  
• Finiteness (유한성) : The algorith terminates
  알고리즘은 유한한 단계를 거쳐 실행이 종료되어야 한다. 모든 명령문은 유한한 시간 내에 실행되어야 하고, 무한 루프같은 무한한 반복을 피해야 한다. 알고리즘은 모든 입력에 대해 종료되어야 하므로 무한히 실행되거나 중단되어서는 안된다.
• Correctness(정확성) : The output produced by algorithm is correct
  입력을 이용한 문제 해결 과정과 출력은 논리적이고 정확해야 합니다. 오류가 없어야 함.
  

 

 

※ 알고리즘과 자료구조와의 관계 
알고리즘의 성능은 자료구조에 의해 결정된다.

성능이란, '얼만큼 빨리 수행되느냐.'이다.

같은 자료라고 해도 어떻게 표현되고 저장되느냐에 따라 사용가능한 알고리즘이 달라지기 때문이다.

자료구조의 기본적인 연산을 구현하기 위해서 알고리즘을 사용한다.

 

 

 

※ 알고리즘 분석 기준

 

복잡도란,

1. 알고리즘의 성능, 효율성을 나타내는 척도. 즉. 어떤 알고리즘이 효율적인지 판단하는 척도.
2. 크게 Time Complextity와 Space Complexity로 나눌 수 있음.
3. 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용 공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시함.
4. 복잡도를 나타내는 방법 : 점근 표기법으로 O(빅오), Ω(오메가), Θ(세타) 등이 있고, 주로 빅오와 세타 표기법이 많이 사용됨.

 

알고리즘을 평가할 때는 주로 수행 시간과 메모리 사용량을 기준으로 둔다.

 

1) 시간 복잡도 (Time Complexity)
- 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다.
- 실행 시간이 아닌, 연산 횟수를 센다. 

- 알고리즘의 성능 평가 Case 분류

• 최선의 경우 (Best Case)
  최적의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 적은 경우
• 최악의 경우 (Worst Case)
  최악의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 많은 경우
• 평균의 경우 (Average Case)
  여러 경우의 수를 고려하여, 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우

알고리즘 분석 시 평균의 경우와 최악의 경우가 가장 많이 활용되며, 알고리즘이 복잡해질수록 Average를 구하기 어려워 Worst Case로 Algorithm Perfomance를 파악한다.

 

 

2) 공간 복잡도 (Space Complexity)
- 메모리(저장공간)가 적게 드는 것을 의미한다.

- 프로그램 실행과 완료에 얼마나 많은 공간이 필요한지를 나타낸다.

- 알고리즘을 실행시키기 위해 필요한 공간(space)은 두 가지로 분류한다.

• 고정 공간(Fixed Space), 알고리즘과 무관한 공간
  - 코드가 저장되는 공간
  - 알고리즘 실행을 위해 시스템이 필요로 하는 공간 
• 가변 공간(Variable Space), 알고리즘과 밀접한 공간
  - 문제를 해결하기 위해 알고리즘이 필요로 하는 공간
  - 변수를 저장하는 공간. 순환 프로그램의 경우 순환 스택(recursion stack) 등

 

3) 시간 복잡도 VS 공간 복잡도

- 시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 자원(메모리 공간)이 필요한지를 판단한다.
- 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 파악할 때는 시간 복잡도를 위주로 파악한다.