목록dev-log (167)
H-Log
점근적 표기 입력 크기(n)가 무한대로 커질 때의 복잡도를 간단히 표기하기 위한 표기법 보통은 다항식이나 간단한 함수로 표기 복잡도의 상한선을 표기 Big-Oh 충족 조건 cf(n) ≥ g(n) c > 0 n ≥ 1 타이트한 값으로 설정 cf(n^2)이나 cf(n^3)도 g(n) 보다 클테지만, 타이트한 cf(n)을 사용 다양한 표기법 Big-Oh : 상한선 오메가 : 하한선 세타 : 빅오-오메가 사이에 속하는 식
logn < n < nlogn < n^2 < n^3 < 2^n < n! 분석 입력 크기에 따라, 단위 연산이 몇 번 수행되는지 결정하는 절차 사용하는 자료구조에 좌우되는 경우도 있다. 표현 척도 단위 연산 : 비교 / 지정 입력 크기 : 배열의 크기 / 리스트의 길이 / 행과 열의 크기 / 트리의 노트와 연결선의 수 분석 방법 최선의 경우 (Best-case) : 단위 연산 수행 횟수가 최소인 경우 잘 안 쓴다. ex) 순차검색의 x가 제일 처음에 위치하면 T=1 최악의 경우 (Worst-case) 단위 연산 수행 횟수가 최대인 경우 대부분 최악의 경우로 구한다. ex) 순차검색의 x가 제일 마지막에 위치하면 T=n 평균의 경우(Average-case) (최선+최악)/2 로 계산 최악의 경우보다 계산이 ..
피보나찌 수 구하기 피보니찌 재귀 함수의 한계를 설명하기 좋음 n(n ≥ 2)의 피보나찌 = (n-2) + (n-1) 1. 재귀적 방법으로 피보나찌 수 구하기 n-1과 n-2의 값이 1 또는 0이 될 때 까지 fib 함수가 재귀적으로 호출된다. int fib(int n) { if (n 2 x T(n - 2) → 왜냐하면 T(n - 1) > T(n - 2) > 2^2 x T(n - 4) > 2^3 x T(n - 6) … 2n/2 x T(n-n) = 2n/2xT(0) = 2^n/2 결론 재귀적 알고리즘으로 구성한 재귀 트리의 노드 수를 T(n)이라 하면, n2인 모든 n에 대하여 T(n)> 2n/2 이다. ⇒ 매우 느림 이유: 같은 피보나찌 수를 중복 계산 2. 반복적 방법으로 피보나찌 수 구하기 int ..
예제 : 임의의 수 x 찾기 문제: 크기가 n인 배열 S에 x가 있는가? 입력(파라미터): (1) 양수 n, (2) 배열 S[1..n], (3) 키 x 출력: x의 위치, 만약 없으면 0. 알고리즘(자연어): x와 같은 원소를 찾을 때까지 S에 있는 모든 원소를 차례로 검사한다. 만일 x 와 같은 원소를 찾으면 S 에서의 그 위치를, S 를 모두 검사하고도 찾지 못하면 0을 내준다 1. 순차 탐색 void seqsearch(int n, // 입력(1) const keytype S[], // (2) keytype x, // (3) index& location) { // 출력 location = 1; while (location n) location = 0; } while-루프: 아직 검사할 항목이 있고, ..
알고리즘 문제에 대한 해답을 찾기 위한 체계적인 “문제 해결 절차” 항상 “효율적인 알고리즘”을 고안하는게 중요 최초의 알고리즘 : 유클리드의 최대공약수 알고리즘의 특성 정확성 : 주어진 입력에 대한 올바른 해 도출 수행성 : 각 단계는 컴퓨터에서 수행 가능해야 한다. 유한성 : 무한루프X, 단계를 마친 후 종료되어야 한다. 효율성 : 효율적일수록 가치가 높아진다 효율성의 척도 : 시간 복잡도 / 공간 복잡도 정확한 알고리즘 : 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘 정확하지 않은 알고리즘 : 어떤 입력에 대하여 멈추지 않거나 틀린 답을 출력하면서 멈추는 알고리즘 문제의 표기 방법 문제 파라미터 : 문제에서 특정 값이 주어지지 않은 변수 문제의 사례 (입력) : 파라미터에 특정 값 지정 ..
테스트 코드 위치 : myApp/tests.py 테스트 명령어 Beautifulsoup4 필요 pip install beautifulsoup4 python manage.py test 테스트 코드 같은지 / 같지 않은지 assertEqual(a, b) : a == b assertNotEqual(a, b) : a ≠ b 참인지 / 거짓인지 assertTrue(a) : a == True assertFalse(a) : a == False 맞는지 / 맞지 않은지 assertIs(a, b) : a is b assertIsNot(a, b) : a is not b None인지 / None이 아닌지 assertIsNone(a) : a is None assertIsNotNone(a) : a is not None 안에 있는..