강의노트/자료구조론 (3) 썸네일형 리스트형 [자료구조론] 2주차: 순환 순환(Recursion) 정의 자체가 순환적인 경우 적합하다. 주어진 문제를 더 작은 동일한 문제로 분할해 해결(분할 정복: Divide and Conquer) Ex) Factorial $n!$은 $n \geq 1$에 대해서는 $n(n-1)!$, $n = 0$에 대해서는 1로 정의할 수 있다. 1 2 3 4 int factorial(int n) { return (n $O(n)$ 순환의 경우 대략 $x^n$에 대해 $n=2^k$라 하면 $k$번의 계산 필요 즉 $\log_{2}{n}$번의 연산을 요하므로 $O(\log{n})$ 1 2 3 4 5 6 7 8 9 10 int power(int x, int n) { if (n == 0) return 1; else { return (n % 2 == 0) ? pow.. [자료구조론] 2주차: Notation Big-O notation 입력의 개수 $n$에 따른 함수의 상한을 표시한 것 수학적 정의 두 함수 $f(n)$과 $g(n)$이 주어졌을 때, 모든 $n \geq n_0$에 대해 $\mid f(n)\mid\; \leq \; c\mid g(n) \mid$ 을 만족하는 상수 $c$, $n_0$ 가 존재하면 $f(n) = O(g(n))$이다. $n$이 어느 정도 커졌을 때 $f(n)$이 $g(n)$보다 항상 작으면 $g(n)$은 $f(n)$보다 연산 횟수가 큰 상한이라는 얘기다. 기본 연산 횟수가 다항식일 경우 최고차항만 사용 $8n^2\log{n} + 5n^2 + n$ -> $O(n^2\log{n})$ $10$ -> $O(1)$ $O(1) < O(\log{n}) < O(n) < O(n\log{n}) < O(.. [자료구조론] 1주차 자료구조(Data structure): 컴퓨터에서 데이터를 보관하는 구조 알고리즘(Algorithm): 주어진 문제를 풀기 위한 단계적인 절차(procedure) 프로그램 = 자료구조 + 알고리즘 문제 해결을 위해 적절한 자료구조를 선택하고, 이 자료구조를 사용하는 효율적인 알고리즘 작성이 필요하다. 알고리즘의 조건 입력과 출력: 입력은 없어도 되지만 출력은 반드시 존재해야 한다. 명백성(Definiteness): 모든 명령어는 모호해서는 안 된다. 유한성(Finiteness): 반드시 종료되어야 한다. 유효성(Effectiveness): 모든 명령어는 실행가능해야 한다. 추상 자료형(Abstract data type) 자료형 데이터의 종류 데이터의 집합과 연산의 집합: 연산(operation)에는 함수.. Prev 1 Next