# 알고리즘

**주어진 문제를 해결하기 위한 절차나 방법**

- 알고리즘은 어떤 문제를 해결하기 위한 단계적인 절차를 의미하며 컴퓨터 과학에서 주어진 문제를 해결하기 위한 절차나 방법을 의미한다.
- 알고리즘의 필요성
- 문제 해결에 있어 다양한 접근 방식과 효율성을 이해하고 평가할 수 있다.
- 컴퓨터 자원을 효율적으로 사용하여 빠르고 정확한 결과를 도출한다.
- 알고리즘 지식을 바탕으로 최적의 해결책을 찾아내고, 프로그래밍 역량을 향상시킨다.

## 좋은 알고리즘

- 문제를 해결하는 방식은 여러가지가 있을 수 있다. 하지만 좋은 알고리즘은 다음과 같은 특징을 가진다.
- **정확성** : 주어진 문제를 정확하게 해결하는가?
- **효율성** : 주어진 문제를 해결하는 데 얼마나 효율적인가?
- 즉, 알고리즘의 평가할 땐 **정확성**과 **효율성**이 중요시된다.
- 따라서 좋은 알고리즘은 정확하고 효율적이어야 한다.

> 에를 들어 사전에서 원하는 단어를 찾아야 한다면 어떻게 할 것인가?
>
> 방법 1 : 사전의 첫 페이지부터 차례대로 찾아본다.
> 방법 2 : 사전의 중간부터 찾아보고, 찾는 단어가 중간보다 앞에 있으면 앞부분만 다시 찾아본다.
>
> 위 두 방법 중 어떤 방법이 더 좋은 방법일까?

## 알고리즘의 성능 평가

- 알고리즘의 성능은 **시간 복잡도**와 **공간 복잡도**로 평가된다.
- **시간 복잡도**
- 알고리즘의 수행 시간을 평가하는 것
- 시간 복잡도는 **입력 크기에 대한 연산 횟수**로 표현된
- **공간 복잡도**
- 알고리즘의 메모리 사용량을 평가하는 것
- 공간 복잡도는 **입력 크기에 대한 메모리 사용량**으로 표현된다.

### 성능 표기법

모든 알고리즘은 입력 크기에 따라 수행 시간이 달라진다. 따라서 알고리즘의 성능을 평가할 때는 **입력 크기**에 따른 **시간 복잡도**와 **공간 복잡도**를 평가해야 한다.

위의 평가를 표현하는 방법으로는 여러 가지가 있지만, 가장 많이 사용되는 것은 **Big O 표기법**이다.

1. **Big O 표기법** : 최악의 경우를 나타낸다.
2. **Big Ω 표기법** : 최선의 경우를 나타낸다.
3. **Big Θ 표기법** : 평균적인 경우를 나타낸다.

알고리즘을 평가할 때는 **Big O 표기법**을 주로 사용한다. 왜냐하면 **최악의 경우**를 나타내기 때문에 **알고리즘의 안정성**을 평가할 수 있기 때문이다.

> Big O 표기법을 사용하는 이유
>
> 만약 최선의 경우 1초, 최악의 경우 1시간이 걸리는 알고리즘이 있다면, 이 알고리즘을 믿고 사용할 수 있을까? 최악의 경우를 나타내는 Big O 표기법을 사용하는 이유는 이러한 이유 때문이다.

### Big O 표기법

- Big O 표기법은 입력 크기에 대한 연산 횟수를 표현하는 방법이다.
- Big O 표기법은 `O(입력 크기에 대한 연산 횟수)`로 표현된다.
- Big O 표기법은 다음과 같은 규칙을 따른다.
1. 상수항은 무시한다.
2. 계수를 무시한다.
3. 최고차항만을 고려한다.

> 예시
>
> - 입력 N에 대해서 `5` 번의 연산을 수행하는 알고리즘의 시간 복잡도가 있다고 했을 때, Big O 표기법으로는 `O(1)`로 표현된다.
> - 입력 N에 대해서 `3N + 1` 번의 연산을 수행하는 알고리즘의 시간 복잡도가 있다고 했을 때, Big O 표기법으로는 `O(N)`로 표현된다.
> - 입력 N에 대해서 `N^2 + 2N + 1` 번의 연산을 수행하는 알고리즘의 시간 복잡도가 있다고 했을 때, Big O 표기법으로는 `O(N^2)`로 표현된다.

