티스토리

FL4G{##st4rbuucks##}

검색하기

블로그 홈

FL4G{##st4rbuucks##}

story.st4rbuucks.kr/m

st4rbuucks 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

07 해시 테이블 해시 테이블 : 원소의 값에 의해 원소가 저장될 위치를 결정 즉, 단 한 번의 계산으로 자신의 자리를 찾기가 가능 해시 함수의 성질 1. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. 2. 계산이 간단해야 한다. 1. Division Method $h(x) = x mod m$ m: table size, 보통 prime number 2. Multiplication Method $h(x) = (xA mod 1) * m$ 0 < A < 1 : constant m은 굳이 소수일 필요가 없다. 보통 $2^p$로 설정 충돌(Collision) 해결 1. Chaining 같은 주소로 해싱되는 원소들을 모두 하나의 연결 리스트에 매달아서 관리 저장할때는 head에 연결하는 것이 효율적, 검사할때는 해당 연결리.. 공감수 0 댓글수 1 2018. 10. 21.
06 검색 트리 record : 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위 field : 레코드에서 각각의 정보를 나타내는 부분 search key / key : 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 (하나 또는 두개이상) search tree : 각 노드가 규칙에 맞게 하나씩의 키를 가지고 있고 이를 통해 해당 레코드가 저장된 위치를 알 수 있다. 트리의 자료구조 : 배열 또는 포인터를 이용한 구조체 Binary Search Tree (BST) 1. 각 노드는 서로 다른 키 값을 하나씩 갖는다. 2. 최상위 레벨에 루트 노드가 있고 각 노드는 최대 두 개의 자식 노드를 갖는다. 3. 임의의 노드의 키 값은 자신의 왼쪽에 있는 모든 노드의 키 값보다 크고, 오른쪽에 있는 모든 노.. 공감수 0 댓글수 0 2018. 10. 21.
05 선택 알고리즘 평균 선형 시간 선택 알고리즘select(A, p, r, i) { if (p=r) then return A[p]; q ← partition(A, p, r); k ← q-p+1; if (i 공감수 0 댓글수 0 2018. 10. 21.
04 정렬 (2) 힙 정렬 (Heap Sort)buildHeap(A[], n) { for i ← n/2 downto 1 heapify(A, i, n); } heapify(A[], k, n) { left ← 2k; right ← 2k+1; if (right ≤ n) then { if (A[left] < A[right]) then smaller ← left; else smaller ← right; } else if (left ≤ n) then smaller ← left; else return; if (A[smaller] < A[k]) then { A[k] ↔ A[smaller]; heapify(A, smaller, n); } } heapSort(A, n) { buildHeap(A, n); for i ← n downto 2 {.. 공감수 0 댓글수 0 2018. 10. 21.
04 정렬 (1) 선택 정렬 (Selection Sort)selectionSort(A[n], n) { for last ← n downto 2{ A[1…n] 중 가장 큰 수 A[k]를 찾는다; A[k] ↔ A[last]; } } 선택 정렬의 수행 시간은 모든 경우에 $\Theta(n^2)$ 버블 정렬 (Bubble Sort)bubbleSort(A[], n) { for last ← n downto 2 for i ← 1 to last-1 if (A[i] > A[i+1]) then A[i] ↔ A[i+1]; } 버블 정렬의 수행 시간은 $\Theta(n^2)$ 중간에 정렬이 완료될 경우, 무의미한 순환을 멈추기 위한, 변형된 버블 정렬bubbleSort2(A[], n) { for last ← n downto 2{ sorted ←.. 공감수 0 댓글수 0 2018. 10. 21.
03 점화식과 알고리즘 복잡도 분석 점화식의 분석 방법 1. 반복대치 더 작은 문제에 대한 함수로 반복해서 대치해 나가는 해법 2. 추정 후 증명 결론을 추정하고 수학적 귀납법을 이용하여 증명하는 방법 $T(n) \le 2T(n/2) + n$ 추정 : $T(n)=O(nlogn)$, 즉 충분히 큰 $n$에 대하여 $T(n) \le cnlogn$인 양의 상수 $c$가 존재한다. induction base : $T(n) \le c \cdot 2log2$를 만족하는 $c$가 존재한다. induction hypothesis와 전개 : $n/2$에 대해 $T(n/2) \le c \cdot (n/2) \cdot log(n/2)$을 만족한다 가정하면, $$\begin{align}T(n) &\leq 2T(n/2) + n \\ &\leq 2c(n/2)log.. 공감수 0 댓글수 0 2018. 10. 20.
02 알고리즘 설계와 분석의 기초 recursion : 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 접근하는 방식 ex) 하노이의 탑 Hanoi(n, from, temp, to) { if n = 1 then print("move ring on" from "to" to); if n > 1 then { Hanoi(n-1, from, to, temp); Hanoi(1, from, temp, to); Hanoi(n-1, temp, from, to); } } induction method : 자신보다 작은 문제에 대해 결론이 옳음을 가정하고 자신과 이 작은 문제의 관계를 통해서 자신에게도 결론이 옳음을 보이는 것 ex) 하노이의 탑 원판 이동 횟수 H(n) : 하노이 탑 원판 .. 공감수 0 댓글수 2 2018. 10. 19.
01 알고리즘이란 알고리즘 : 문제 해결 과정을 (논리적으로) 묘사하는 것 알고리즘의 속성 5가지 입력 (0개 이상) 출력 (1개 이상) 명확성 : 모든 사람이 똑같이 이해하도록 명확하게 서술되어야 함 효율성 : 각 과정이 하나하나 tracing이 가능해야 함 종료성 (항상 출력을 얻을 수 있다) +) 종료되지 않는 프로그램? -> Procedure -> Reactive software 공감수 0 댓글수 5 2018. 10. 18.
[쉽게 배우는 알고리즘] 책소개 한 학기동안 이 책으로 알고리즘에 대해 공부하게 되었다. 그렇게 어려워 보이지도 않고 재밌게 공부할 수 있을 것 같다. 목차 01 알고리즘이란 02 알고리즘 설계와 분석의 기초 03 점화식과 알고리즘 복잡도 분석 04 정렬 05 선택 알고리즘 06 검색 트리 07 해시 테이블 08 집합의 처리 09 동적 프로그래밍 10 그래프 11 그리디 알고리즘 12 문자열 매칭 13 NP-완비 14 상태 공간 트리의 탐색 공감수 0 댓글수 0 2018. 10. 18.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.