> For the complete documentation index, see [llms.txt](https://dahye-jeong.gitbook.io/til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dahye-jeong.gitbook.io/til/algorithm.md).

# Algorithm

프로그래밍 = **자료구조** + **알고리즘**

컴퓨터가 효율적으로 문제를 처리하기 위해서는 **문제를 정의하고 분석**하여 최적의 프로그램을 작성해야한다.

* 자료(Data) : 프로그램의 처리 대상이 되는 값들
* 자료형(Data Type) : 처리할 **자료의 집합**과 자료에 대해 적용할 수 있는 **연산자의 집합**
  * 연산(operation)  : 어떤 일을 처리하는 과정
* 자료구조(Data Structure) : 자료를 효율적으로 표현하고 저장하고 처리할 수 있도록 정리하는 것
  * 스택(Stack), 큐(Queue)
  * Array List, Node List, Sequence
  * Map, Dictionary
  * Priority Queue
  * Tree, Binary Tree, Heap, Search Tree
  * Graph

## 자료의 추상화(Data Abstraction)

* 크고 복잡하고 어려운 문제를 처리할 때
  * 큰 문제는 **작게 나누어** 단순히 생각하기(단순화)
  * 핵심적인 것에 집중하기(추상화)
  * 중요정보부터 강조하기(정보은닉)

### 추상 데이터 타입(ADT : Abstract Data Type)

자료와 연산자의 특성을 **논리적으로 추상화**하여 정의한 자료형

* **추상화** : "무엇(what)"인가를 논리적으로 정의 : 알고리즘 정의
* 구체화 : "어떻게(how)"할 것인가를 실제적으로 표현 : 프로그램 구현

## 알고리즘(Algorithm)

주어진 문제를 해결하기 위한 **단계적인 절차**이다.

이 절차에는 **입력값**과 **출력값**이 존재해야하며, **유한한 단계**를 거쳐서 **반드시 종료**되어야 한다.

### 조건

* 입력 : 0개 이상의 입력 존재
* 출력 : 1개 이상의 출력 존재
* 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야함
* 유한성 : 한정된 수의 단계 후에는 반드시 종료한다.
* 유효성 : 각 명령어들은 실행 가능한 연산이어야한다.

### 표현방법

알고리즘은 주로 **자연어, 의사코드, 프로그래밍언어** 등의 방법으로 기술할 수 있다.

#### 자연어

```
알고리즘 A
(1단계) 원소의 인덱스를 id로 정의한다.
(2단계) 집합 S에 대하여 1<=id<=n까지의 합을 구하고 이를 s라 한다.
(3단계) s를 출력하고 종료한다.
```

#### 의사코드(shudo code)

```
알고리즘 A
(1단계) id←1,s←0
(2단계) s = s + Sid, id ← id + 1
(3단계) id <= n goto 2단계
(4단계) print s
```

#### 프로그래밍 언어

```c
void A(int S, int n){
    int s = 0;
    for(int id = 1;id<=n;id++){
        s = s + S[id];
    }
    printf("%d\n",s);
}
```

#### 순서도(Flow chart)를 이용한 도식화 표현

### 계산 문제

수학적으로 계산 가능하며, 컴퓨터를 이용해 풀 수 있는 모든 문제들을 의미한다.

* **결정 문제(decision problem)**
* 탐색 문제(search problem)
* 카운팅 문제(counting problem)
* **최적화 문제(optimization problem)**
* 함수형 문제(function problem)

### 결정 문제

계산 문제들 중 그 결과를 'YES' or 'NO'로 답할 수 있는 문제를 의미한다.

### 최적화 문제

계산결과 얻은 후보 해들 중 가장 적절한 해를 찾는 형태의 문제를 말한다.

### 성능분석

* 평가기준
  * 정확성 : 올바른 자료 입력 시 유한한 시간 내에 올바른 결과 출력 여부
  * 명확성 : 알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었는가
  * 수행량 : 일반적인 연산 제외, 알고리즘 특성상 나타내는 중요 연산 모두 분석
  * **실행시간, 메모리 사용량** => 측정가능
  * **최적성** : 가장중요
* 자료구조로 알고리즘을 완료하는데 얼마나 많은 시간과 공간이 필요한지에 따라 이 자료구조가 좋은지 나쁜지 평가할 수 있다.

#### 수행시간 측정

* 실행시간이 짧으면서 메모리 자원을 덜 사용하는 것이 효율적
* 일반적으로 **실행시간이 메모리 공간보다 더 중요시**

```c
#include <time.h>

void main(){
    clock_t start, end;
    double duration;
    start = clock();
    // 코드
    end = clock();
    duration = (double)(start - end) / CLOCKS_PER_SEC;
}
```

```python
import time
start_time = time.time() # 시간측정 시작

# program code

end_time = time.time() #시간측정 종료
print("time : ", end_time - start_time) # 수행시간 출력
```

수행시간을 측정하는 전형적인 프로그램이다. 하지만 소프트웨어 환경에 따른 실행속도의 차이와 데이터에 따른 전혀 다른 결과 등등의 문제점도 있다.

### 복잡도 분석

**알고리즘 효율성**을 계산량으로 표현할 것이며, 계산량은 입력크기 **n에 대한 실행시간**을 나타낸다.

* 어느 알고리즘이 가장 빠른가, 비용이 적게 드는가, 최적이라 볼 수 있는가
* 실행과 관계없이 **효율성**을 평가하자
* 직접 구현하지 않고서도 대략적인 수행 시간을 분석하는 방법
* 시간 복잡도(time complexity) : 알고리즘의 수행 시간 분석
  * 알고리즘을 이루고 있는 **기본 연산들이 몇 번이나 수행되는지**를 숫자로 표시(산술, 대입, 비교, 이동 등의 기본적인 연산)
  * 입력의 개수가 n일 때, 연산의 실행횟수는 n에 따라 변한다
  * 시간복잡도 T(n) → 입력의 개수 n에 대한 함수
  * 실제 실행시간 보다는 명령문의 실행 빈도수에 따라 계산
* 공간 복잡도(space complexity) : 알고리즘 수행시 필요로하는 메모리 공간 분석
  * 파이썬 공간 복잡도 주의 : 파이썬은 다른 언어에 비해서 구현상의 복잡함이 적은 편이지만 데이터 처리량이 많은 때는 꼭 메모리 제한을 고려하도록 해야한다.\
    리스트를 여러개 선언하고, 그중에서 크기가 1,000만 이상인 리스트가 있는 경우에는 메모리 제한을 고려해야한다.
  * **int 자료형 데이터의 개수에 따른 메모리 사용량**

    |    데이터의 개수    | 메모리 사용량 |
    | :-----------: | :-----: |
    |     1,000     |  약 4KB  |
    |   1,000,000   |  약 4MB  |
    | 1,000,000,000 |  약 40MB |

#### 성능 분석 표기법

* **빅오(O)표기법** : 연산의 횟수를 대략적(점근적)으로 표기하여 **함수의 상한**을 표시하기 위한 방법
* 궁극적으로 다항식의 최고차항의 차수만 사용한다.

```
f(n) = 5            //=> O(1)
f(n) = 2n+1         //=> O(n)
f(n) = 3n^2 +100    //=> O(n^2)
```

```
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(n^k) < O(2^n) < O(n!)
```

사실상 지수형이나 팩토리얼의 복잡도를 가지면 사용하는 것이 무의미하다.

* 빅오메가 : **함수의 하한**을 표시하기 위한 방법
* 빅세타 : 함수의 **하하인 동시에 상한**을 표시

#### 최선, 평균, 최악의 경우

* 최선의 경우 : 수행 시간이 가장 빠른 경우
  * 찾고자 하는 숫자가 맨 앞에 있음(O(1))
* **최악의 경우 : 수행 시간이 가장 늦은 경우**
  * 찾고자 하는 숫자가 맨 뒤에 있는 경우(O(n))
* 평균의 경우 : 수행시간이 평균적인 경우
  * 각 요소들이 균일하게 탐색 (O(n))

### 프로그래밍 대회를 위한 여섯 단계 문제 해결 알고리즘

1. **문제를 읽고 이해한다.**
2. **재정의와 추상화** 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할지 계획을 세운다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

## 실습

### C++

#### 입력을 모르는 경우

입력이 몇 개인지 주어지지 않은 경우가 있다.

```cpp
while(scanf("%d %d",&a,&b)==2)
// scanf의 리턴값은 성공적으로 입력받은 변수의 개수이다.
while(cin >> a >>b)
```

이렇게 입력을 EOF까지 받으면 된다.

#### 한 줄 입력받기

```cpp
fgets(s, 100, stdin);
//줄바꿈까지 입력 받는다.
scanf("%[^\n]\n", s);
// 줄바꿈을 입력받지 않기때문에 편리하다. 하지만 공백을 인식하지 않는다.
```

```cpp
#include <cstdio>
int main() {
    char c;
    while ((c = getchar()) && c != EOF) {
        printf("%c",c);
    }
    return 0;
}
```

while을 이용해서 입력을 받아 공백까지 그대로 출력할 수 있다.

#### 숫자입력받기

```cpp
scanf("%1d",a);
```

`%d`사이에 숫자를 넣으면 그 길이만큼 입력을 받는다.

#### typedef

C언어에서 **사용자 정의 데이터 타입**을 만드는 경우에 쓰이는 키워드이다. 타입을 새롭게 정의하는 것이 아닌, 이미 정의되어 있는 타입에 다른 타입을 부여하는 것이다.

```c
//typedef <type정의> <새로운 type 이름>

typedef int element;
typedef struct ListNode{
  element data;
  struct ListNode *link;
} ListNode;
```

### python

#### 입력받기

```python
input()
```

파이썬은 `input()` 으로 간단하게 입력 받을 수 있다. 이때 받는 값이 int여야한다면,

```python
int(input())
```

받는 값을 리스트로 매핑해야한다면

```python
list(map(int, input().split()))
```

다음과 같이 입력값을 다양하게 받아 올 수 있다.

#### 빠르게 입력받기

입력 데이터의 수가 많은 문제에 `input()` 핫무를 사용하면, 동작 속도가 느려 시간 초과로 오답 판정을 받을 수 있다.

```python
import sys

# 하나의 문자열 데이터 입력받기
# rstrip()은 줄바꿈 기호로 입력되는 것을 제거
input_data = sys.stdin.readline().rstrip()
```

다음과 같이 `sys` 라이브러리의 `readline()` 을 사용하는 것을 권장한다.

## 알고리즘 문제 풀이 사이트

* <https://codeup.kr/> : 난이도가 낮은 기본문제 풀이
* <https://programmers.co.kr/>