본문 바로가기

알고리즘

[알고리즘] 합병정렬과 퀵정렬(1) - 설명 분할통치법은 일반적인 알고리즘 설계기법의 일종으로 다음과 같은 해결절차를 가진다. 1. 분할(divide) : 입력 데이터 L을 둘 이상의 분리된 부분집합 L1, L2, ---으로 나눈다. 2. 재귀(recur) : L1, L2, ---각각에 대한 부문제를 재귀적으로 해결한다. 3. 통치(conquer) : 부문제들에 대한 해결을 합쳐 L의 해결을 구한다. 합병정렬(O(nlog n))은 분할통치법에 기초한 정렬 알고리즘이다. 힙정렬과 같이 비교에 기초한 정렬이지만, 힙정렬과는 다르게 우선순위 큐를 사용하지 않으며, 데이터를 순차적방식으로 접근한다. 합병정렬 알고리즘(mergeSort)는 세 단계로 이루어진다. (n개의 원소로 이루어진 입력 리스트L에 대해) 1. 분할 : 무순리스트 L을 각각 n/2개의 ..
[알고리즘] 힙과 힙정렬(2) - 예제 [문제1] 삽입식 힙 생성 프로그램 - 순차힙으로 구현(배열) - 최대힙으로 구현(삭제도 최대값 삭제) - 연산 효율을 위해 배열 인덱스 0 위치는 사용하지않고 비움 - 데이터 구조를 단순하게 하기 위해 힙의 항목(키, 원소)쌍에서 원소를 생략하고 키만 사용 - 키들은 중복이 없는 1이상의 정수 - 최대항목수 < 100 - i : 를 힙에 삽입하고 0을 출력 - d : 힙에서 삭제하여 반환된 키를 출력 - p : 힙의 내용을 출력(레벨순서로 출력) - q : 프로그램 종료 입력예시 출력예시 i 5 i 15 i 10 i 20 i 30 i 25 p d i 31 i 29 d p q 0 0 0 0 0 0 30 20 25 5 15 10 30 0 0 31 29 20 25 5 15 10 #include #includ..
[알고리즘] 힙과 힙정렬(1) - 설명 힙은 내부노드에 키를 저장하면서 두가지 속성을 만족하는 이진트리이다 1. 힙순서: 루트를 제외한 모든 내부노드에 대해 key(v) >= key(parent(v)) 또는 key(v)
[알고리즘] 우선순위 큐(2) - 예제 [문제1] n개의 양의 정수를 입력받아, 제자리 선택정렬을 하는 프로그램 -배열의 뒷 부분을 정렬 상태로 유지 입력예시 출력예시8 2 5 6 8 1 7 3 4 1 2 3 4 5 6 7 8 #include #include void main(){ int *arr; int arrNumber, max, temp; scanf("%d", &arrNumber); arr = (int*)malloc(sizeof(int)*arrNumber); for (int i = 0; i = 0; i--){ max = 0; for (int j = 1; j arr[max]){ max = j; } } for ..
[알고리즘] 우선순위 큐(1) - 설명 우선순위큐ADT는 임의의 데이터 항목이 삽입되며, 일정한 순서에 의해 삭제되는 데이터구조이다 우선순위 큐에 저장되는 데이터 항목은 (키, 원소)쌍으로 정의된다 Ex) 우편배달부가A는 우편물을 가방에 아무렇게나 담아서 각각의 주소에 도착했을 때, 우편물을 가방에서 찾아서 배달한다. 반면, 우편배달부B는 우편물을 가방에 순서대로 담아서 각각의 주소에 도착했을 때, 우편물을 꺼내서 바로 배달한다. 이 경우 주소는 키가되고, 원소는 우편물이 된다 A의 경우, 삽입은 빠르지만, 삭제가 느리다 B의 경우, 삽입은 느리지만, 삭제가 느리다 우선순위 큐ADT메소드 1) 주요메소드 insertItem(k, e) - 키k인 원소e를 큐에 삽입 element removeMin() - 큐로부터 최소 키를 가진 원소를 삭제하여..
[알고리즘] 기본 추상자료형(10) - 예제(트리ADT) [문제1] 이진트리구현 및 탐색 입력예시 출력예시9 노드 개수 5 3 9 3 8 15 8 0 2 2 0 0 15 0 0 9 7 10 7 12 0 12 0 0 10 0 0 3 탐색횟수 RLL LL LR 5 9 7 12 5 3 8 5 3 15 #include #include #include struct node { int number; struct node *left; struct node *right; }; void freeTree(struct node *tree){ if (tree == NULL) { return; } freeTree(tree->left); freeTree(tree->right); free(tree); } void preorder(struct node *tree){ if (tree == ..
[알고리즘] 기본 추상자료형(9) - 예제(트리ADT) [문제1] 트리의 순회(선위순회, 중위순회, 후위순회) - 다음과 같이 트리를 구현 - 없는 노드번호를 입력받는다면, -1출력 - 선위순회는 1, 중위순회는 2, 후위순회는 3 - id를 입력받아서 그 노드부터 순회를 하여 출력 입력예시 출력예시1 2 30 70 90 입력예시 출력예시2 3 50 130 120 80 입력예시 출력예시1 9 -1 #include #include struct node { int id; int data; struct node *left; struct node *right; }; void addLeftchild(struct node *parent, int value, int id){ struct node *newnode = (struct node*)malloc(sizeof(str..
[알고리즘] 기본 추상자료형(8) - 예제(트리ADT) [문제1] 연결리스트를 이용한 트리 구현 - 노드번호를 받아서, 그 노드와 자식노드가 있다면 출력(없으면 미출력) - 없는 노드번호를 입력받는다면, -1출력 - 트리구조 입력예시 출력예시 230 70 90 입력예시 출력예시 3 50 120 입력예시 출력예시 9 -1 #include #include struct node { int data; struct node *left; struct node *right; }; void addLeftchild(struct node *parent, int value){ struct node *newnode = (struct node*)malloc(sizeof(struct node)); newnode->data = value; newnode->left = NULL; new..

티스토리툴바