우선순위 큐우선순위 큐에서는 데이터들이 우선 순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나가게 된다. 우선순위 큐 ADT객체: n개의 element형의 우선 순위를 가진 요소들의 모임연산: create() ::= 우선순위 큐를 생성한다. init(q) := 우선순위 큐 q를 초기화 한다. is_empty(q) ::= 우선순위 큐 q가 비어있는지를 검사한다. is_full(q) ::= 우선순위 큐 q가 가득 찼는가를 검사한다. insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가한다. delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다. find(q) ::= 우선순위가 가장 높은 요소를 반환한다. 우선순위..
CS/자료구조
해싱해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다.해시테이블: 키에 대한 연산에 의해 직접 접근이 가능한 구조해싱: 해시테이블을 이용한 탐색 이상적인 해싱 알고리즘add(key, value): index 실제로는 해시 테이블의 크기가 제한되어 있으므로 하나의 키당 해시테이블에서 하나의 공간을 할당할 수가 없다.mod를 사용하자h(k) = k mod M 충돌과 오버플로우충돌: 서로 다른 키를 갖는 항목들이 같은 해시주소를 가지는 현상오버플로우 발생: 충돌이 발생하고, 해시 주소에 더 이상 빈 버킷이 남아 있지 않으면 발생해결법:개방 주소법 : 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장체이닝: 해시 테이블의 하나의 위치가 여러 개의 항목을 ..
순차탐색int seq_search(int key, int low, int high){ int i; list[high + 1] = key; for (i = low; list[i] != key; i++) //키 값을 찾으면 종료 ; if (i == (high + 1)) return -1; // 탐색 실패 else return i; // 탐색 성공} 이진탐색정렬된 배열의 탐색에 적합함배열의 중앙에 있는 값을 조사하여, 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다.search_binary(list, low, high): middle list[middle]) return list[middle + 1]부터..
정렬대상을 크기순으로 오름차순이나 내림차순으로 나열하는 선택 정렬 알고리즘selection_sort(A, n):for i 삽입 정렬 알고리즘insertion_sort(A, n):for i = 0 and A[j] > key do A[j + 1] 버블 정렬 알고리즘BubbleSort(A, n):for i 합병 정렬 알고리즘merge_sort(list, left, right):if left merge(list, left, mid, last):i 기수 정렬 알고리즘RadixSort(list, n):for d
그래프그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조다.대표적인 예는 지하철 노선도가 있다. 개인적으로 대단하다고 생각하고 있다. 그래프의 정의와 용어정점(vertex): 위치라는 개념. (node라고도 부름)간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch라고도 부름)인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의..
트리트리는 계층적인 자료를 표현하는데 적합한 자료구조이다. 트리의 용어노드(node) : 트리를 구성하는 기본 원소노드 (root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드형제 노드(siblings node): 같은 부모 노드를 갖는 노드들리프 노드(leaf node/leaf): 루트 노드를 제외한 차수가 1인 정점을 뜻한다. 쉽게 말해 자식이 없는 노드. 단말 노드라 부르기도 한다.경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서길이(length): 출발 노드에서 도착 노드까지 거치는 간선의 개수..
리스트리스트는 자료를 정리하는 방법 중의 하나로 To_Do_List와 같은 형식을 사용한다. 리스트 ADT객체: n개의 element형으로 구성된 순서 있는 모임연산: insert(list, pos, item) ::= pos 위치에 요소를 추가한다. insert_last(list, item) ::= 맨 끝에 요소를 추가한다. insert_first(list, item) ::= 맨 처음에 요소를 추가한다. delete(list, pos) ::= pos 위치의 요소를 제거한다. clear(list) ::= 리스트의 모든 요소를 제거한다. get_entry(list, pos) ::= pos 위치의 요소를 반환한다. get_length(list) ::= 리스트의 길이를 구한다. ..
큐컴퓨터의 기본 자료구조 중 하나로 먼저 들어온 데이터가 먼저 나가는 구조로 되어 있습니다. 즉, FIFO(First-In First-Out) 선입선출.한쪽에서는 데이터가 추가되고 한쪽에서는 데이터가 삭제되는 구조를 가지고 있음 큐 ADT객체: 0개 이상의 요소들로 구성된 선형 리스트연산: create(max_size) ::= 최대 크기가 max_size인 공백큐를 생성한다. init(q) ::= 큐를 초기화한다. is_empty(q) ::= if(size == 0) return TRUE; else return FALSE; is_full(q) ::= if(size == max_size) return TRUE; else return FALSE..
스택 스택은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 제한적으로 접근할 수 있는 후입선출(Last-In-First-Out) 형태의 선형 자료구조이다. 스택 상단 : 스택에서 입출력이 이루어지는 부분 스택 하단 : 스택의 바닥 부분 요소 : 스택에 저장되는 것 공백 스택 : 스택에 요소가 없는 상태 스택의 is_empty 연산 is_empty(S): if top == -1 then return TRUE else return FALSE 스택의 is_full 연산 is_full(S): if top >= (MAX_STACK_SIZE-1) then return TRUE else return FALSE 스택의 push 연산 push(S, x): if is_full(S) then error "overflow" els..
순환순환(recursion)이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법ex) 팩토리얼, 피보나치, 이항계수 계산, 이진 탐색, DFS... 내부적인 구현복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수와 지역 변수를 스택으로부터 할당받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드라 한다. 순환 알고리즘의 구조자기 자신을 순환적으로 호출하는 부분과 순환 호출을 멈추는 부분으로 구성되어 있다. 순환의 원리주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법으로 분할정복(divide and conquer)이라 한다.순환호출이 일어날 때마다 문제의 크기가 작아진다.문제의 크기가 점점 작아지면 풀기가 쉬워지고 결국은 풀기 쉬운 문제가..
자료구조: 자료들을 정리하여 보관하는 구조 -> 스택 큐 등등 프로그램프로그램 = 자료구조 + 알고리즘ex) scores[] + for i 알고리즘입력 : 0개 이상의 입력이 존재하여야 한다.출력 : 1개 이상의 출력이 존재하여야 한다.명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.유효성 : 각 명령어들은 종이와 연필, 또는 커퓨터로 실행가능한 연산이어야 한다.
빅오 표기법 * 두개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n0에 대하여 |f(n)|n0에 대하여 c|g(n)|
