[알고리즘] 1주차 정리

알고리즘

• 알고리즘은 문제를 해결하기 위한 여러 방법들의 집합이다

시간복잡도

• 시간복잡도는 입력값과 문제를 해결하는데 걸리는 시간과의 상관관계이다
  • 입력값의 길이를 N이라고 했을때, 그에 따라 얼마나 비례해서 증가하는지를 측정해야 한다

공간복잡도

• 공간복잡도는 공간과의 상관관계이다

점근 표기법

• 알고리즘의 성능을 수학적으로 표기하는 방법이다
• 알고리즘의 효율성을 평가하는 방법이다

종류

1. 빅오(Big-O)표기법
   • 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기
2. 빅 오메가(Big-Ω) 표기법
   • 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기

표현

• 빅오 표기법
  • O(N)의 시간복잡도를 가진 알고리즘이다
• 빅 오메가 표기법
  • Ω(1)의 시간복잡도를 가진 알고리즘이다

메모

• 빅 오메가(Big-Ω) 표기법은 최선의 경우! 그러나 현실에서 잘 적용이 안 되므로 거의 알고리즘의 성능을 빅오표기법으로 측정한다.
• 빅오(Big-O)표기법은 최악의 경우! 입력값에 비례해서 어느 정도 반복이 될지 감이 오면, 상수를 제거한 채 표현하면 된다.

정리

1. 규칙을 파악하는 것이 중요
2. 입력값에 비례해서 얼마나 늘어날지를 파악하자 - 1, N, N^2....
3. 공간복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민하자
4. 최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민하자
5. 알고리즘 문제가 이해가지 않을때 아래의 방법들을 사용해 문제에 대해 더 깊게 파악한다면 풀이방법을 떠올릴 수 있다
   1. 바로 코드를 작성하지 말고, 문제의 다른 예시들을 떠올리면서 규칙성을 생각해보자
   2. 배웠던 자료구조를 활용하면 어떨지 생각해보자
   3. 문제의 특징을 하나하나 글로 써보자
6. 파이썬 문법
   • 해당 문자가 알파벳인지 확인하는 방법 str.isalpha()
   • 문자를 아스키 코드로 바꾸는 방법 ord('a')
   • 아스키 코드를 문자로 바꾸는 방법 chr(97)
   • 0이 26개만큼 초기화 된 배열 만들기 [0] * 26
   • 알파벳을 숫자 인덱스로 만들기 ord(char) - ord('a')