알고리즘 썸네일형 리스트형 [알고리즘] 그래프(1) - 설명 그래프는 네트워크 모델을 추상화한 것이다. 네크워크 모델의 예로는 지하철노선도, SNS등을 예로 들 수 있다.그래프는 (V, E) 쌍이다. V는 정점(vertex)라 불리는 노드의 집합이고, E는 간선(edge)라 불리는 정점 쌍들의 집합이다각 정점과 간선은 원소, 즉 정보를 저장한다 그래프는 위와같이 표현될 수 있다 간선의 종류에는 방향간선과 무방향간선이 있다방향간선은 (u, v)로 표현되며, 두 정점중 첫 정점은 시점(origin), 두번째 정점은 종점(destination)을 나타낸다. (Ex 항공편)무방향간선은 무순 쌍(u, v)로 표현된다. (Ex 도시간의 거리) 그래프 용어간선의 끝점 : 간선의 양쪽 끝에 있는 두 개의 정점들정점의 부착간선 : 정점에 연결된 간선들정점의 차수 : 정점에 연결된.. [알고리즘] 해시테이블(2) - 예제 [문제1] 해시테이블을 분리연쇄법을 이용해 충돌을 처리하는 해시테이블 프로그램 - 해시테이블은 크기가 M인 배열로 동적 할당한다 - 입력 키는 중복이 없는 자연수다 - 키x에 대한 해시함수 h(x) = x % M을 사용한다 - 삽입 시 충돌이 발생하는 경우, 해당 버켓 리스트의 맨 앞에 삽입한다 삽입(i) : 키 x를 받아 해시테이블에 삽입 탐색(s) : 키 x가 해시테이블에 존재하는지 탐색(해당 키가 있다면 키가 저장된 순위를 출력, 없다면 0출력) 삭제(d) : 키 x가 해시테이블에 존자하면 삭제(해당 키가 있다면 키가 저장된 순위를 출력, 없다면 0출력) 출력(p) : 해시테이블에 저장된 키들을 순서대로 인쇄 종료(e) : 프로그램 종료 입력예시 출력예시13 i 34 i 23 i 26 i 21 s .. [알고리즘] 해시테이블(1) - 설명 해시란 키를 직접 조사하여 저장 주소를 찾는 방식이다 해시테이블은 키-주소 매핑에 의해 구현된 사전ADT이다 그리고 해시테이블은 버켓 배열과 해시함수로 이루어져있다. 버켓배열은 해시테이블을 구현한 1차원 배열을 의미하고, 해시함수는 키-주소 매핑을 위한 연산을 수행하는 함수이다. 해시함수 h는 주어진 형의 키를 고정 범위[0, M-1]로 매핑한다 Ex) 해시함수 h h(x) = x % M (h는 정수 키 x에 대한 해시함수이다) 정수 h(x)를 키x의 해시값이라 한다. 주어진 키 형의 해시테이블은 다음으로 구성된다 - 해시함수h - 크기M의 배열(해시테이블) 사전을 해시테이블로 구현할 때의 목표는 항목(k, e)를 첨자 i = h(k)에 저장하는 것이다. 해시함수는 보통 두 복함수의 복합체로 명세된다. .. [알고리즘] 탐색트리(2) - 예제 [문제1] 이진탐색트리를 구현하는 프로그램- 삽입(i) : 키를 받아 노드생성 및 트리에 삽입- 삭제(d) : 키를 받아 트리에 존재하면 해당 노드 삭제후 키를 출력, 없다면 X를 출력- 탐색(s) : 키를 받아 트리에 존재하면 해당 키를 출력, 없다면 X를 출력- 출력(p) : 현재 트리를 전위순회로 출력- 종료(q) : 프로그램 종료 입력예시 출력예시i 3i 2i 7s 4i 6pi 5s 6q X 3 2 7 6 6 i 9i 2i 15i 1i 7i 11i 5i 8i 3i 4pd 2d 13pq 9 2 1 7 5 3 4 8 15 11 2 X 9 3 1 7 5 4 8 15 11 #include#includestruct node{int key;struct node *parent;struct node *lChil.. [알고리즘] 탐색트리(1) - 설명 탐색트리는 사전의 두 번째 형태로써 이진트리로 구현되며 탐색, 삽입, 삭제의 주요 작업을 지원한다. 이진트리를 구현하는 방식에 따라 탐색트리를 이진탐색트리, AVL트리, 스플레이 트리로 나눌 수 있다. 이진탐색트리는 내부노드에 (키, 원소) 쌍을 저장하며 다음의 성질을 만족하는 트리이다. - u, v, w는 모두 트리노드며 u와 w가 각각 v의 왼쪽 오른쪽 부트리에 존재할 때 key(u) < key(v) [알고리즘] 사전ADT(2) - 예제 [문제1] 정렬되어 있는 n개의 정수 키와 탐색할 키 k를 입력받아, 사전에서 k의 위치를 출력하는 프로그램(이진탐색-재귀버전) - x ≤ k 를 만족하는 사전의 키 x 중 가장 큰 값의 위치(즉, 인덱스) 출력 (위치는 0부터 시작한다고 가정하고, 위 조건을 만족하는 x가 없는 경우 –1 출력) - 즉, 키 k가 존재하는 경우에는 k의 위치를 출력하면 되고, 그렇지 않은 경우 k보다 작으면서 가장 큰 수의 위치를 출력하면 된다. 입력예시 출력예시 8 -7 -92 -31 -7 4 14 20 29 44 2 -> 사전에서 -7의 위치는 2 8 33 -92 -31 -7 4 14 20 29 44 6 -> 문제 조건을 만족하는 사전의 키는 29, 29의 위치는 6 #include #include int maxin.. [알고리즘] 사전ADT(1) - 설명 사전ADT는 (키, 원소) 쌍으로 표현된 데이터 항목의 모음을 추상데이터구조로 모델링한 것이다. 사전ADT에는 2종류가 있다. - 무순사전ADT : 데이터항목이 키 순서와 관계 없이 저장된 사전(Ex. 기록파일(log file)) - 순서사전ADT : 키 순서에 의해 정렬이 되어 저장된 사전(Ex. 일람표) 사전ADT메소드 1) 일반메소드 - integer size() : 사전의 항목 수를 반환 - boolean isEmpty() : 사전의 비어 있는지 여부를 반환 2) 접근메소드 - element findElement(k) : (키, 원소) 항목들의 모음인 사전에 키 k를 가진 항목이 존재하면 해당 원소를 반환, 그렇지 않으면 특별원소 NoSuchKey를 반환 3) 갱신메소드 - insertItem(k.. [알고리즘] 합병정렬과 퀵정렬(2) - 예제 [문제1] n개의 양의 정수(중복 가능)를 입력받아 합병정렬하는 프로그램 - 단일연결리스트로 구현 입력예시 출력예시 8 73 65 48 31 29 20 8 3 3 8 20 29 31 48 65 73 #include #include struct node{ int data; struct node *next; }; void partition(struct node *L, struct node **L1, struct node **L2, int n) { struct node *p = L; *L1 = L; for (int i = 0; i next; } *L2 = p->next; p->next = NULL; } struct node *merge(struct node .. 이전 1 2 3 4 다음
