언제나 휴일

[C언어 알고리즘] 4.2.1 이진 탐색 알고리즘 소스 코드//common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Book.h #pragma once #include "common.h" #define MAX_TIT_LEN 200 #define MAX_AUT_LEN 20 typedef struct _Book Book; struct _Book { char title[MAX_TIT_LEN+1]; char author[MAX_AUT_LEN+1]; int num; }; Book..

[C언어 알고리즘] 4.2 이진 탐색 알고리즘 이번에는 이진 탐색 알고리즘을 알아봅시다. 이진 탐색 알고리즘은 특정 키순으로 정렬 상태의 배열에서 원하는 값의 요소를 빠르게 검색하는 알고리즘입니다. 순차적으로 비교하여 검색한다면 자료의 개수가 N개인 배열에서 최악의 경우 N번 비교해야 합니다. 하지만 이진 탐색 알고리즘으로 검색하면 logN 번이면 검색할 수 있습니다. 이진 탐색 알고리즘은 배열의 중간에 있는 요소와 비교해서 배열의 요소가 크면 재귀적으로 앞쪽 배열에서 검색하고 배열의 요소가 작으면 재귀적으로 뒤쪽 배열에서 검색합니다. 만약 같은 값이면 해당 인덱스를 반환합니다. 그리고 배열의 원소 개수가 0이면 재귀를 탈출하기 위해 인덱스 -1을 반환합니다. 이진 탐색 알고리즘(base:배열, asiz..

[C언어 알고리즘] 4.1.1 최소값(최대값) 찾기 알고리즘 소스 코드//common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Book.h #pragma once #include "common.h" #define MAX_TIT_LEN 200 #define MAX_AUT_LEN 20 typedef struct _Book Book; struct _Book { char title[MAX_TIT_LEN+1]; char author[MAX_AUT_LEN+1]; int num; }..

선형 자료구조에 보관한 자료 중에 최소값을 찾는 방법은 많습니다. 그 중에 분할 정복 알고리즘으로 해결하는 방법을 알아봅시다. 분할 정복 알고리즘에서는 모집합을 부분 집합으로 나누는 작업을 선행합니다. 원하는 기준에 맞게 부분 집합으로 분리한 후에 부분 집합에서 원하는 결과를 구합니다. 그리고 해결한 부분을 합쳐서 다시 커다란 집합에서 원하는 결과를 구하는 과정을 반복합니다. 최소값(최대값) 찾기 알고리즘도 분할 정복 알고리즘으로 문제를 해결할 수 있습니다. 배열의 원소 중에 최소값을 찾기 위해 원소 개수가 2보다 크면 배열의 앞 부분에서 최소값을 찾기 위해 재귀함수를 호출하고 마찬가지로 뒷 부분에서 최소값을 찾기 위해 재귀함수를 호출합니다. 그리고 배열의 앞 부분의 최소값과 뒷 부분의 최소값을 비교하여..

[C언어 알고리즘] 4. 분할정복 알고리즘 분할 정복 알고리즘은 커다란 문제를 작은 문제로 나누어 작은 문제를 해결하고 이를 다시 합쳐 커다란 문제를 해결하는 알고리즘입니다. 분할 정복 알고리즘은 내부적으로 재귀 알고리즘을 사용합니다. 대표적인 분할 정복 알고리즘에는 최소값(최대값) 찾기 알고리즘, 이진 탐색 알고리즘과 병합 정렬 알고리즘 등이 있습니다.[C언어 알고리즘] 4.1 최소값(최대값) 찾기 알고리즘[C언어 알고리즘] 4.2 이진 탐색 알고리즘[C언어 알고리즘] 4.3 병합 정렬(Merge Sort) 알고리즘