### 시간 복잡도의 종류


- O(1) : 상수 시간
- O(log n) : 로그 시간
- O(n) : 선형 시간
- O(n log n) : 선형 로그 시간
- O(n^2) : 이차 시간
- O(2^n) : 지수 시간
- O(n!) : 팩토리얼 시간

## 알고리즘 표현 방법

알고리즘을 표현하는 방법은 여러 가지가 있다. 대표적인 알고리즘 표현 방법으로는 **자연어(natural language)**, **의사코드(Pseudocode)**, **순서도(flowchart)** 등이 있다.

- 자연어 : 우리가 일상적으로 사용하는 언어. 메뉴얼, 설명서 등에 사용된다.
- 의사코드 : 자연어와 프로그래밍 언어의 형식을 섞어서 작성한 코드로, 사람이 읽을 수 있도록 단순화한 코드를 의미한다. 알고리즘을 설계할 때, 복잡한 문법이나 세부 사항 없이 알고리즘의 핵심 로직을 명료하게 전달하는 목적으로 사용된다
- 순서도 : 알고리즘의 흐름을 그림으로 표현한 것이다.
- 

### 의사코드의 특징

1. 자연어와 프로그래밍 언어의 중간 형태를 가진다
2. 복잡한 문법이나 세부 사항을 최소화하여 알고리즘의 핵심 로직을 쉽게 이해할 수 있다
3. 의사코드는 일반적인 프로그래밍 언어와 달리 표준화되지 않았기 때문에 작성 방식이 작성자마다 다를 수 있다
4. 알고리즘 설계 및 문서화 과정에서 효과적이다
- 설계 단계에서 미리 오류를 확인하고 수정할 수 있다
- 코드 검토가 쉬워진다

> 건물을 지을 때 설계를 하고, 설계에 따라 뼈대를 튼튼하게 하는 것이 중요하듯이, 프로그래밍할 때도 그 구조를 잘 구성하는 것이 매우 중요하다.

### 의사코드 예시

Begin
    Input A
    Input B
    Compute SUM = A + B
    Print SUM
END

파일을 연다. 
파일의 각 행(line)에 대해서 "cat" 이라는 단어를 찾는다. 
    "cat" 단어를 지운다. 
    "cat" 단어를 지운 자리에 "bat"이라는 새로운 단어를 넣는다. 
파일을 닫는다.

FOR each index of string
    IF string(index) is equals to hash
        RETURN "Hash Found"
    END IF
END FOR

let n = 0
for each person in room
    set n = n + 1

- 의사코드에서 반드시 따라야 하는 규칙은 없다
- 의사코드를 어떻게 작성해야 하는지를 정의한 문법은 없다
- 의사코드는 목적이 무엇인가에 따라 의사 코드가 더 자세할 수도 있다

## 알고리즘 설계 방법의 종류

컴퓨터의 많은 알고리즘은 모두 기발안 아이디어에 기반하고 있지만. 큰 틀의 관점에서 다음의 알고리즘 설계 방법을 배워본다.

- 브루트 포스: 가능한 모든 경우의 수를 탐색하여 최적의 해를 찾는 방법. (비효율적일 수 있으나 확실한 해결책을 제공한다)
- 그리디 알고리즘: 각 단계에서 최적의 선택을 하여 전체 문제의 해를 찾는 방법. (항상 최적의 해를 보장하지는 않는다)
- 재귀 알고리즘: 함수가 자기 자신을 호출하여 문제를 더 작은 단위로 나누어 해결하는 방법
- 분할 정복: 문제를 작은 하위 문제로 분할한 후, 각 하위 문제를 해결하고 결과를 결합하여 원래 문제의 해를 찾는 방법
- 백트래킹: 가능한 모든 해를 탐색하되, 어떤 조건을 만족하지 않는 해는 더 이상 탐색하지 않고 되돌아가는 방법
- 동적 계획법: 작은 문제의 해를 저장하고 이를 활용하여 큰 문제의 해를 찾는 방법으로 중복 계산을 줄이고 효율성을 높이는 방법