삶은 감자

03. 점화식과 점근적 복잡도 분석 1. 점화식 : 어떤 함수를 자신과 똑같은 함수를 이용해 나타내는 것 예) 등차수열, 피보나치 수열, n!재귀함수의 복잡도를 구하는데 유용 (알고리즘의 수행시간을 점화식으로 표현 가능) 2. 점화식으로 표현된 식의 점근적 복잡도를 구하는 방법 : 반복 대치, 추정 후 증명, 마스터 정리 3. 반복 대치 : 더 작은 문제에 대한 함수로 반복해서 대치해서 계산하는 방법직관적이긴 한대 길어지면 복잡해짐 4. 추정 후 증명 : 결론을 먼저 추정하고 수학적 귀납법으로 옳은지 증명하는 방법 유의 사항 직관적이지 않을 때가 있음 (경험 필요) 추정을 의미있게 해야함 점화식의 모양에 익숙해져야한다 -> 마스터 정리 이용 5. 마스터 정리 : 형식에 맞는 점화식의 복잡도를 바로 알 수..

02. 알고리즘 설계와 분석의 기초 알고리즘의 표현 - 의사코드 pseudo code 프로그램 작성 시 각 모듈이 작동하는 논리를 표현하기 위한 언어 일반적인 언어로 프로그래밍 코드와 유사하게 표현 알고리즘 표현 or 모델링에 사용 점근적 분석 : 입력 크기가 클 때 분석 방법 변수가 커짐에 따라 함수가 증가하는 비율을 표현하는 방법 무한을 간단하게 표기 Big O, theta, omega Big O notation 최악의 경우 소요되는 시간 계수와 상수는 버림. 차수만 중요 세타 표기법 : 점근적 증가율이 f(n)과 일치하는 모든 함수 집합 (평균) 빅오 표기법 : 점근적 증가율이 f(n)을 넘지 않는 모든 함수 집합 (상한) 오메가 표기법 : 점근적 증가율이 적어도 f(n)이 되는 모든 함수 집합 (..

01. 알고리즘 개요 알고리즘 : 문제해결을 위한 방법을 수학적 명령이나 규칙의 집합으로 표현한 것 알고리즘의 효율 문제해결 관점 : 최소시간 방법의 기술 관점 : 결과물이 같아도 방법이 서로 다름 -> 가장 빠른 방법이 가장 효율적이다 알고리즘: 명확(프로그래밍 언어로 변환 용이)하고 효율적(처리 시간,공간(메모리))이어야함 소요시간을 얼마나 소모하는가 : 최악, 평균... 데이터 양에 따라 대략적으로 얼마나... 알고리즘의 수행시간 상수 시간 : n의 크기와 상관 없이 일정한 시간 소요 선형 시간 : n의 크기에 비례하여 수행 시간 증가 제곱 시간 : n의 제곱에 비례하여 수행 시간 증가 재귀 호출 : 예시; 팩토리얼 구하기 n에 비례해서 증가어떤 문제 안에 크기만 다른 같은 문제들이 포함되기도 함 ..