dew's CSE Studying

14.1 해싱이란?-키값 비교로써 탐색하고자 하는 항목에 접근-해싱(hashing): 키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산하여 항목에 접근-어떤 항목의 키만을 가지고 바로 항목이 들어 있는 배열의 인덱스를 결정-해시 테이블: 키 값의 연산에 의해 직접 접근이 가능한 구조14.2 추상 자료형 사전사전의 개념사전(dictionary): (키,값)쌍의 집합 (=맵, 테이블)키(key): 사전의 단어처럼 항목과 항목을 구별시켜주는 것값(value): 단어의 설명에 해당한다-오직 키에 의해서 관리된다리스트: 위치에 의하여 관리 사전의 연산add, delete, search 14.3 해싱의 구조해시함수(hash function)-탐색키를 입력받아 해시주소 생성-이 해시주소가 배열로 구현된 해시테이..

13.1 탐색이란?탐색(search): 여러 개의 자료 중에서 원하는 자료를 찾는 작업-탐색의 단위: 항목(숫자일 수도, 구조체일 수도)키(key): 항목과 항목을 구별 = 탐색키(search key)=>탐색이란 탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는 것 13.2 정렬되지 않은 배열에서의 탐색순차 탐색순차 탐색(sequential search): 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법  ex: 탐색값과 일치하는 항목을 찾을 때까지 리스트의 앞부터 순차탐색 개선된 순차 탐색=>비교횟수를 1/2로 줄여보자!int seq_search2(int key, int low, int high){ int i;..

12.1 정렬이란?정렬(sorting): 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것 구조레코드(record): 정렬시켜야 될 대상필드(field): 레코드의 나누어진 단위(ex. 이름, 학번, 주소, 전화번호)키(key): 레코드와 레코드를 식별해주는 역할을 하는 필드(ex. 학번 필드->학생을 구별해줌)"정렬이란 결국 레코드들을 키값의 순서로 재배열하는 것!" 정렬 알고리즘단순하지만 비효율적인 방법 - 삽입 정렬, 선택 정렬, 버블 정렬 등복잡하지만 효율적인 방법 - 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬 등-자료의 개수가 일정 개수를 넘어가면 반드시 효율적인 알고리즘을 사용해야 한다 내부 정렬(internal sorti..

11.1 최소 비용 신장 트리신장 트리신장 트리(spanning tree): 그래프 내의 모든 정점을 포함하는 트리 1.모든 정점들이 연결되어 있어야 하고2.사이클을 포함해서는 안된다=>그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다 -깊이우선/너비우선 탐색 도중 사용된 간선들만 표시하면 만들 수 있다-그래프의 최소 연결 부분 그래프최소: 간선의 수가 가장 적다(최소 n-1개의 간선)-통신 네트워크 구축에 많이 사용-각 링크의 구축 비용이 같지 않기 때문에 가장 적은 링크만 사용한다고 해서 최소 비용이 얻어지는 것은 아니다  최소 비용 신장 트리최소 비용 신장 트리(MST: minimum spanning tree): 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 ..

10.1 그래프란?그래프의 소개그래프(graph): 객체 사이의 연결 관계를 표현한 수 있는 자료구조 그래프의 역사오일러(Euler)-Konigsberg의 다리 문제 해결 1736 10.2 그래프의 정의와 용어그래프의 정의그래프: 정점(vertex)과 간선(edges)들의 유한집합G=(V,E)V(G): 그래프 G의 정점들의 집합E(G): 그래프 G의 간선들의 집합 정점(=노드): 여러 가지 특성을 가질 수 있는 객체간선(=링크): 이러한 정점들 간의 관계V(G1) = {0, 1, 2, 3}E(G1) = {(0,1), (0,2), (0,3), (1,2)} 무방향 그래프와 방향 그래프무방향 그래프(undirected graph): 간선을 통해서 양방향으로 갈 수 있음 (A,B)=(B,A)방향 그래프(dire..

9.1 우선순위 큐 추상 데이터 타입우선순위 큐의 소개우선순위 큐의 사용: 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영체제에서의 작업 스케쥴링, 수치 해석적인 계산 등우선순위 큐는 배열, 연결리스트 등 여러 가지 방법으로 구현이 가능한데 우리는 가장 효율적인 히프(heap)로 구현~ 최소 우선순위 큐: 가장 우선순위가 낮은 요소를 먼저 삭제최대 우선순위 큐: 가장 우선순위가 높은 요소를 먼저 삭제 9.2 우선순위 큐의 구현방법배열을 사용하는 방법정렬X배열삽입 O(1) : 그냥 배열 맨 끝에 요소 추가삭제 O(n): 가장 우선순위가 높은 요소를 찾아야 한다. 정렬이 안 되어있으므로 처음부터 끝까지 다 스캔해야 한다 정렬O배열삽입 O(n): 삽입위치를 찾고->이동 시켜서 빈자리 만들고->삽입해야함삭제 O..

8.1 트리의 개념-계층적 자료구조트리의 용어들트리는 한 개 이상의 노드로 이루어진 유한집합이다. 루트-서브트리에서 서브트리는 또다시 루트-서브트리로 나눠질 수 있다.조상노드(ancestor node): 루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드를후손노드(descendent node): 임의의 노드 하위에 연결된 모든 노드들을 의미한다단말노드(terminal node, leaf node): 자식노드가 없는 노드(차수=0)비단말노드(nonterminal node): 자식노드가 있는 노드 노드의 차수(degree): 어떤 노드가 가지고 있는 자식노드의 개수트리의 차수: 트리가 가지고 있는 노드의 차수 중에서 가장 큰 값레벨(level): 트리의 각 층에 번호를 매기는 것. 루트노드가 1층이다높..

7.1 원형 연결 리스트원형 연결리스트의 소개원형 연결 리스트 : 마지막 노드가 첫 번째 노드를 가리키는 리스트(원래는 NULL이었는데!) 장점: 하나의 노드에서 다른 모든 노드로의 접근이 가능하다(링크만 따라서 쭉쭉 가면 되니까!) = 삽입/삭제가 단순연결리스트보다 용이하다특히 insert_last가 매우 효율적이다. 단순연결리스트에서는 첫 번째 노드부터 쭉쭉 링크 따라서 가야지만 마지막 노드에 도달할 수 있었는데 원형 연결 리스트에서는 head포인터가 마지막을 가리키도록 해주기만 하면 된다. 원형 연결리스트의 정의원칙적으로 헤드포인트만 있으면 된다ListNode *head; insert_first()헤드포인터 head가 마지막 노트를 가리키고 있다는 것에 유의해야한다 insert_last()위 코드에..

6.1 리스트 추상 데이터 타입리스트의 소개L=(item0, item1, ... , item(n-1))리스트는 순서와 위치를 가진다는 점에서 집합과는 다른 개념이다항목, 삭제, 탐색을 해보자그냥 일상적으로 작성하는 투두리스트 같은 거다! 리스트 ADT-객체: n개의 element형으로 구성된 순서 있는 모임-연산: insert(list, pos, item) ::= pos 위치에 item을 추가한다 insert_last(list, item) ::= 맨 끝에 item을 추가한다 insert_first(list, item) ::= 맨 처음에 item을 추가한다 delete(list, pos) ::= pos 위치의 요소를 제거한다 clear(list) ::= 리스트의 모든 요소를 제거..

5.1 큐 추상 데이터 타입큐(queue): 먼저 들어온 애가 먼저 나가는 선입선출(FIFO:First In First Out)구조의 자료구조마트에서 줄 서는 거를 생각하자!!계속 쌓이는 스택의 경우 데이터의 추가와 삭제가 같은 쪽에서 일어났지만 큐는 전단(front)에서 삭제가, 후단(rear)에서 삽입이 일어난다! 큐의 ADT:-객체: 0개 이상의 요소들로 구성된 선형 리스트-연산: create(max_size) ::= 최대 크기가 max_size인 공백큐를 생성 init(q) ::= 큐를 초기화 is_empty(q) ::= if(size==0) return TRUE; else return FALSE; is_full(q) ::= ..