[수학] 1. Overview
1. 알고리즘 복잡도 (시간 복잡도)
- 입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여, 알고리즘의 수행시간을 평가하는 방법
- 3가지 점근적 표현법
- O 빅오 :
최악의 상황을 고려하여 성능 측정 결과 표현 👍 - Θ 세타 :
평균적인 경우에서의 성능 측정 결과 표현 - Ω 오메가 :
최선의 상황일 때의 성능 축정 결과 표현
2. 경우의 수
- 어떤 사건 혹은 일이 일어날 수 있는 경우의 가짓수를 수로 표현
일상 생활에서의 경우의 수
- 주사위 : 던지는 결과, 1~6 사이의 숫자이므로 경우의 수는 6
- 윷 : 던지는 결과, 도, 개, 걸, 윶, 모 이므로 경우의 수는 5
- 가위바위보 : 게임 결봐, 가위, 바위, 보 중에 하나를 낼 수 있으므로 경우의 수는 2
- 동전 : 던지는 결과, 앞면 혹은 뒷면이르모 경우의 수는 2
완전 탐색으로 경우의 수를 푸는 알고리즘
- 순열 : 서로 다른 n개의 원소 중에서 r을
중복 없이골라순서에 상관 있게나열하는 경우의 수nPr - 조합 : 서로 다른 n개의 원수 중에서 r을
중복 없이골라순서에 상관 없이나열하는 경우의 수nCr - 중복 순열 : 서로 다른 n개의 원소 중에서 r개를
중복 있게 골라 순서에 상관 있게나열하는 경우의 수nH
3. 점화식
- 점화식(재귀식) : 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식
- 등차 수열 :
F(n) = F(n-1) + a - 등비 수열 :
F(n) = F(n-1) * a - 팩토리얼 :
F(n) = F(n-1) * n - 피보나치 수열 :
F(n) = F(n-1) + F(n-2)
나의 회고 🤫
나는 코드로 구현할 때 점화식은 이해가 가는데 순열과 조합은 정말 너무 어려웠다…
이번 공부를 통해 순열과 조합 공포증에서 벗어나도록 열공해보자!!
