본문 바로가기
[알고리즘] 합병정렬과 퀵정렬(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] ToyCOM의 구조에 대하여 빈칸을 채우거나 옳은 것을 선택해라. (A) ToyCOM의 기억장치 용량은 64KB이다. (B) PC(Program Counter)는 기억장치 주소를 나타내므로 16비트이다. (C) ToyCOM의 명령어 길이는 16비트이고, 8개의 기억장소를 차지한다. (D) IR(Instruction Register)은 16비트이다. (E) SP(Stack Point)는 시스템 스택의 주소를 나타내므로 16비트이다. (F) MBR(Memory Buffer Register)은 기억장치의 데이터 버스를 구동하므로 8비트이다. (G) ToyCOM은 입출력 장치를 메모리 맵으로 연결하기 때문에 입력(input)과 출력(output) 명령어를 제공할 필요가 (없다, 있다). [문제2] 상..
[컴퓨터구조론] 중앙처리정치 설계(1) - 설명 ToyCOM은 생능출판사에서 개발한 간단한 중앙처리장치이다. - ToyCOM은 8비트의 데이터를 처리한다. 이를 위하여 8개의 8비트 범용 레지스터(R0~R7)를 가지고 있으며, 8비트의 데이트를 처리할 수 있는 연산기와 8비트의 상태 레지스터를 갖고 있다. - 기억장치는 바이트 단위로 구성되어 있고 용량은 64KB이다. 따라서 주소 레지스터인 프로그램 카운터(PC)와 스택 포인터(SP)는 16비트이다. - 기억장치를 액세스하기 위하여 16비트의 주소 레지스터(MAR)와 8비트의 버퍼 레지스터(MBR)을 운영한다. - 명령어의 길이는 모두 16비트이다. 따라서 명령어 레지스터(IR)는 16비트이다. 프로그래머가 어셈블리 언어로 프로그램을 작성할 때 알고 있어야 할 수준으로 컴퓨터 구조를 표현한 것을 프로..
[알고리즘] 우선순위 큐(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 == ..

티스토리툴바