알고리즘

Juhwan Lee·2022년 3월 12일

알고리즘은 구현을 많이 해봐야 는다.
1. 전체적인 구조를 파악한다.
2. 스스로 구현을 해보자 (백지에서 직접 작성을 해보자)
3. 하루에 16시간-18시간 투자하자

❓알고리즘이란?

: 똑같은 상황일때 문제를 푸는 순서를 조금 달리하거나 조금 더 효율적인 방법을 사용하여 시간을 기하급수적으로 줄이도록 노력하는 방법론

ex) 램? 메모리
최하상황(클라이언트)을 가정하고 코딩.
어떻게하면 메모리를 가장 적게쓰면서 코딩을 할까?    
시간 복잡도(연산 횟수), 공간 복잡도(메모리)를 낮춰서
문제를 풀 수 있는지 알아보는 것.

❗ for문이 중첩되면 문제가 있는지 무조건 확인하자!
👉분명히 방법이 있다.

빅오(Big-O: 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지) (O)

빅 오메가(Big-Ω: 최선의 성능이 나올때 어느 정도의 연산량이 걸릴 것인지) (X)

❗우리는 다음만 기억하면 됩니다.

입력값에 비례해서 얼마나 늘어날지 파악해보자.
$1$ ? $N$ ? $N^2$ ?

공간복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민하자.

최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민하자
C로 푸는게 아니라면 공간복잡도를 고려하는 경우가 흔치 않다.

💡`시간 복잡도`란?

입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말합니다! 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이죠.

우리는 시간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?

💡`공간 복잡도`란?

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말합니다! 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것이죠.
우리는 공간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?

파이썬 알고리즘 인터뷰

Chapter4. 빅오, 자료형

빅오
- O(1): 입력값이 아무리 커도 실행 시간은 일정하다. 최고의 알고리즘
- O(log n): 웬만한 n의 크기에 대해서도 매우 견고하다. 대표적으로 ‘이진 검색’
- O(n log n): 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘
- O( $n^2$ ): 버블 정렬 같은 비효율적인 정렬 알고리즘
- O( $2^n$ ): 피보나치 수를 재귀로 계산하는 알고리즘
- O( $n!)$ : 가장 느린 알고리즘

빅오 표기법은 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다.

파이썬 자료형
1. 숫자: 정수형으로 int만을 제공함. bool은 논리 자료형인데 파이썬에서 내부적으로 1(True)과 0(False)으로 처리되는 int의 서브 클래스
  object > int > bool
```
```python
  >>> True == 1
  True
  >>> False == 0
  True
```
```
2. 매핑: 키와 자료형으로 구성된 복합 자료형, 파이썬에 내장된 유일한 매핑 자료형은 딕셔너리이다.
3. 집합: set은 중복된 값을 갖지 않는 자료형
```
>>> a = set()
>>> a
set()
>>> type(a)
<class 'set'>

# 빈 집합이 아닌 값이 포함된 집합을 선언할 때는 a = {1,2,3} 형태로 하는데, 
# 집합은 딕셔너리와 동일하게 중괄호({})를 사용하므로 이 점에 유의해야 한다.

>>> a = {'a','b','c'}
>>> type(a)
<class 'set'>
>>> a = {'a':'A', 'b':'B','c'='C'}
>>> type(a)
<class 'dict'>
```
  set은 입력 순서가 유지되지 않으며, 중복된 값이 있을 경우 하나의 값만 유지한다.
4. 시퀀스: ‘수열’과 같은 의미. 파이썬에서는 list라는 시퀀스 타입이 배열의 역할을 수행한다. str은 변경할 수 없으며, 불변이다. 반면 list는 가변이다.