오식랜드

피보나찌 수 구하기 피보니찌 재귀 함수의 한계를 설명하기 좋음 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)이라 하면, n2인 모든 n에 대하여 T(n)> 2n/2 이다. ⇒ 매우 느림 이유: 같은 피보나찌 수를 중복 계산 2. 반복적 방법으로 피보나찌 수 구하기 int ..

logn < n < nlogn < n^2 < n^3 < 2^n < n! 수행시간을 좌우하는 기준 for 루프 반복 횟수 함수의 호출 횟수 특정 행의 수행 횟수 *n = A[] 배열의 원소 수 상수시간 n 데이터 개수 n일때, n에 비례하는 시간이 소요됨 n의 수가 증가할수록 오래걸림 sample1(A[ ], n) { k = ; return A[k] ; } sample2(A[ ], n) { sum ← 0 ; for i ← 1 to n sum← sum+ A[i] ; return sum ; } n^2 n2에 비례하는 시간이 소요 sample3(A[ ], n) { sum ← 0 ; for i ← 1 to n for j ← 1 to n sum← sum+ A[i]*A[j] ; return sum ; } sample..

예제 : 임의의 수 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 안에 있는..

1. 변수 : {{ }} 2. 코멘트 : {# #} 혹은 {% comment %} {% endcomment %} 3. 태그 : {% %} ({% for i in myData %} {% endfor %} 4. 필터 : {{ i.text | truncatechars:10 }} --> 10글자 까지만 보여주는 필터