본문 바로가기

[Basic] Data43

[Algorithm] 기본 수학 이론 - 점화식 점화식 (= 재귀식) 점화식(재귀식) 이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 대표적인 점화식 *a : 고정된 상수 등차 수열 : 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) ex) 등차 수열_재귀 let result; function recursive(s, t, number) { if (number == 1) return s; return recursive(s, t, number - 1) + t; } result = recursive(3, 2, 5); console.log(result); // output : 11 ex.. 2023. 2. 13.
[Algorithm] 기본 수학 이론 - 경우의 수 [순열, 조합] 경우의 수 어떤 사건 혹은 일이 일어날 수 있는 경우의 거짓수를 수로 표현 일상 생활에서의 경우의 수 주사위 : 던지는 결과, 1 ~ 6 사이의 숫자이므로 경우의 수는 6 윷 : 던지는 겨과, 도, 개, 걸, 윷, 모 이므로 경우의 수는 5 가위바위보 : 게임 결과, 가위, 바위, 보 중에 하나를 낼 수 있으므로 경우의 수는 3 동전 : 던지는 결과, 앞면 혹은 뒷면이므로 경우의 수는 2 완전 탐색으로 경우의 수를 푸는 알고리즘 순열 : 서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수 (nPr) 조합 : 서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수 (nCr) 중복 순열 : 서로 다른 n개의 원소 중에서 r개를 중복 있게.. 2023. 2. 13.
[Algorithm] 기본 수학 이론 - 알고리즘 복잡도 코딩테스트 할 때는 가장 중요시 여겨야 할 것 메모리 사용량, 효율성(시간 복잡도, 공간 복잡도) 이다. 시간 복잡도 입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여, 알고리즘의 수행시간을 평가하는 방법 3가지 점근적 표현법 O(빅오) : 최악의 상황을 고려하여 성능 측정 결과 표현 Θ(세타) : 평균적인 경우에서의 성능 측정 결과 표현 Ω(오메가) : 최선의 상황일 때의 성능 측정 결과 표현 아무래도 컴퓨터 프로그래밍쪽에서는 빅오 표기법이 널리 사용된다. 왜냐하면, 알고리즘의 평균적인 시간은 의미가 없는 경우가 많기 때문이다. 함수가 평균적으로 "대충 이정도 시간이 걸릴꺼야!" 보다 "절대로 이 시간 이상은 넘지 않을거야!" 라고 말하는 것이 신뢰도가 높고, 최악의 상황을 제일 고려해야 .. 2023. 2. 13.

티스토리툴바