Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 선형회귀모델
- 화웨이라우터
- 한국데이터산업진흥원
- 라이프니츠 공식
- 가우스조던소거법
- lte라우터
- 김영평생교육원
- 정보처리기사 후기
- 메가존아이티평생교육원
- 머신러닝
- LU분해
- LU분해 알고리즘 구현
- 행렬식
- 행렬식의 정의
- LU분해 파이썬
- 선형대수학
- 여인수 전개
- 학사
- determinant
- 컴공수학
- 가우스조르당소거법
- 학점은행제
- 행렬식 파이썬
- 한국기술교육대학교
- 컴퓨터공학
- 원격평생교육진흥원
- 정규방정식
- 알고리즘
- 정보처리기사 기출
- 중간고사
Archives
- Today
- Total
gyeo-ri.com
[알고리즘] 점화식과 수열 알고리즘 본문
*한국기술대학교 원격평생교육원에서 수강중인 학점은행제 컴퓨터공학 학사 과정의 알고리즘 요약 자료(시험 대비)입니다.
점화식
- 명시적으로 자기 호출을 사용하지 않더라도 그 속에서 자신(n)과 똑같지만 크기가 다른(n-1) 문제를 발견할 수 있는 경우 재귀적 성질을 포함하는 알고리즘의 복잡도는 점화식을 이용하여 접근이 가능함
- 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현
점화식의 점근적 복잡도를 구하는 방법
- 반복 대치 : T(n)의 식을 T(1)이 될 때 까지 반복하여 치환함
- 추정 후 증명 : 귀납적으로 가설을 설정, 가설을 만족함을 증명
- 시간 복잡도(빅오표기법 등)의 증명 과정
- 마스터 정리 : 특정한 모양을 가진 재귀식에 대해 바로 결과를 알 수 있는 정리
- T(n) = aT(n/b) + f(n)
- 입력 크기가 n인 문제를 풀기 위해 입력 크기가 n/b인 문제를 a번 풀고 나머지 f(n)의 오버헤드가 필요한 알고리즘
- 제시된 형태의 재귀식이 아닌 경우에도 점화식의 변수를 치환하여 마스터 정리를 사용 가능하도록 변형할 수 있음
수열 알고리즘
- 등차수열 : 각 항마다 일정한 값을 더하는 수열
- 등비 수열 : 각 항마다 일정한 값을 곱하는 수열
- 피보나치 수열 : 1,1,로 시작하여, 바로 직전의 두 값(n-2+n-1)을 더한 값을 다음 값(n)으로 취하는 수열(1,1,2,3,5,8.....)
- 팩토리얼 수열 : 팩토리열(N!의 형태로 쓰며, 1부터 N까지의 곱을 의미) 1!, 2!, ~ N!까지의 합
- +,- 교행 수열 : 순서대로 한 번 더하고 한 번 빼는 수열
- +, - 교행 분수 수열 : 1/2*3 - 2/3*4 + 3/4*5 ... 와 같이 분수 형태로 숫자/부호가 순차적으로 등장하는 수열
- 숫자 변수, 분수 변수, 합계 변수, 스위치 변수가 알고리즘에 사용
'Study Note > 알고리즘' 카테고리의 다른 글
[알고리즘] 정렬 알고리즘 (0) | 2020.09.28 |
---|---|
[알고리즘] 복잡도와 점근적 표기법(빅오 표기법, 빅오메가 표기법, 세타 표기법) (0) | 2020.09.27 |
Comments