옆히
Do it! 자료구조와 함께 배우는 알고리즘 입문 : C 언어 편 본문
 |
Do it! 자료구조와 함께 배우는 알고리즘 입문 : C 언어 편 -  보요 시바타 지음, 강민 옮김/이지스퍼블리싱 |
01 기본 알고리즘
01-1 알고리즘이란?
세 값의 최댓값
조건 판단과 분기
순서도의 기호
01-2 반복
1부터 n까지의 정수 합 구하기
양수만 입력하기
구조적 프로그래밍
다중 루프
직각 이등변 삼각형 출력
02 기본 자료구조
02-1 배열
자료구조
배열
메모리 할당 기간과 동적 객체 생성
배열의 동적 생성
배열 요소의 최댓값 구하기
배열 요소를 역순으로 정렬하기
기수 변환
소수의 나열
다차원 배열
한 해의 지난 날 수를 계산하는 프로그램
02-2 구조체
구조체란?
구조체의 배열
03 검색
03-1 검색 알고리즘
검색과 키
배열에서 검색하기
03-2 선형 검색
선형 검색
보초법
03-3 이진 검색
이진 검색
복잡도
bsearch 함수
비교 함수
구조체 배열에서 검색하기
04 스택과 큐
04-1 스택
스택이란?
스택 만들기
04-2 큐
큐란?
배열로 큐 만들기
링 버퍼로 큐 만들기
05 재귀 알고리즘
05-1 재귀의 기본
재귀란?
순차곱셈 구하기
유클리드 호제법
05-2 재귀 알고리즘 분석
재귀 알고리즘의 분석
재귀 알고리즘의 비재귀적 표현
05-3 하노이의 탑
하노이의 탑
05-4 8퀸 문제
8퀸 문제란?
퀸 놓기
가지 뻗기
분기 한정법
8퀸 문제를 푸는 프로그램
06 정렬
06-1 정렬
정렬이란?
06-2 버블 정렬
버블 정렬
06-3 단순 선택 정렬
단순 선택 정렬
06-4 단순 삽입 정렬
단순 삽입 정렬
06-5 셸 정렬
단순 삽입 정렬의 특징
셸 정렬
06-6 퀵 정렬
퀵 정렬 살펴보기
배열을 두 그룹으로 나누기
퀵 정렬
비재귀적인 퀵 정렬
06-7 병합 정렬
정렬을 마친 배열의 병합
병합 정렬
06-8 힙 정렬
힙이란?
힙 정렬
배열을 힙으로 만들기
06-9 도수 정렬
도수 정렬
07 집합
07-1 집합
집합과 원소
부분집합과 진부분집합
집합의 연산
07-2 배열로 집합 만들기
배열로 집합 만들기
07-3 비트 벡터로 집합 만들기
비트 벡터로 집합 만들기
08 문자열 검색
08-1 문자열의 기본
문자열이란?
문자열 리터럴
배열에 문자열 저장하기
포인터와 문자열
문자열의 길이
문자열에서 문자 검색하기
문자열 비교
08-2 브루트-포스법
문자열 검색이란?
브루트-포스법
08-3 KMP법
KMP법
08-4 Boyer-Moore법
Boyer-Moore법
09 리스트
09-1 선형 리스트
선형 리스트란?
배열로 선형 리스트 만들기
09-2 포인터로 연결 리스트 만들기
포인터로 연결 리스트 만들기
09-3 커서로 연결 리스트 만들기
커서로 연결 리스트 만들기
프리 리스트
09-4 원형 이중 연결 리스트
원형 리스트
이중 연결 리스트
원형 이중 연결 리스트
10 트리
10-1 트리
트리란?
순서 트리 탐색
10-2 이진트리와 이진검색트리
이진트리
완전이진트리
이진검색트리
이진검색트리 만들기
11 해시
11-1 해시법
정렬된 배열에 새로운 값 추가하기
해시법
충돌
체인법
오픈 주소법
참고용
[C/C++] 인자로 넘겨받은 배열로는 배열의 크기를 구할 수 없다. (tistory.com)
[C/C++] 인자로 넘겨받은 배열로는 배열의 크기를 구할 수 없다.
다음과 같이 배열이 주어지면 배열의 크기와 원소의 크기를 통해 배열의 길이를 알 수 있다. void main() { int arr[] = {1,2,3,4,5,6}; size_t arr_size = sizeof(arr)/sizeof(int); // 6 } 그런데 다음과 같이 함수의 인
woo-dev.tistory.com
포인터로 변환된 배열에서 범위 기반 for 루프를 사용할 수 없다. (배열의 크기를 알지 못하기 때문이다.)출처: https://boycoding.tistory.com/210 [소년코딩:티스토리]
[용어] 절대 경로, 상대 경로, 작업 경로에.. : 네이버블로그 (naver.com)
[용어] 절대 경로, 상대 경로, 작업 경로에 대하여
: C 언어 관련 전체 목차 http://blog.naver.com/tipsware/221010831969 1. 절대 경로 '절대 경로(A...
blog.naver.com
std::cout << *reinterpret_cast<int*>(&arr1[i * size]) << " ";
01 기본 알고리즘
concatenation (순차) <> selection <> repetition
operator <> operand (피연산자); unary operator, binary operator, ternary operator
conditional operator (3항 연산자) // max = (a> b) ? a : b;
expression, assignment expression (대입식), evaluation (식의 값을 알아냄;
flowchart, process, predefined process, decision, loop limit, terminator, real line, dotted line, broken line
variable, parameter, formal parameter, value, actual argument (실인수) increment (증가)
Procedures, Function (), Method
short circuit evaluation , initializer(초기화)
\n : new line, line break, EOL(end of line)
- 결정트리 그려서 중앙값 찾는 함수 구현
- 순서도
- 사전 판단 vs 사후 판단
02 기본 자료구조
travelse(가로지르다, 횡단하다)
pseudorandom number(의사 난수), quasirandom number(준난수)
function-like macro // #define swap(type, x, y) do{type t = x; x = y; y = t;}while(0)
comopsite number(합성수), comma operator, entity(독립체)
- array, multidimensional array, structure
- 배열 요소의 최댓값 구하기 (traverse), 배열 요소 스왑
- 기수(cardinal number) 변환 // while (x) { number[digit++] = characterList[x % cardinal]; x /= cardinal; }
- 소수(prime number) 판단 (n은 소수 == n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않음.)
- 윤년 (1년이 366인 날) : year%4 == 0 && year%100 != 0 || year %400 ==0
랜덤으로 테이블 뽑기
for (int i = 0; i < size; i++) {
tmp = rand() % range--; // 범위 - 뽑은 횟수
RandomTable[i] = NumberTable[tmp + i]; // 뽑은 수 넣기
NumberTable[tmp + i] = NumberTable[i]; // 사용한 수 자리에 i번째 수 넣기
}
n이하 소수 전부구하기
prime[ptr++] = 2;
prime[ptr++] = 3;
for (n = 5; n <= max; n+= 2) {
flag = 1;
for (i = 1; count++, prime[i] * prime[i] <= n; i++) {
count++;
if (0 == n % prime[i]) {
flag = 0;
break;
}
}
if (flag) prime[ptr++] = n;
}
연산량 줄이기 1. 구한 소수들을 저장하고 이 소수들로 판단 + 짝수 거름 2. 자신의 제곱근보다 작은 소수만으로 나눔
03 검색
# 검색과 키 (searching and key)
- 배열에서 검색하기 : 선형 검색, 이진 검색, 해시법
- 선형 리스트 검색
- 이진검색트리(Binary search tree) 검색
#배열 검색
선형 검색(Linear search; sequential search) : 무작위로 늘어놓은 데이터 모임에서 검색을 수행
#Linear search
int search(int a[], int n, int key) {
int i = 0;
a[n] = key; //Set the sentinel
while (1) {
if (key == a[i]) return i == n ? -1 : i;
i++;
}
}
이진 검색(Binary search) : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행
#binary search
int BinarySearch(const int a[], int n, int key) {
int start = 0;
int end = n - 1;
int center;
do {
center = (start + end) / 2;
if (key == a[center]) return center;
else if (key > a[center]) start = center + 1;
else end = center - 1;
} while (start <= end);
return -1;
}
해시법(Hashing) : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행
- 체인법(Chaining): 같은 해시 값의 데이터를 선형리스트로 연결하는 방법
- 오픈 주소법(Open addressing) : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법
처음부터 순서대로 검사하는 선형 검색은 임의로 늘어놓은 배열에서 검색하는 방법 중 유일한 방법입니다.
보초법(sentinel method) : 검색 전 키 값을 배열 맨 끝 요소에 저장해서 기존 종료 조건인 (1.검색할 값을 발견하지 못하고 배열의 끝을 지남, 2.검색할 값과 같은 요소를 발견함) 중 1번 조건을 생략함 > 연산 비용 50% 줄어듬
Binary search 1.center = ( left + right )/2 위치로 감 2.찾은 값이 키 값보다 작으면 left = i + 1, 크면 right = i - 1로 함 3. 찾을 때까지 반복 // Binary search는 데이터가 '오름차순' 정렬되어야만 사용가능하다.
참고//floor function&ceiling fucntion
#복잡도(complexity)
알고리즘의 성능을 객관적으로 평가하는 기준
- 시간 복잡도 (time complexity) : 실행에 필요한 시간을 평가한 것
- 공간 복잡도 (space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
O(n) 복잡도를 표기할 때 사용하는 O는 Order에서 따옴
bsearch 함수(정렬된 배열에서 검색하는 함수)
#include <stdlib.h>
void *bsearch(const void *key, const void *base, size_t nmemb, //size_t nmemb 요소의 개수
size_t size, int (*compar)(const void *, const void*)); //size_t size 요소의 사이즈
int int_cmp(const int *a, const int *b){
if (*a < *b) return -1;
else if (*a > *b) return 1;
else return 0;
} //return 값 -1, 1을 바꾸면 내림차순 정렬에서도 사용이 가능하다.
함수포인터
//void* function(void const parameter) 반환값이 포인터임
//void (*function)(void const parameter) 함수 포인터 선언
//함수에 대한 포인터는 매개변수 선언에서만 변수 이름 앞의 *와 ()를 생략 가능
//void mainfunction (int parameter, int callback_function(int n)){} 아래 선언과 같음
void mainfunction (int parameter, int (*callback_function)(int n)) {
//함수 포인터가 있을 시 내용 실행
if (NULL != callback){
callback_function(0); //(*callback_function)(0);
//callback_function 으로 수정 및 변경에 유연해짐
}
}
... ( ... , (int(*)(const void*, const void*)) exampleFunctionName ) //함수원형 캐스팅
int __cdecl strcmp(const char *_Str1, const char *_Str2)
int npcmp(const Person* x, const Person* y) { return strcmp(x->name, y->name); }
//x->name과 y->name를 대소비교 함
//전자가 작으면 (알파벳 순서가 앞) 음수, 후자가 작으면 양수, 같으면 0이 return됨
size_t : 부호 없는 정수형(unsigned integer)으로 sizeof, alignof, offsetof 의 반환 값 문자열이나 메모리의 사이즈를 나타낼 때 사용
void* 형 선형 검색
void *LinearSearch(const void *key, const void *base, size_t nmemb, size_t size,
int (*compar)(const void*, const void*)){
size_t i = 0; //주소 값으로 쓸거니까 size_t 로 선언
if (size == sizeof(int)) {
*((int*)base + nmemb) = *(int*)key; //Set the sentinel
while (1) {
if (0 == compar(key, (int*)base + i)){
if (i == nmemb) return NULL; //sentinel 발견시 NULL 반환
return ((int*)base + i); //발견한 인덱스의 포인터 반환
}
i++;
}
}
}04 스택과 큐
스택(stack)은 데이터를 일시적으로 저장하기 위한 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)입니다. 스택에 데이터를 넣는 작업을 push라 하고, 스택에서 데이터를 꺼내는 작업을 pop이라고 합니다.
pop을 하는 위치를 top이라 하고, 스택의 가장 밑바닥 부분을 bottom이라고 합니다. Stack point, Base point
1.배열 생성 2.push 하면 Stack point++ 3.pop하면 --Stackpoint 4.데이터 소거는 stackpoint--
큐(Queue)는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조로, 데이터의 입력과 출력 순서는 선입선출(FIFO, First In First Out입니다. 큐에 데이터를 넣는 작업을 인큐(enqueue)라 하고, 데이터를 꺼내는 작업을 (dequeue)라고 합니다. 또 데이터를 꺼내는 쪽을 front라 하고, 데이터를 넣는 쪽을 rear라고 합니다.
링 버퍼(ring buffer) : Dequeue 과정에서 배열을 앞쪽으로 옮기지 않는 큐
요소개수 저장하는 변수 필요; start = rear 일 때 가득찬지 비어있는지 구분이 필요함
//enqueue
if (rear - front != max) { que[rear++ % max] = x; }
if ((rear + 1) % max != front) {
que[rear] = x;
rear = (rear + 1) % max;
}
//dequeue
if(front != rear) *x = que[front++ % max];
링 버퍼는 '오래된 데이터를 버리는' 용도로 사용할 수 있다. 요소의 개수가 n인 배열에 계속해서 데이터가 입력될 때 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버리는 용도로 사용한다. ( cnt++ % N //모듈러 연산 활용 )
데크(Deck; Deque))이라는 양방향 대기열(deque / double ended queue)은 시작과 끝 지점에서 양쪽으로 데이터를 인큐하거나 디큐하는 자료구조임
//enqueue
que[rear++] = x;
if (rear == max) rear = 0;
//reverse dequeue
if (--front < 0) front = max - 1;
que[front] = x;
//dequeue
*x = que[front++];
if (front == max) front = 0;
//reverse dequeue
if (--rear < 0) rear = max - 1;
*x = que[rear];
05 재귀 알고리즘
어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 Recursive((재귀적))이라고 한다.
#Factorial을 recursive definition ((재귀적으로 정의))하기
int factorial(int x){
if(x) return x * factorial(x - 1);
else return 1;
}
#Direct((직접)) 재귀, Indirect((간접))재귀
재귀 알고리즘에 알맞는 경우는 '풀어야 할 문제', '계산할 함수', '처리할 데이터 구조'가 재귀적으로 정의되는 경우이다.
분기가 일어나는 반복적인 구조, 재귀를 정의로 접근 흐름을 하나하나 다 따라가지 말자
Euclidean method of mutual division((유클리드 호제법))
두 양의 정수 a, b (a > b)에 대하여 a = bq + r (0 <= r < b)이라 하면 a, b의 최대공약수는 b, r의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, r) //r = 0이라면, a, b의 최대공약수는 b가 된다.
#재귀적으로 구현한 유클리드 호제법
int get_gcd(int x1, int x2) {
if (x1 < x2) swap(x1, x2); //#define swap(a, b) {int tmp = a; a = b; b = tmp;}
if (x2) return gcd(x2, x1 % x2);
return x1;
}
#배열로 받은 n개의 정수에 대한 유클리드 호제법
int gcd_array(const int a[], int n) {
if (2 == n) return gcd(a[0], a[1]);
else return gcd(a[0], gcd_array(&a[1], n - 1)); //&a[1] 재귀할수록 주소가 한 칸 앞으로
//예외 처리
if (1 == n) return a[0];
else return -1;
}
//최대공약수 = GCD = Greatest Common Divisor, 최소공배수 = LCM = Largest Common multiple
//서로소 = relatively prime, disjoint
//gcd(a, b) * lcd(a, b) = a * b, lcd(a, b) = a* b / gcd #link
#재귀 알고리즘을 분석하기 위한 top-down analysis((하향식분석))과 bottom-up analysis ((상향식 분석))
void recur2(int n){
if (n > 0) {
recur2(n - 2);
printf("%d\n");
recur2(n - 1);
}
}
위 함수를 분석해보자
위와 같은 방법으로 분기를 따라 분석해 재귀적으로 정의된 문제를 코드로 풀어낼 수 있다.
위 그림과 같은 하노이의 탑 문제를 상향식으로 분석해보자
하노이의 탑 문제가 재귀적인 구조를 가짐을 알 수 있다. 따라서 왼쪽 분기와 오른쪽 분기의 정의를 재귀적으로 작성하면 다음과 같다.
#재귀 알고리즘의 비재귀적 표현
다음과 같이 재귀적으로 정의된 함수를 비재귀적인 표현으로 나타낼 수 있다.
void recur(int n)
{
if (n > 0) {
recur(n - 1);
printf("%d\n", n);
recur(n - 2);
}
}
위 함수에서 tail recursion((꼬리 재귀))인 recur(n - 2)는 n에서 2를 빼고 함수의 처음으로 돌아라는 표현과 같다,
이를 반영하면 다음과 같다.
void recur(int n){
Top:
if (n > 0) {
recur(n - 1);
printf("%d\n", n);
n -= 2;
goto Top;
}
}
꼬리 재귀는 이렇게 바꿀 수 있지만 앞에서 호출한 재귀 함수 recur(n - 1)은 이 방법으로 바꿀 수는 없다. 재귀 호출을 하면서 이전에 n 일 때의 함수가 남아있는 채 n-1 일 때의 함수를 호출하기 때문에 n 일 때의 함수 값을 따로 저장할 필요가 있기 때문이다.
즉 변수 n을 저장할 필요가 생긴다. 이럴 때 Stack 구조를 사용하면 n 값을 push하고 나중에 순차적으로 pop 시킬 수 있기 때문에 재귀 함수 recur(n - 1)을 다음과 같이 비재귀적인 표현으로 바꿀 수 있다.
void recur(int n){
IntSTACK stack(30);
while (1) {
if (n > 0) {
stack.Push(n);
n -= 1;
continue;
}
if (!stack.IsEmpty()) { //비어 있으면 1 반환
stack.Pop(&n;
printf("%d\n", n);
n -= 2;
continue;
}
break;
}
}
#하노이의 탑 비재귀적 표현으로 풀기
void moveQQ(int n, int dep, int des) {
IntSTACK stack(100);
IntSTACK DEPstack(100);
IntSTACK DESstack(100);
while (1) {
if (n > 0) {
stack.Push(n--);
DEPstack.Push(dep);
DESstack.Push(des);
des = 6 - dep - des;
continue;
}
if (!stack.Isempty())
{
stack.Pop(&n);
DEPstack.Pop(&dep);
DESstack.Pop(&des);
printf("%d번 원반을 %d번 기둥에서 %d번 기둥으로 옮깁니다.\n", n--, dep ,des);
dep = 6 - dep - des;
continue;
}
break;
}
}
재귀는 결국 분기가 반복적으로 일어나는 표현이므로 각 재귀마다 분귀가 어떻게 정의되어 있는지를 아는게 중요하다.
#8-Queen problem(8퀸 문제)
체스판에 퀸 8개를 서로 공격받지 않는 위치로 배치하는 문제이다. 체스판은 총 64칸(8 x 8)이므로 단순히 경우의 수를 생각하면 64P8(178,462,987,637,760)이므로 경우의 수가 너무 많다. 따라서 규칙을 세워서 경우의 수를 줄일 수 있다.
- 각 열에 퀸을 1개만 배치합니다. (경우의 수 : 8^8 = 16,777,216)
- + 각 행에 퀸을 1개만 배치합니다. (경우의 수 : 8! = 40,320)
이처럼 필요하지 않는 분기를 없애 불필요한 조합을 줄이는 방법을 한정(Bounding) 조작이라 하고, 가지 뻗기와 한정 조작을 조합하여 문제를 풀어 가는 방법을 분기 한정법(branching and bounding method)이라고 한다.
하노이의 탑이나 8퀸 문제처럼 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법을 divide and conquer(분할 해결법)이라 한다.
#8퀸 문제 풀기
void _8Queens(int row) {
for (int column = 0; column < 8; column++) {
if (!flagC[column] && !flagD[row + column] && !flagRD[column - row + 7]) {
Pos[row] = column;
if (row == 7) {
print();
}
else {
flagC[column] = flagD[row + column] = flagRD[column - row + 7] = 1;
_8Queens(row + 1);
flagC[column] = flagD[row + column] = flagRD[column - row + 7] = 0;
}
}
}
}
#비재귀적으로 8퀸 문제 풀기
void NoRecursion_8Queens() {
int row = 0; int column = 0;
while (1) {
if (column > 7){ //Backtracking
if (--row < 0) break;
flagC[Pos[row]] = flagD[row + Pos[row]] = flagRD[Pos[row] - row + 7] = 0;
column = ++Pos[row];
continue;
}
if (!flagC[column] && !flagD[row + column] && !flagRD[column - row + 7]) {
Pos[row] = column;
column = 0;
if (row == 7) {
for (int i = 0; i < 8; i++) cout << Pos[i]; cout << endl;
column = 9; //다른 경로 탐색
}
else {
flagC[Pos[row]] = flagD[row + Pos[row]] = flagRD[Pos[row] - row++ + 7] = 1;
}
}
else column++;
}
}
//while문 중첩시켜서도 구현 가능
06 정렬
Sort(정렬)은 이름, 학번, 키 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말합니다. 키 값이 작은 데이터를 앞쪽에 높으면 ascending order(오름차순) 정렬, 그 반대로 높으면 descending order(내림차순) 정렬이라고 부릅니다.
#정렬 알고리즘의 안정성
정렬 알고리즘은 stable(안정된) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있습니다. 같은 키 값의 요소의 순서가 정렬 전후에도 유지되면 안정된 정렬이라고 합니다.
#내부 정렬과 외부 정렬
내부 정렬 (internal sorting) : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘입니다.
외부 정렬 (external sorting) : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘입니다.
#정렬 알고리즘의 핵심 요소
정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입이며 대부분의 정렬 알고리즘은 이 세 가지 요소를 응용한 것입니다.
버블 정렬(bubble sort)
요소가 n개인 배열의 이웃한 요소를 비교하고 교환하는 작업을 패스(pass)라고 합니다. 마지막 요소는 이미 끝에 놓이기 때문에 처음에 수행할 패스의 횟수는 n-1회입니다. 패스를 k번 할 때마다 앞쪽의 요소가 k개가 정렬됩니다. 따라 패횟수는 (n-1) + (n-2) + (n-3) + ... + (n - (n - 2)) + 1 = n(n-1) / 2회입니다. 버플정렬은 stable 입니다.
#버블 정렬
#define swap(type, a, b) do {type tmp = a; a = b; b = tmp;} while(0)
int bubbleSort(int* arr, size_t size) {
if (size == 1) return 0;
int last = 0;
for (int i = 0; i < size - 1; i++) {
if (arr[i] > arr[i + 1]) {
swap(int, arr[i], arr[i + 1]);
last = i + 1; //마지막 교환 위치 저장
}
}
if (last) bubbleSort(arr, last); //정렬된 부분 제외
return 0;
}
//if (arr[i] > arr[i + 1]) { return -1 } 정렬 검사 가능
#양방향 버블 정렬(bidirection bubble sort; 칵테일 정렬(cocktail sort), 셰이커 정렬(shaker sort))
위에 작성된 버블 정렬로는 {2, 3, 4, 5, 1} 와 같이 마지막 요소를 제외하고 정렬이 완료된 배열에 대하여 빠른 시간내에 정렬이 불가합니다. 1회의 pass를 끝마쳐도 {2, 3, 4, 1, 5} 와 같이 1이 한 칸만 이동하기 때문입니다.
이때 홀수 번째의 패스는 가장 작은 요소를 맨 앞으로 옮기고 짝수번째 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식을 사용하면(스캔 방향을 매 pass마다 교대로 바꾸면) 더 적은 횟수로 비교를 수행할 수 있습니다.
#cocktail sort
#define swap(type, a, b) do {type c = a; a = b; b = c;} while(0)
void cocktailSort(int* arr, size_t size) {
int left = 0;
int right = size - 1;
int last = right;
while (left < right) {
//left
for (int i = 0; i < right; i++) {
if (arr[i] > arr[i + 1]) {
swap(int, arr[i], arr[i + 1]);
last = i + 1;
}
}
right = last;
//right
for (int j = right; j > left; j--) {
if (arr[j - 1] > arr[j]) {
swap(int, arr[j - 1], arr[j]);
last = j - 1;
}
}
left = last;
}
}
단순 선택 정렬(straight selection sort)
가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘입니다. not stable
- 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택합니다.
- a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환합니다. //총 요소가 n개이면 1, 2 과정을 (n-1)회 반복
#straight selection sort
#define swap(type, a, b) do {type tmp = a; a = b; b = tmp;} while(0)
void selectionSort(int* arr, size_t size) {
for (int i = 0; i < size - 1; i++) {
int min = i;
for (int j = i + 1; j < size; j++) {
if (arr[min] > arr[j]) min = j;
}
swap(int, arr[i], arr[min]);
}
}
단순 삽입 정렬(straight insertion sort)
선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입 하는' 작업을 반복하여 정렬하는 알고리즘입니다. 단순 선택 정렬과 비슷하게 보일 수 있지만 단순 선택 정렬은 값이 가장 작은 요소를 선택해 알맞은 위치로 옮긴다는 점이 다릅니다. 단순 삽입 정렬은 떨어져 있는 요소들이 서로 뒤바뀌지 않아 stable 합니다.
- 아직 정렬되지 않은 부분의이 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입합니다. //n-1회
알맞은 위치에 삽입
- 정렬된 열의 왼쪽 끝에 도달합니다.
- tmp보다 작거나 같은 key를 갖는 항목 a[i]를 발견합니다. //열이 0이 아닙니다 && key가 tmp보다 큽니다.
#straight insertion sort
void insertionSort(int* arr, size_t size){
int i, j;
for (i = 1; i < size; i++) {
int tmp = arr[i];
for (j = i; j > 0 && arr[j - 1] > tmp; j--) {
arr[j] = arr[j - 1];
}
arr[j] = tmp;
}
}
위에 세가지 단순 정렬(버블, 선택, 삽입)의 시간 복잡도는 모두 O(n^2) 입니다.
//printf("%*s%s", 4 * j, "", (i != j) ? "^-" : " ");
#straight inserion sort with sentinel method
void sentinelInsertion(int* arr, size_t size) { //arr[0] 안씀
for (int i = 1; i < size; i++) {
int j = i;
int tmp = arr[0] = arr[i]; //Set the sentinel
while (arr[j - 1] > tmp) arr[j--] = arr[j - 1];
arr[j] = tmp;
}
}
#binary insertion sort(이진 삽입 정렬) not stable
void binaryInsertionSort(int* arr, size_t size) { //Q10 not stable
int i, j;
for (i = 1; i < size; i++) {
int key = arr[i];
int start = 0; int end = i - 1; int mid;
//삽입위치 이진검색
while (start <= end) {
mid = (start + end) / 2;
if (key < arr[mid]) end = --mid;
else start = ++mid;
}
//칸 밀기
for (j = i; j > start; j--) arr[j] = arr[j - 1];
//memmove(arr + start + 1, arr + start, sizeof(int)*(i - start));
arr[j] = key;
}
}shell sort(셸 정렬)
셸 정렬은 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘입니다.
단순 삽입 정렬의 특징
- 장점 : 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라집니다.
- 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아집니다.
셸 정렬은 단순 삽입 정렬의 장점은 살리고 단점은 보완한 정렬 알고리즘으로, 도널드 셸(D.L.Shell)이 고안했습니다. 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹 별로 단순 삽입 정렬을 수행하고 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법입니다. h간격, 그룹의 크기, insertion 인덱스
8칸 배열에 대한 셸 정렬의 전체 흐름, 각각의 정렬을 'h-정렬'이라고 합니다.
- 2개 요소에 대해 '4-정렬'을 합니다.(4개의 그룹)
- 4개 요소에 대해 '2-정렬'을 합니다.(2개의 그룹)
- 8개 요소에 대해 '1-정렬'을 합니다.(1개의 그룹)
정렬되지 않은 상태의 배열에 대해 단순 삽입 정렬을 그냥 적용하는 것이 아니라 'h-정렬'로 조금이라도 정렬이 된 상태에 가까운 배열로 만들어 놓은 다음에 마지막으로 단순 삽입 정렬을 수행하여 정렬을 마칩니다. 단순 삽입 정렬의 장점을 살리고 단점을 보완합니다. 정렬 해야 하는 횟수는 늘지만 전체적으로는 요소 이동의 횟수가 줄어들어 효율적인 정렬을 할 수 있습니다.
h 값의 감소하는 수열에서 h 값이 서로 배수가 되지 않도록 하면 효율적인 정렬이 가능해짐 (ex : h_{n + 1} = 3h_{ n } + 1)
#shell sort
void shellSort(int* arr, size_t size) {
int i, j, h;
int cnt = 0;
for (h = 1; h < size / 9; h = 3 * h + 1); //Find the Maximum value of sequence not exceeding h/9
for (; h > 0; h /= 3) {
for (i = h; i < size; i++) {
int tmp = arr[i];
for (j = i - h; j >= 0 && arr[j] > tmp; j -= h) {
arr[j + h] = arr[j];
}
arr[j + h] = tmp;
}
}
}
Quick sort(퀵 정렬)
퀵 정렬은 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘입니다. 퀵 정렬이라는 이름은 이 알고리즘의 정렬 속도가 매우 빠른 데서 착안한 찰스 앤터니 리처드 호어(C.A.R.Hoare)가 직접 붙인 이름입니다. O(n log n)
- 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
- 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
#Quick sort
void quickSort(int* arr, size_t size) {
int x = arr[size / 2]; //Set the pivot
int pl = 0; int pr = size - 1;
do {
while (arr[pl] < x) pl++;
while (arr[pr] > x) pr--;
if (pl <= pr) {
swap(int, arr[pl], arr[pr]);
pl++;
pr--;
}
} while (pl <= pr);
if (0 < pr) quickSort(arr, pl);
if (pl < size - 1) quickSort(arr + pl, size - pl);
}
//int pl = (Pop(&lstack, &left), left); 쉼표 연산자, 왼쪽 피연산자를 평가한 후 오른쪽 피연산자를 평가하고, 그 결과로 오른쪽 피연산자의 값을 반환함
#Quick sort with no recursion
#define swap(type, a, b) do {type tmp = a; a = b; b = tmp;} while(0)
void QuickSortNR(int arr[], int left, int right) {
IntSTACK lstack(right - left + 1);
IntSTACK rstack(right - left + 1);
lstack.Push(left);
rstack.Push(right);
while (!lstack.IsEmpty()) {
int pl = (lstack.Pop(&left), left);
int pr = (rstack.Pop(&right), right);
int x = arr[(left + right) / 2];
if (right - left <= 9) {
_shellSort(arr + left, right - left + 1); //요소의 개수가 9개 이하면 쉘 정렬
}
else {
do {
while (arr[pl] < x) pl++;
while (arr[pr] > x) pr--;
if (pl <= pr) {
swap(int, arr[pl], arr[pr]);
pl++;
pr--;
}
} while (pl <= pr);
if (left - pr > right - pl) {
swap(int, left, pl); swap(int, pr, right);
} //배열의 요소가 더 많은 배열을 먼저 push 합니다.
if (left < pr) {
lstack.Push(left);
rstack.Push(pr);
}
if (right > pl) {
lstack.Push(pl);
rstack.Push(right);
}
}
}
}
++퀵 정렬 함수에서 요소의 개수가 많은 그룹을 먼저 push하면 요소의 개수가 적은 그룹이 이후 push 됩니다. 일반적으로 요소의 개수가 적은 배열일수록 적은 횟수로 분할을 종료할 수 있습니다. 따라서 요소의 개수가 적은 그룹은 먼저 나누면 스택에 쌓여 있는 데이터의 최대 개수를 줄일 수 있습니다. 배열의 요수 개수가 n이라고 하면 스택에 쌓이는 데이터의 최대 개수는 log n 보다 적습니다. 따라서 요소의 개수가 백만 개여도 스택의 최대 용량은 20개면 충분합니다.
++퀵 정렬은 요소의 개수가 적은 배열에 대해서는 처리가 아주 빠르게 진행되지 않습니다. 위 코드에서는 배열의 요소가 9개 이하이면 셸 정렬을 시행했음
++피벗을 선택하는 방법은 퀵 정렬의 실행 효율에 큰 영향을 줍니다. 피벗의 값이 한 쪽으로 치우친 경우 배열이 균등하게 나누어지지 않기 때문입니다. 빠른 정렬을 원한다면 배열을 정렬한 다음에 가운데 값을 피벗으로 하면 되지만 가운데 값을 구하고자 할 경우 그에 대한 처리가 필요하고 이 처리에 대해 많은 계산 시간이 요구되어 배보다 배꼽이 더 커집니다. 이 문제를 해결하기 위해 다음과 같은 방법이 사용될 수 있습니다.
- 나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음 가운데 요소와 끝에서 두 번째 요소를 교환합니다. 피벗으로 끝에서 두 번째 요소를 교환합니다. 피벗으로 끝에서 두 번째 요소의 값(arr[right - 1])을 선택하여 나눌 대상의 범위를 arr[left + 1] ~ arr[right - 2]로 좁힙니다.
위의 방법을 통해 나눌 그룹의 크기가 한쪽으로 치우치는 것을 피하면서도 나눌 때 스캔할 요소를 3개씩 줄일 수 있다는 장점이 있습니다.
#quick sort + 위에 아이디어 전부 결합
int sort3elem(int x[], int a, int b, int c)
{
if (x[b] < x[a]) swap(int, x[b], x[a]);
if (x[c] < x[b]) swap(int, x[c], x[b]);
if (x[b] < x[a]) swap(int, x[b], x[a]);
return b;
}
void QuickSortNR(int arr[], int left, int right) {
IntSTACK lstack(right - left + 1);
IntSTACK rstack(right - left + 1);
lstack.Push(left);
rstack.Push(right);
while (!lstack.IsEmpty()) {
int pl = (lstack.Pop(&left), left);
int pr = (rstack.Pop(&right), right);
int pc = (left + right) / 2;
if (right - left < 9) {
shellSort(arr + left, right - left + 1);
}
else {
int x = arr[sort3elem(arr, pl, pc, pr)]; //pivot 저장 + 처음 가운데 끝 요소 정렬
swap(int, arr[pc], arr[pr - 1]); //가운데 요소와 끝에서 두 번째 요소 교환
pl++; pr -= 2;
do {
while (arr[pl] < x) pl++;
while (arr[pr] > x) pr--;
if (pl <= pr) {
swap(int, arr[pl], arr[pr]);
pl++;
pr--;
}
} while (pl <= pr);
//크기가 큰 배열 먼저 push
if (left - pr > right - pl) {
swap(int, left, pl); swap(int, pr, right);
}
if (left < pr) {
lstack.Push(left);
rstack.Push(pr);
}
if (right > pl) {
lstack.Push(pl);
rstack.Push(right);
}
}
}
}
#<stdlib.h>의 qsort 함수 사용하기
헤더 : #include<stdlib.h>
형식 : void qsort(void* base, size_t nmemb, size_t size, int(*compar)(const void*, const void*));
base : 배열, nmemb : 요소의 개수, size : 배열 요소의 크기, compar : 비교인자(내림, 오름 차순)
- qsort 함수는 bsearch 함수와 마찬가지로 int형이나 double형 등의 배열뿐만 아니라 구조체형 배열 등의 모든 자료형의 배열에 적용할 수 있습니다. 함수 이름은 퀵 정렬에서 따왔지만 내부적으로 항상 퀵 정렬 알고리즘을 사용하지는 않습니다.
- qsort 함수는 같은 키 값을 가지고 있는 데이터가 2개 이상인 경우에 이름의 오름차순으로 정렬이 되기는 하지만 정렬 전후의 데이터가 같은 순서를 유지하지는 않습니다.(안정된 정렬은 아닙니다.) //실습6-12
비교 함수는 아래의 값을 반환하는 함수이며 직접 작성해야 합니다.
#비교 함수의 반환값
- 첫 번째 인수가 가리키는 값이 더 작은 경우 음수 값을 반환합니다.
- 첫 번째 인수가 가리키는 값과 두 번째 인수가 가리키는 값이 같은 경우 0을 반환합니다.
- 첫 번째 인수가 가리키는 값이 더 큰 경우 양수 값을 반환합니다.
qsort(arr, ARRSIZE, sizeof(arr), (int(*)(const void*, const void*))int_cmp);
//(int(*)(const void*, const void*)) 함수 원형 캐스팅
++strcmp(), strncmp
헤더 : <string.h>, <cstring>
int strcmp(const char* str1, const char* str2);
int strncmp(const char* str1, const char* str2, size_t n);
문자열 str1 ,str2 를 비교해서 같으면 0, str1 < str2 면 -1, str1 > str2 면 1을 반환함.
c언어 입문 p.371 "배열 표기법은 요소를 구성하는 모든 바이트 값을 한 번에 수정한다." 참고
*p[n] != (*p)[n]
/*--- 문자열을 가리키는 p를 오름차순으로 정렬 ---*/
void sort_pvstr(char *p[], int n)
{
qsort(p, n, sizeof(char *), pstrcmp);
}
//다중포인터는 그냥 가리키는 대상이 여러번 간 것 간단히 생각하자
#본문 Q20 코드 참고
/* Q20 범용 퀵 정렬(qsort 함수와 비슷한 성능으로 동작합니다) */
#include <stdio.h>
#include <stdlib.h>
/*--- x, y가 가리키는 n 바이트의 메모리 영역을 교환 ---*/
static void memswap(void *x, void *y, size_t n)
{
unsigned char *a = (unsigned char *)x;
unsigned char *b = (unsigned char *)y;
for (; n--; a++, b++) {
unsigned char c = *a;
*a = *b;
*b = c;
}
}
void q_sort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))
{
if (nmemb > 0) {
size_t pl = 0; /* 왼쪽 커서 */
size_t pr = nmemb - 1; /* 오른쪽 커서 */
size_t pv = nmemb; /* 피벗 */
size_t pt = (pl + pr) / 2; /* 피벗 업데이트 */
char *v = (char *)base; /* 첫 번째 요소에 대한 포인터 */
char *x; /* 피벗에 대한 포인터 */
do {
//피벗이 포인터여서 값이 정렬하면서 바뀔 수 있으므로 갱신해줌
if (pv != pt) x = &v[(pv = pt) * size];
while (compar((const void *)&v[pl * size], x) < 0) pl++;
while (compar((const void *)&v[pr * size], x) > 0) pr--;
if (pl <= pr) {
//피벗이 제 위치에서 벗어나면 위치를 다시 고침
pt = (pl == pv) ? pr : (pr == pv) ? pl : pv;
memswap(&v[pl * size], &v[pr * size], size);
pl++;
if (pr == 0) /* 부호가 없는 정수 0부터 1씩 감소를 피합니다. */
goto QuickRight;
pr--;
}
} while (pl <= pr);
if (0 < pr) q_sort(&v[0], pr + 1, size, compar);
QuickRight:
if (pl < nmemb - 1) q_sort(&v[pl * size], nmemb - pl, size, compar);
}
}
Merge sort(병합 정렬)
병합 정렬은 배열을 앞부분과 뒷부분을 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘입니다. 분할정복법
#병합 정렬 알고리즘; 배열의 요소 개수가 2개 이상인 경우
- 배열의 앞부분을 병합 정렬로 정렬합니다.
- 배열의 뒷부분을 병합 정렬로 정렬합니다.
- 배열의 앞부분과 뒷부분을 병합합니다.
#merge sort
static void merge(int* arr1, size_t n1, int* arr2, size_t n2) {//arr1, 2는 각각 왼쪽 오른쪽
size_t p1, p2, p3; //total size n1 + n2
p1 = p2 = p3 = 0;
int* buff = (int *)calloc(n1, sizeof(int));
for (int i = 0; i < n1; i++)
buff[i] = arr1[i];
while (p1 < n1 && p2 < n2)
arr1[p3++] = (buff[p1] <= arr2[p2]) ? buff[p1++] : arr2[p2++];
while (p1 < n1)
arr1[p3++] = buff[p1++];
free(buff);
}//buff 먼저 다 옮겨도 arr2는 뒷부분이라서 안옮겨도 이미 들어가 있음
static void _mergeSort(int* arr, size_t left, size_t right) {
if (left >= right) return;
size_t center = (left + right) / 2;
_mergeSort(arr, left, center);
_mergeSort(arr, center + 1, right);
merge(arr + left, center - left + 1, arr + center + 1, right - center);
}
void mergeSort(int* arr, size_t nmemb) {
_mergeSort(arr, 0, nmemb - 1);
}
배열 병합의 시간 복잡도는 O(n)이고 데이터의 요소 개수가 n개일 때, 병합 정렬의 단계는 log n만큼 필요하므로 전체 시간 복잡도는O(n log n)이라고 할 수 있습니다. 병합 정렬은 서로 떨어져 있는 요소를 교환하는 것이 아니므로 안정적인 정렬 방법이이라고 할 수 있습니다.
Heap sort(힙 정렬)
힙 정렬은 힙을 사용하여 정렬하는 알고리즘입니다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전이진트리입니다. 이때 부모의 값이 자식보다 항상 작아도 힙이라고 합니다.(부모와 자식 요소의 관계만 일정하면 됩니다.) 최대힙은 부모>=자식, 최소힙은 자식>=부모 관계를 만족시킴
힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않습니다. 위 그림을 예시로 보면 형제 관계인 7, 8은 작은 쪽인 7이 왼쪽에 있지만 형제 관계인 6, 5는 작은 쪽인 5가 오른쪽에 있습니다.(힙은 형제의 대소 관계가 정해져 있지 않은 특성이 있기 때문에 부분순서트리(partial ordered tree)라고도 합니다.)
힙에 요소를 배열에 저장할 때 BFS 순서로 배열에 저장함(10 트리 참고) 위 그림을 기준으로 배열 arr[0] ~ arr[5] = { 9, 7, 8, 6, 5, 4 }임
#부모와 자식의 인덱스 사이 관계
- parent = arr[(idx - 1) / 2]
- left child = arr[idx * 2 + 1]
- right child = arr[idx * 2 + 2]
힙 정렬은 '가장 큰 값이 루트에 위치'하는 특징을 이용하는 정렬 알고리즘입니다. 힙에서 가장 큰 값인 루트를 꺼내는 작업을 반복하고 그 값을 늘어 놓으면 배열은 정렬을 마치게 됩니다. 즉, 힙 정렬은 선택 정렬을 응용한 알고리즘이며 힙에서 가장 큰 값인 루트를 꺼내고 남은 요소에서 다시 가장 큰 값을 구해야 합니다.
#루트를 없애고 힙 상태 유지하기
- 루트를 꺼냅니다.
- 마지막 요소(맨 아래에서 오른쪽 끝에 있는 자식)를 루트로 이동합니다.
- 자기보다 큰 값을 가지는 자식 요소와 자리를 바꾸며 아래쪽으로 내려가는 작업을 반복합니다. 이때 자식의 값이 작거나 잎에 다다르면 작업이 종료 됩니다.
#배열로 힙 만들기
앞서 루트를 없애고 힙 상태 유지하기에서 했던거 처럼 루트를 없앤 다음 마지막 요소를 루트로 옮기고 루트로 옮긴 요소를 알맞은 위치로 옮기면서 힙을 만듭니다. 이 방법을 이용하면 아랫부분의 작은 부분 트리부터 시작해 올라가는 방식(bottom-up)으로 전체 배열을 힙으로 만들 수 있습니다.
- 시작은 젤 아랫 단계;가장 오른쪽 부분트리로 이동
- 부분 트리를 힙으로 만듬
- 왼쪽 부분 트리로 이동, 더이상 왼쪽 부분 트리가 없을 때까지 2번으로
- 부분 트리를 한 칸 더 확장함
힙 정렬은 선택 정렬을 응용한 알고리즘입니다. 단순 선택 정렬은 정렬되지 않은 영역의 모든 요소를 대상으로 가장 큰 값을 선택합니다. 힙 정렬에서는 첫 요소를 꺼내는 것만으로 가장 큰 값이 구해지므로 첫 요소를 꺼낸 다음 나머지 요소를 다시 힙으로 만들어야 그 다음에 꺼낼 첫 요소도 가장 큰 값을 유지합니다. 따라서 단순 선택 정렬에서 가장 큰 요소를 선택할 때의 시간 복잡도 O(n)의 값을 한 번에 선택할 수 어 O(1)로 줄일 수 있습니다. 그 대신 힙정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(log n)입니다. 따라서 힙정렬은 힙으로 만드는 작업을 요소의 개수만큼 반복하므로 시간 복잡도의 값은 O(n log n)입니다.
#heap sort
static void downHeap(int* arr, int left, int right) {
int parent, child, cl, cr, tmp;
for (parent = left; parent < (right + 1) / 2; parent = child) {
cl = parent * 2 + 1; cr = cl + 1;
child = (right >= cr && arr[cl] < arr[cr]) ? cr : cl;
if (arr[parent] >= arr[child]) break;
swap(int, arr[parent], arr[child]);
}
}
void heapSort(int* arr, int nmemb) {
nmemb--;
for (int i = (nmemb - 1) / 2; i >= 0; i--)
downHeap(arr, i, nmemb);
for(;nmemb > 0; nmemb--) {
swap(int, arr[0], arr[nmemb]);
downHeap(arr, 0, nmemb - 1);
}
}
counting sort(도수 정렬); distribution counting
도수 정렬은 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘입니다.
도수 정렬 알고리즘
- 도수분포표 만들기 //for (i = 0; i < n; i++) f[a[i]]++;
- 누적도수분포표 만들기 //for (i = 1; i < n; i++) f[i] += f[i - 1];
- 목적 배열 만들기 //for (i = n - 1; i >= 0; i--) b[--f[a[f]]] = a[i];
- 배열 복사하기 //for (i = 0; i < n; i++)a[i] = b[i];
도수분포표를 만들고 작성한 뒤 배열의 각 요솟값과 누적도수분포표를 대조하여 정렬을 마친 배열을 만듬; 도수정렬은 if문 대신 for문만을 사용해 정렬할 수 있는 알고리즘입니다.
도수 정렬 알고리즘은 데이터의 비교, 교환 작업이 필요 없어 매우 빠릅니다. 단일 for문만을 사용하며 재귀 호출, 이중 for문이 없어 아주 효율적인 알고리즘입니다. 하지만 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 사용할 수 있습니다.
도수 정렬 알고리즘은 각 단계에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기 때문에 같은 값에 대해서 순서가 바뀌는 일이 없어 이 정렬 알고리즘은 안정적이라고 할 수 있습니다. 그러나 3단계(목적 배열 만들기)에서 배열 a를 스캔할 때 마지막 위치부터가 아닌 처음부터 스캔을 하면 안정적이지 않습니다. //카운팅 할 때 1, 2, 3, 4, 5씩 증가하는데 카운팅된 횟수를 인덱스로 참고할 때는 5 4 3 2 1씩 마지막 인덱스 번호부터 시작하 때문에 스캔을 마지막부터해야 stable 함
++calloc 함수가 동적으로 확보하는 메모리의 모든 값은 0으로 초기화됨
#counting sort
void countSort(int* arr, int nmemb, int min, int max) {
//calloc은 메모리 할당시 자동으로 값이 o으로 초기화됨
int* FDT = (int*)calloc(max - min + 1, sizeof(int));
int* tmp = (int*)calloc(nmemb, sizeof(int));
//1.도수분포표(Frequency Distribution Table) 만들기
for (int i = 0; i < nmemb; i++)
FDT[arr[i] - min]++; //min 음수일 경우
//2.누적도수분포표(Cumulative Frequency Table) 만들기
for (int i = 1; i < max - min + 1; i++)
FDT[i] += FDT[i - 1];
//3.목적 배열 만들기
for (int i = nmemb - 1; i >= 0; i--)
tmp[--FDT[arr[i] - min]] = arr[i];
//4.배열 복사하기
for (int i = 0; i < nmemb; i++)
arr[i] = tmp[i];
free(FDT);
free(tmp);
}07 집합
집합(set)이란 객관적으로 범위를 규정한 '어떤 것'의 모임이며, 그 집합 안에서 각각의 '어떤 것'을 원소(element)라고 부릅니다.
//Z : 정수; 독일어 Zhal(수)이라는 단어의 앞 글자를 따옴
집합에 포함되는 원소는 서로 달라야 합니다. 또한 집합은 집합을 원소로 가질 수 있습니다. (원소의 중복을 허용하는 집합은 다중 집합(multiset)이라고 하며, 집합과는 구별해서 부릅니다.)
- 무한집합(infinite set) : 정수의 집합처럼 원소의 개수가 무한한 집합
- 유한집합(finite set) : 원소의 개수가 유한한 집합
- 공집합(empty set) : 원소가 하나도 없는 집합
- 부분집합(subset) : 다른 집합에 포함된 집합
- 진부분집합(proper subset) : 부분집합이면서 원래 집합과 같지 않음
- 합집합(union)
- 교집합(intersection)
- 여집합(complement set)
- 차집합(relative complement, set difference) : 여집합을 일반화한 개념
- 대칭 차집합(symmetric difference) : 두 집합 A, B가 있을 때 공통 부분을 뺀 나머지 원소들의 집합
- 전체 집합(universal set) : 대상이 되는 모든 원소를 포함한 집합
#비트 벡터
중복되지 않는 정수집합을 비트로 나타내는 방식 - 자리에 해당하는 수에 0, 1을 사용하여 표현 -> 메모리 사용량이 크게 감소함 #link
8 문자열 검색
문자열(string) : 프로그램에서 문자의 '나열'을 나타냄
#문자열 리터럴(string literal)
C언어에서는 "STRING"이나 "ABC"처럼 문자의 나열을 2개의 큰따옴표로 묶은 것을 string literal이라고 합니다. 문자열 안의 문자는 메모리 공간에 연속으로 배치됩니다. 컴퓨터는 문자열 리터럴의 끝을 나타내기 위해 Null character를 자동으로 추가합니다. 널 문자는 내부 컴퓨터 환경이나 문자 코드에 관계없이 모든 비트의 값이 0입니다.
문자열 리터럴의 특징
- 문자열 리터럴의 자료형은 char형 배열입니다. 그러나 문자열 리터럴의 표현식을 평가하여 얻는 자료형은 char*형이고 그 값은 첫 번째 문자에 대한 포인터입니다.
- 문자열 리터럴의 메모리 영역 기간은 정적 메모리 영역의 기간과 같습니다. 그러므로 프로그램의 시작부터 끝까지 메모리 영역이 유지됩니다.
- 같은 문자열 리터럴이 여러 개 있는 경우에는 이를 각각 다른 메모리 영역에 넣어두는 컴퓨터 환경도 있고 같은 영역에 넣어두고 공유하는 컴퓨터 환경도 있습니다.
- 문자열 리터럴은 변수가 아니라 상수의 성질을 가지고 있습니다. 즉, 문자열 리터럴이 저장된 메모리 영역에 값을 대입할 수 없습니다.
(CHAR_BIT + 3) / 4 ; 비트수를 바이트로 변환 3을 더하는 이유는 반올림 해주기 위해서 (9, 10, 11bit to byte)
++CHAR_BIT (limits.h) : 1바이트의 비트수; 지금과 달리 예전에는 2의 제곱수가 아니라 10 12 18비트와 같은 컴퓨터들이 있었는데 C언어는 다양한 비트 단위를 갖는 하드웨어를 지원해야 했으므로 C언어는 데이터 모델이 있다. 데이터 모델에 따라 자료형 비트가 달라진다. (don't rely on 1 byte being 8 bit in size use CHAR_BIT instead of 8 as a constant to convert between bits and bytes) #link
//문자열 초기화 방식
char st[10] = { 'A', 'B','C', 'D', '\0'};
char st[10] = "ABCD";
//오류
st1[10] = { 'A', 'B','C', 'D', '\0'};
st2[10] = "ABCD";
//*x++ *x값을 쓰고 주소증가++문자열의 길이 : NULL 문자 제외한 문자의 개수를 의미
문자열 끝에는 반드시 널 문자가 있습니다. 따라서 검색에 실패하는 경우는 없습니다. -> 보초법
int str_len(const char* s) {
int len = 0;
while (*s++)
len++;
return len;
}
int str_len2(const char* s) {
const char* p = s;
while (*s)
s++;
return s - p;
}
#strlen 함수
헤더 : string.h
형식 : size_t strlen(const char* s);
반환값 : 구한 문자열의 길이를 반환합니다.
#strchr 함수
헤더 : string.h
형식 : char* strchr(const char* s, int c);
해설 : s가 가리키는 문자열에서 가장 앞쪽에 있는 c를 찾습니다. 이때 c는 널 문자여도 됩니다.
반환값 : 찾은 문자에 대한 포인터를 반환합니다. 문자가 없으면 널 포인터를 반환합니다.
#strrchr 함수
헤더 : string.h
형식 : char* strrchr(const char* s, int c);
해설 : s가 가리키는 문자열 가운데 가장 뒤쪽에 있는 c를 찾습니다. 이때 c는 널 문자여도 됩니다.
반환값 : 찾은 문자에 대한 포인터를 반환합니다. 문자가 없으면 널 포인터를 반환합니다.
초기의 C 언어는 함수로 전달하는 매개변수로 char형이나 short형 등의 값을 먼저 int형으로 형 변환을 했기 때뭇에 표준 라이브러리 함수에서 '문자'를 주고 받을 때는 char형이 아니라 int형으로 주고받습니다.
#strcmp 함수
헤더 : string.h
형식 : int strcmp(const char* s1, const char* s2);
해설 : s1, s2가 가리키는 문자열의 대소 관계를 비교합니다. 처음부터 순서대로 한 문자씩 unsigned char형 값으로 비교합니다.
반환값 : 문자열이 같으면 0, s1이 s2보다 크면 양의 정수, 작으면 음의 정수 값을 반환합니다.
#strncmp 함수
헤더 : string.h
형식 : int strncmp(const char* s1, const char* s2, size_t n);
해설 : s1, s2가 가리키는 문자 배열에서 n번째 문자까지의 대소 관계를 비교합니다. 처음부터 순서대로 한 문자씩 unsigned char형 값으로 비교합니다. NULL 문자 이후의 비교는 하지 않습니다.
반환값 : 문자 배열이 같으면 0, s1이 s2보다 크면 양의 정수 값, 작으면 음의 정수 값을 반환합니다.
#tolower, toupper 함수
헤더 : ctype.h
형식 : int tolower(int c), int toupper(int c)
해설 : tolower는 대문자만 소문자로 변경하고 다른 문자는 그대로 반환, toupper은 소문자만 대문자로 변경 다른 문자는 그대로 반환하는 함수
문자열 검색(string searching)이란?
문자열 검색이란 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고 들어 있다면 그 위치를 찾아내는 것을 말합니다. 검색할 문자열을 패턴(pattern)이라 하고 문자열 원본을 텍스트(text)라고 하자.
#브루트-포스법(Brute force method)
브루트-포스법은 선형 검색을 확장한 알고리즘이므로 단순법, 소박법이라고도 합니다.
텍스트와 패턴을 첫번째 자리수부터 마지막까지 비교한 뒤 하나라도 다른게 있다면 검사할 텍스트의 포인터 위치를 한 칸 앞으로 옮기고 이 과정을 문자열을 찾을 때까지(또는 '\0'\을 만날 때까지) 반복함
int bf_searching(const char txt[], const char pat[]) {
int pt = 0, pp = 0;
while (txt[pt] != '\0' && pat[pp] != '\0') {
if (txt[pt] == pat[pp]) {
pt++; pp++;
}
else {
pt = pt - pp + 1;
pp = 0;
}
}
if (pat[pp] == '\0')
return pt - pp;
return -1;
}
#KMP법
"연속으로 일치한 문자열에서 접두사와 접미사가 같은 경우가 있을 때 중간 과정을 생략하고 접미사를 접두사의 위치로 점프시킴"
브루트-포스법은 다른 문자를 만나면 패턴에서 문자를 검사했던 위치 결과를 버리고 다음 텍스트의 위치로 1칸 이동한 다음 다시 패턴의 첫 번째 문자부터 검사합니다. 이와 달리 KMP법은 검사했던 위치 결과를 버리지 않고 이를 효율적으로 활용하는 알고리즘입니다.
KMP법은 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구합니다. 이런 방법으로 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높입니다.
몇 번째 문자부터 다시 검색을 시작할지 패턴을 이동시킬 때마다 다시 계산해야 한다면 높은 효율을 기대할 수 없습니다. 그래서
'몇 번째 문자부터 다시 검색할지'에 대한 값을 미리 '표'로 만들어 이 문제를 해결합니다.
string matching의 시간복잡도를 O(n)으로 함
검색하려는 pattern으로 중복을 체크해 skiptable을 만들고 txt 인덱스를 가리는 pt를 움직여서 문자열을 검색함
#KMP법
int KMP_searching(const char txt[], const char pat[]) {
int pt = 1, pp = 0;
char* skipTable = (char*)calloc(strlen(pat) + 1, sizeof(char));
if (skipTable == NULL) return -1;
//skip table 작성
while (pat[pt] != '\0') {
if (pat[pt] == pat[pp]) {
skipTable[++pt] = ++pp;
}
else if (pp == 0) {
skipTable[++pt] = pp;
}
else {
pp = skipTable[pp];
}
}
pt = pp = 0;
while (txt[pt] != '\0' && pat[pp] != '\0') {
if (txt[pt] == pat[pp]) {
pt++; pp++;
}
else if (pp == 0)
pt++;
else
pp = skipTable[pp];
}
free(skipTable);
if (pat[pp] == '\0')
return pt - pp;
return -1;
}
#Boyer-Moore string-search algorithm
보이어-무어 알고리즘은 KMP법처럼 스킵하기 위한 테이블을 모든 문자별로 작성( static tables for computing the pattern shifts ) (UCHAR_MAX_ + 1 크기)
preprocess 과정을 txt가 아닌 pattern에 대해서만 함. 패턴이 텍스트보다 짧거나 multiple searche에 적합한 알고리즘임
The algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text). It is thus well-suited for applications in which the pattern is much shorter than the text or where it persists across multiple searches.
보이어-무어 알고리즘은 일반적으로 패턴의 길이가 길어질수록 빠르게 작동하고 주요 특징으로는 tail부터 match를 시작하며 static tables을 사용해 검색이 불필요한 문자들을 스킵함
The Boyer–Moore algorithm uses information gathered during the preprocess step to skip sections of the text, resulting in a lower constant factor than many other string search algorithms. In general, the algorithm runs faster as the pattern length increases. The key features of the algorithm are to match on the tail of the pattern rather than the head, and to skip along the text in jumps of multiple characters rather than searching every single character in the text.
패턴 문자열의 길이가 n일 때 옮길 크기는 아래와 같음
- 패턴에 들어 있지 않은 문자를 만난 경우 : 패턴을 옮길 크기는 n
- 패턴에 들어 있는 문자를 만난 경우 : 마지막에 나오는 위치의 인덱스가 k이면 패턴을 옮길 크기는 n-k-1, 같은 문자가 패턴 안에 중복해서 들어 있지 않다면 패턴을 옮길 크기는 n ('ABAC'
table의 값은 tail에서 얼마만큼 떨어져 있는지만 보기 때문에 위 그림과 같이 뒤에 있는 A와 일치하는 경우 table에서의 값만큼 pt를 이동 시키면 문자열을 찾을 수 없다. 따라서 테이블에서 구한 이동 값의 크기가 ptr_len - pp 의 길이보다 작다면 위 그림과 같은 경우로 판단하고 pt를 ptr_len + pp만큼 이동시킨다.
#Boye-Moore법
int BM_searching(const char* txt, const char* pat) {
int pt, pp;
int txt_len = strlen(txt);
int pat_len = strlen(pat);
char skip[UCHAR_MAX + 1];
//skip table 작성
for (pt = 0; pt <= UCHAR_MAX; pt++)
skip[pt] = pat_len;
for (pt = 0; pt < pat_len - 1; pt++) //마지막 문자 제외
skip[pat[pt]] = pat_len - pt - 1;
//string-searching
while (pt < txt_len) {
pp = pat_len - 1;
while (txt[pt] == pat[pp]) {
if (!pp) return pt;
pp--; pt--;
}
pt += (skip[txt[pt]] > pat_len - pp) ? skip[txt[pt]] : pat_len - pp;
}
return -1;
}
%ld 서식 지정자는 'long int' 자료형을 출력하기 위한 것입니다. 포인터 간의 차이를 나타내는 값은 일반적으로 long int 형식으로 캐스팅됩니다.
텍스의 문자 개수가 n이고 패턴의 문자 개수가 m이라고 할 때 위에서 살펴본 세가지 문자열 검색 알고리즘의 시간 복잡도
- 브루트-포스법 : O(mn)이지만 일부러 꾸민 패턴이 아니라면 O(n)
- KMP법 : O(n) 처리가 복잡하고 패턴 안에 반복이 없으면 효율 좋지 않음 그러나 검사하는 위치를 앞으로 되돌릴 필요가 없다는 특징이 있어 순서 파일을 읽어 들이며 검색할 때 많이 사용함
- Boyer-Moore법 : 가장 나쁜 경우 O(n) 평균적으로는 O(n/m)
#strstr 함수
헤더 : string.h
형식 : char *strstr(const char *s1, const char *s2);
해설 : S1이 가리키는 문자열에서 s2가 가리키는 문자열과 일치하는 (널 문자를 포함하지 않는) 문자열을 찾습니다. 가장 앞쪽에 나오는 문자열을 찾습니다.
반환값 : 찾아낸 문자열에 대한 포인터(첫 번째 문자에 대한 포인터)를 반환합니다. 찾지 못하면 널 포인터를 반환합니다. s2가 길이가 0인 문자열이면 s1을 반환합니다.
++ s -= a - b - c; == s = s - (a - b - c);
9 리스트
리스트는 데이터를 순서대로 나열한(줄지어 늘어놓은) 자료구조입니다.
#선형리스트
++스택과 큐도 리스트 구조
리스트는 데이터를 순서대로 나열해 놓은 자료구조를 말합니다. 가장 단순한 구조를 가진 리스트를 선형 리스트(linear list) 또는 연결 리스트(linked list)라고 합니다. 연결 리스트에서 데이터는(node) 또는 요소(element)라고 합니다. 각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있습니다. 처음과 끝에 있는 노드는 특별히 각각 머리 노드(head node), 꼬리 노드(tail node)라고 합니다. 또한 하나의 노드에 대해 바로 앞에 있는 노드를 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드를 다음 노드(successor node)라고 합니다.
배열로 구현한 선형리스트가 같는 문제
- 쌓이는 데이터의 크기를 미리 알아야 합니다.
- 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 않습니다.
#포인터로 연결 리스트 만들기
연결 리스트에 데이터를 삽입할 때 노드용 객체를 만들고, 삭제할 때 노드용 객체를 없애면 앞에서 제시한(배열로 구현한 선형리스트) 데이터를 밀고 당기는 문제를 해결할 수 있습니다.
자기 자신과 같은 자료형의 객체를 가리키는 데이터를 가지고 있는 자료구조를 자기 참조(self-referential)형이라고 합니다.
#자기 참조 구조체와 typedef 선언
/*--- 노드 ---*/
typedef struct __node {
Member data; /* 데이터 */
struct __node* next; /* 뒤쪽 포인터(뒤쪽 노드에 대한 포인터) */
} Node;구조체 Node는 자기 참조형이고 멤버 next는 struct __node형 객체를 가리키는 포인터입니다. 자기 참조라는 말에 속아 멤버 next가 '자기 자신을 가리키는 포인터'라고 잘못 생각할 수도 있습니다. 하지만 여기서 말하는 '자기 참조 구조체'란 '자기 자신과 같은 자료형의 객체를 가리키는 포인터(struct__node)를 멤버로 가지고 있다.'라는 뜻입니다.
#연결 리스트
typedef struct __node {
type data;
struct __node* next;
}Node;
typedef struct {
Node* head;
Node* crnt;
}List;
static Node* AllocNode(){
return calloc(1, sizeof(Node);
}
static void SetNode(Node* n, const type* data, const Node* next){
n->data = *data;
n-next = next;
}
//type == member
/*--- 머리에 노드를 삽입 ---*/
void InsertFront(List* list, const Member* x) {
Node* ptr = list->head;
list->head = list->crnt = AllocNode();
SetNode(list->head, x, ptr);
}
/*--- 꼬리에 노드를 삽입 ---*/
void InsertRear(List* list, const Member* x) {
if (list->head == NULL) {
InsertFront(list, x);
}
else {
Node* ptr = list->head;
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = list->crnt = AllocNode();
SetNode(ptr->next, x, NULL);
}
}
/*--- 머리 노드를 삭제 ---*/
void RemoveFront(List* list) {
if (list->head == NULL)
return;
Node* ptr = list->head->next;
free(list->head);
list->head = list->crnt = ptr;
}
/*--- 꼬리 노드를 삭제 ---*/
void RemoveRear(List* list) {
if (list->head == NULL)
return;
if (list->head->next == NULL) {
RemoveFront(list);
}
else {
Node* ptr = list->head;
Node* pre = ptr;
while (ptr->next != NULL) {
pre = ptr;
ptr = ptr->next;
}
pre->next = NULL;
free(ptr);
list->crnt = pre;
}
}
/*--- 선택한 노드를 삭제 ---*/
void RemoveCurrent(List* list) {
if (list->crnt == list->head) {
RemoveFront(list);
}
else {
Node* pre = list->head;
while (pre->next != list->crnt)
pre = pre->next;
pre->next = list->crnt->next;
free(list->crnt);
list->crnt = pre;
}
}
/*--- 모든 노드를 삭제 ---*/
void Clear(List* list) {
while (list->head != NULL) {
RemoveFront(list);
}
}
/*--- 선형 리스트 종료 ---*/
void Terminate(List* list) {
Clear(list);
}
//PULGE
void Purge(List* list, int compare(const Member* x, const Member* y)) {
Node* ptr = list->head;
while (ptr != NULL) {
Node* ptr2 = ptr;
Node* pre = ptr;
while (pre->next != NULL) {
ptr2 = pre->next;
if (!compare(&ptr->data, &ptr2->data)) {
pre->next = ptr2->next;
free(ptr2);
}
else {
pre = ptr2;
}
}
ptr = ptr->next;
}
list->crnt = list->head;
}
//RETRIEVE
Node* Retrieve(List* list, int n) {
Node* ptr = list->head;
while (ptr != NULL && n >= 0) {
if (n-- == 0) {
list->crnt = ptr;
return ptr;
}
ptr = ptr->next;
}
return NULL;
}
#커서로 연결 리스트 만들기
연결 리스트는 배열로 만든 리스트와 다르게 '노드의 삽입, 삭제를 데이터 이동 없이 수행한다'라는 특징이 있었지만 삽입, 삭제를 수행할 때 마다 노드용 객체를 위한 메모리 영역을 만들고 해제하는 과정이 필요합니다. 메모리 영역을 만들고 해제하는 데 필요한 비용은 결코 무시할 수 없습니다. 이때 프로그램 실행 중에 데이터의 개수가 크게 바뀌지 않고 데이터 개수의 최댓값을 미리 알 수 있다고 가정하면 배열을 사용해 효율적으로 연결 리스트를 운용할 수 있습니다.
베열의 커서에 해당하는 값은 다음 노드에 대한 포인터가 아니라 다음 노드가 들어 있는 요소의 인덱스에 대한 값입니다. 여기서 포인터 역할을 하는 인덱스를 커서(cursor)라고 합니다.
커서로 만든 연결 리스트에서 삭제를 여러 번 하면 배열은 빈 레코드가 너무 많아져 효율이 떨어집니다. 즉, 비어 있는 레코드를 효율적으로 활용해야 합니다. '사용하지 않는 빈 배열'의 문제를 해결하기 위해 삭제한 레코드를 관리하기 위한 자료구조 프리 리스트(free list)를 만듭니다. (free list는 cursor list idx는 같은 구조체)
#커서로 만든 연결 리스트
#define Null -1 /* 빈 커서 */
typedef int Index; /* 커서 형 */
/*--- 노드 ---*/
typedef struct {
Member data; /* 데이터 */
Index next; /* 뒤쪽노드 */
Index Dnext; /* 프리 리스트의 뒤쪽노드 */
} Node;
/*--- 선형 리스트 ---*/
typedef struct {
Node* n; /* 리스트 본체(배열) */
Index head; /* 머리노드 */
Index max; /* 사용 중인 꼬리 레코드 */
Index deleted; /* 프리 리스트의 머리노드 */
Index crnt; /* 주목노드 */
} List;
------------------------------------------------------------------------
/*--- 삽입할 레코드의 인덱스를 구한다. ---*/
static Index GetIndex(List *list)
{
if (list->deleted == Null) /* 삭제할 레코드가 없는 경우 */
return ++(list->max);
else {
Index rec = list->deleted;
list->deleted = list->n[rec].Dnext;
return rec;
}
}
/*--- 지정된 레코드를 삭제 리스트에 등록한다. ---*/
static void DeleteIndex(List *list, Index idx)
{
if (list->deleted == Null) { /* 삭제할 레코드가 없는 경우 */
list->deleted = idx;
list->n[idx].Dnext = NULL;
}
else {
Index ptr = list->deleted;
list->deleted = idx;
list->n[idx].Dnext = ptr;
}
}
/*--- n이 가리키는 노드의 각 멤버에 값을 설정 ----*/
static void SetNode(Node *n, const Member *x, Index next)
{
n->data = *x; /* 데이터 */
n->next = next; /* 뒤쪽노드에 대한 포인터 */
}
/*--- 선형 리스트를 초기화(가장 큰 요소수는 size) ---*/
void Initialize(List *list, int size)
{
list->n = calloc(size, sizeof(Node));
list->head = Null; /* 머리노드 */
list->crnt = Null; /* 주목노드 */
list->max = Null;
list->deleted = Null;
}
/*--- 함수 compare 의해 x와 같은 노드를 검색 ---*/
Index search(List *list, const Member *x, int compare(const Member *x, const Member *y))
{
Index ptr = list->head;
while (ptr != Null) {
if (compare(&list->n[ptr].data, x) == 0) {
list->crnt = ptr;
return ptr; /* 검색 성공 */
}
ptr = list->n[ptr].next;
}
return Null; /* 검색 실패 */
}
/*--- 머리에 노드를 삽입 ---*/
void InsertFront(List *list, const Member *x)
{
Index ptr = list->head;
list->head = list->crnt = GetIndex(list);
SetNode(&list->n[list->head], x, ptr);
}
/*--- 꼬리에 노드를 삽입 ---*/
void InsertRear(List *list, const Member *x)
{
if (list->head == Null) /* 비어있는 경우 */
InsertFront(list, x); /* 머리에 삽입 */
else {
Index ptr = list->head;
while (list->n[ptr].next != Null)
ptr = list->n[ptr].next;
list->n[ptr].next = list->crnt = GetIndex(list);
SetNode(&list->n[list->n[ptr].next], x, Null);
}
}
/*--- 머리노드를 삭제 ---*/
void RemoveFront(List *list)
{
if (list->head != Null) {
Index ptr = list->n[list->head].next;
DeleteIndex(list, list->head);
list->head = list->crnt = ptr;
}
}
/*--- 꼬리노드를 삭제 ---*/
void RemoveRear(List *list)
{
if (list->head != Null) {
if (list->n[list->head].next == Null) /* 노드가 하나만 있으면 */
RemoveFront(list); /* 머리노드를 삭제 */
else {
Index ptr = list->head;
Index pre;
while (list->n[ptr].next != Null) {
pre = ptr;
ptr = list->n[ptr].next;
}
list->n[pre].next = Null;
DeleteIndex(list, ptr);
list->crnt = pre;
}
}
}
/*--- 주목노드를 삭제 ---*/
void RemoveCurrent(List *list)
{
if (list->head != Null) {
if (list->crnt == list->head) /* 머리노드를 주목하고 있으면 */
RemoveFront(list); /* 머리노드를 삭제 */
else {
Index ptr = list->head;
while (list->n[ptr].next != list->crnt)
ptr = list->n[ptr].next;
list->n[ptr].next = list->n[list->crnt].next;
DeleteIndex(list, list->crnt);
list->crnt = ptr;
}
}
}
/*--- 모든 노드를 삭제 ---*/
void Clear(List *list)
{
while (list->head != Null) /* 텅 빌 때까지 */
RemoveFront(list); /* 머리노드를 삭제 */
list->crnt = Null;
}
/*--- 선형 리스트의 뒤처리 ---*/
void Terminate(List *list)
{
Clear(list); /* 모든 노드를 삭제 */
free(list->n);
}
#원형 리스트
위 그림과 같이 선형 리스트의 꼬리 노드가 머리 노드를 가리키면 원형 리스트(circular list)라고 합니다. 원형 리스트는 고리 모양으로 나열된 데이터를 저장할 때 알맞은 자료구조입니다.
원형 리스트와 선형 리스트의 차이점은 꼬리 노드의 다음 노드를 가리키는 포인터가 NULL이 아니라 머리 노드의 포인터 값이라는 점입니다.
- 빈 원형 리스트를 판단하는 방법 : list->head == NULL
- 노드가 1개인 원형 리스트를 판단하는 방법 : list->head->next == list->head
- p가 가리키는 노드가 머리 노드인지 판단하는 방법 : p == list->head
- p가 가리키는 노드가 꼬리 노드인지 판단하는 방법 : p->next == list->head
#이중 연결 리스트
선형 리스트의 가장 큰 단점은 다음 노드는 찾기 쉽지만 앞쪽의 노드는 찾을 수 없다는 점입니다. 이 단점을 개선한 자료구조가 이중 연결 리스트(doubly linked list)입니다. (이중 연결 리스트는 양방향 리스트라고도 합니다.)
- 포인터 p가 머리 노드인지 판단하는 방법 : p->prev== NULL || p == list->head
- 포인터 p가 꼬리 노드인지 판단하는 방법 : p->next== NULL
#원형 이중 연결 리스트
원형 리스트와 이중 연결 리스트 개념을 합친 원형 이중 연결 리스트(circular doubly linked list)
- p가 가리키는 노드가 머리 노드인지 확인하는 방법 : p->prev == list->head //list->head는 더미 노드
- p가 가리키는 노드가 꼬리 노드인지 확인하는 방법 : p->next == list->head
10 트리
트리(tree)는 데이터 사이의 계층 관계를 나타내느 자료구조입니다.
#트리 관련 용어
- Root(루트) : 트리의 가장 윗부분에 위치한 노드
- Leaf(리프) : 트리의 가장 아랫부분에 위치한 노드; termianal node, external node
- non-external node(안쪽 노드) : 루트를 포함하여 리프를 제외한 노드; non-external node
- Child(자식) : 어떤 노드로부터 가지로 연결된 아래쪽 노드, 노드는 여러 자식을 가질 수 있음
- Parent(부모) : 어떤 노드에서 가지로 연결된 위쪽 노드, 노드는 1개의 부모를 가짐
- Sibling(형제) : 같은 부모를 가지는 노드
- Ancestor(조상) : 어떤 노드에서 가지로 연결된 위쪽 노드 전부
- Descendant(자손) : 어떤 노드에서 가지로 연결된 아래쪽 노드 전부
- Level(레벨) : 루트로부터 얼마나 떨어져 있는지에 대한 값, 루트의 레벨은 0이고 가지가 늘수록 레벨이 1씩 증가함
- Degree(차수) : 노드가 갖는 자식의 수, 모든 노드의 차수가 n이하인 트리를 n진 트리라고 함
- Height(높이) : 루트부터 가장 멀리 떨어진 리프까지의 거리(리프 레벨의 최댓값)
- Subtree(서브 트리) : 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리
- Null tree(널 트리) : 노드, 가지가 없는 트리
- Ordered tree(순서 트리) & Unordered tree(무순서 트리) : 형제 노드의 순서가 있는지 없는지에 따라 구분
#순서 트리 탐색
순서 트리 탐색에 두가지 방법 BFS, DFS
- 너비 우선 탐색 (Breadth-First Search)
너비 우선 탐색은 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고 한 레벨에서의 검색이 끝나면 다음 레벨로 내려갑니다.
A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> L
- 깊이 우선 탐색 (Depth-First Search)
깊이 우선 탐색은 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법입니다. 리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우에는 부모에게 돌아갑니다. 그런 다음 다시 자식 노드로 내려갑니다. 깊이 우선 탐색을 진행하면서 '언제 노드를 방문할지'는 다음과 같이 세 종류로 구분합니다.
1. 전위 순회 (Preorder) : 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식
A -> B -> D -> H -> E -> I -> J -> C -> F -> K -> L -> G
2.중위 순회 (Inorder) : 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식
H -> D -> B -> I -> E -> J -> A -> K -> F -> L -> C -> G
3.후위 순회 (Postorder) : 왼쪽 자식 -> 오른쪽 자식 -> (돌아와) 노드 방문
H -> D -> I -> J -> E -> B -> K -> L -> F -> G -> C -> A
#이진트리와 이진검색트리
- 이진트리 (binary tree) : 노드가 왼쪽 자식과 오른쪽 자식을 갖고 이때 각 노드의 자식이 2명 이하로 유지되는 트리
- 완전이진트리 (complete binary tree) : 루트부터 노드가 "채워져 있으면서" 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리
채우는 조건
1.마지막 레벨을 제외한 레벨은 노드를 가득 채웁니다.
2.마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되 반드시 끝까지 채울 필요는 없습니다.
높이가 k인 완전이진트리가 가질 수 있는 노드의 최댓값 : 2^(k + 1) - 1
n개의 노드를 저장할 수 있는 완전이진트리의 높이 : log n
- 이진검색트리(binary search tree) : 아래의 조건을 만족하는 이진트리
1.어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 합니다.
2.오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 합니다.
3.같은 키 값을 갖는 노드는 없습니다.
이때 이진검색트리를 중위순회(Inorder) 하면 키 값의 오름차순으로 노드를 얻을 수 있습니다.
#이진검색트리 출력 (중위순회 이용)
void PrintTree(const BinNode* p) {
if (p == NULL)
return;
PrintTree(p->left);
PrintLnMember(&p->data);
PrintTree(p->right);
}
#이진검색트리 삽입 & 검색
//search Data
BinNode* Search(BinNode* p, const Member* x) {
if (p == NULL)
return p;
int cmp = MemberNoCmp(&p->data, x);
if (!cmp)
return p;
else if (cmp == 1)
Search(p->left, x);
else
Search(p->right, x);
}
//Add Data
BinNode* Add(BinNode* p, const Member* x) {
int cmp;
if (p == NULL) {
p = AllocBinNode();
SetBinNode(p, x, NULL, NULL);
}
else if ((cmp = MemberNoCmp(&p->data, x)) == 0) {
printf("ERR : You input the data that was registered already\n");
}
else if (cmp == 1)
p->left = Add(p->left, x);
else
p->right = Add(p->right, x);
return p;
}
#이진검색트리 제거
int Remove(BinNode** root, const Member* x) {
BinNode* next, * temp;
BinNode** left;
BinNode** p = root;
while (1) {
int cond;
if (*p = NULL) {
printf("ERR\n");
return -1;
}
else if ((cond = MemberNoCmp(x, &(*p)->data)) == 0)
break;
else if (cond < 0)
p = &((*p)->left);
else
p = &((*p)->right);
}
if ((*p)->left == NULL) {
next = (*p)->right;
}
else {
left = &((*p)->left);
while ((*left)->right != NULL) {
left = &((*left)->right);
}
next = *left;
*left = (*left)->left;
next->left = (*p)->left;
next->right = (*p)->right;
}
temp = *p;
*p = next;
free(temp);
return 0;
}11 해시법
해시법(hashing)은 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것으로, 검색뿐만 아니라 추가, 삭제도 효율적으로 수행하는 방법입니다.
//hash는 '다진 고기 요리', '뒤범벅', '뒤죽박죽', '잡동사니'라는 뜻이 담겨 있습니다.
보통 해시 함수는 '나머지를 구하는 연산' 또는 이런 나머지 연산을 다시 응용한 연산'을 사용합니다. 그리고 해시 테이블의 각 요소를 버킷(bucket)이라고 합니다.
#충돌(collision)
키 값과 해시 값의 대응 관계가 반드시 1대1은 아닙니다 위 그림과 같이 버킷이 중복되는 현상을 충돌(collision)이라고 합니다. 그래서 해시 함수는 가능하면 해시 값이 중복되지 않도록 고르게 분포된 값을 만들어야 합니다.
++
데이터를 추가할 때 충돌이 전혀 발생하지 않는다고 가정하면 검색, 추가, 삭제 작업은 해시 함수를 통한 인덱스 찾기로 대부분 완료됨 -> 시간복잡도 O(1)
데이터 추가 시 해시 테이블을 크게 하면 충돌 발생을 억제할 수 있지만 이 방법은 메모리를 쓸데없이 많이 차지함 -> 시간과 공간의 절출(trade-off) 문제가 항상 따라다님
충돌을 피하기 위해서 해시 함수는 해시 테이블 크기 이하의 정수를 가능한 한 치우치지 않게 고르게 만들어야 함 일반적으로 해시 테이블 크기는 소수가 좋다고 알려짐. 이 밖에도 키 값이 정수가 아닌 경우 해시 값을 구하려면 다른 방법을 사용해야하는데 실수 키 값에 대한 비트 연산(bitwise operaion)을 하는 방법, 문자열 키 값에 대한 각 문자 코드에 곱셈과 덧셈을 하는 방법이 있음
++
#충돌에 대한 대처
1.체인법(chaining) : 같은 해시 값을 갖는 요소를 연결 리스트로 관리
2.오픈 주소법(open adressing) : 빈 버킷을 찾을 때까지 해시를 반복
- 체인법(chaining)은 같은 해시 값을 갖는 데이터를 쇠사슬(chain) 모양으로 연결 리스트에서 연결하는 방법으로, 오픈 해시법(open hashing)이라고도 합니다.
#search
1.해시 함수가 키 값을 해시 값으로 변환합니다.
2.해시 값을 인덱스로 하는 버킷을 선택합니다.
3.선택한 버킷의 연결 리스트를 처음부터 순서대로 검색합니다. 키 값과 같은 값을 찾으면 검색 성공입니다. 끝까지 스캔하여 찾지 못하면 검색 실패입니다.
Node* Search(const ChainHash* h, const Member* x) {
int key = hash(x->no, h->size);
Node* p = h->table[key];
while (p != NULL) {
if (p->data.no == x->no)
return p;
p = p->next;
}
return NULL;
}
/*
typedef struct __node {
Member data;
struct __node* next;
}Node;
typedef struct {
int size;
Node **table;
}ChainHash;
*/
#Add & Remove
1.해시 함수가 키 값을 해시 값으로 변환합니다.
2.해시 값을 인덱스로 하는 버킷을 선택합니다.
3-add.버킷에 저장된 포인터가 가리키는 연결 리스트를 처음부터 순서대로 검색합니다. 연결리스트의 끝까지 키 값과 같은 값이 없다면 리스트의 맨 앞 위치에 노드를 삽입합니다.
3-remove.'' 같은 값을 찾으면 그 노드를 리스트에서 삭제
int Add(ChainHash* h, const Member* x) {
Node* temp;
int key = hash(x->no, h->size);
Node* p = h->table[key];
while (p != NULL) {
if (p->data.no == x->no)
return 1;
p = p->next;
}
if ((temp = calloc(1, sizeof(Node))) == NULL)
return 2;
SetNode(temp, x, h->table[key]);
h->table[key] = temp;
return 0;
}
int Remove(ChainHash* h, const Member* x) {
int key = hash(x->no, h->size);
Node* p = h->table[key];
Node** pp = &h->table[key];
while (p != NULL) {
if (p->data.no == x->no) {
pp = &p->next;
free(p);
return 0;
}
pp = &p->next;
p = p->next;
}
return 1;
}- 오픈 주소법(open addressing)은 충돌이 발생했을 때 재해시(rehashing)를 수행하여 비어 있는 버킷을 찾아내는 방법으로, 닫힌 해시법(closed hashing)이라고도 함. 오픈 주소법은 빈 버킷을 만날 때까지 재해시(rehashin)를 여러 번 반복하므로 연결 탐사법(linear probing)이라고도 합니다.
#요소 삭제 & 요소 검색
//open addressing
typedef enum {
Occupied, Empty, Deleted
} Status;
typedef struct {
Member data;
Status stat;
} Bucket;
typedef struct {
int size;
Bucket *table;
} ClosedHash;
//Search
Bucket *Search(const ClosedHash *h, const Member *x)
{
int i;
int key = hash(x->name, h->size);
Bucket *p = &h->table[key];
for (i = 0; p->stat != Empty && i < h->size; i++) {
if (p->stat == Occupied && !strcmp(p->data.name, x->name))
return p;
key = rehash(key, h->size);
p = &h->table[key];
}
return NULL;
}
//ADD
int Add(ClosedHash *h, const Member *x)
{
int i;
int key = hash(x->name, h->size);
Bucket *p = &h->table[key];
if (Search(h, x))
return 1;
for (i = 0; i < h->size; i++) {
if (p->stat == Empty || p->stat == Deleted) {
SetBucket(p, x, Occupied);
return 0;
}
key = rehash(key, h->size);
p = &h->table[key];
}
return 2;
}
//REMOVE
int Remove(ClosedHash *h, const Member *x)
{
Bucket *p = Search(h, x);
if (p == NULL)
return 1;
p->stat = Deleted;
return 0;
}remind
1.기본 알고리즘, 2.기본 자료구조
세 값의 최댓값, 에라토스테네스의 체(어떤 정수 n은 n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다면 소수임), 함수 매크로 do ~ while()
3.검색 알고리즘
선형 검색-보초법, 이진 검색, 해시법(체인법, 오픈 주소법), 함수 포인터, bsearch()
4.스택과 큐
스택-후입선출, 큐-선입선출-링 버퍼, deck(duque/double ended queue)
5.재귀 알고리즘
Euclidean method of mutual division, 하향식 분석&상향식 분석, Towers of Hanoi, 8-Queen problem, 분할 정복
6.정렬
내부 정렬&외부 정렬, 교환&선택&삽입, (버블 정렬-양방향 버블 정렬, 단순 선택 정렬, 단순 삽입 정렬)~O(n^2), 셸 정렬-증분값(h 값이 서로 배수가 되지 않아야 함; h= h*3 + 1)~O(n^1.25), 퀵 정렬-피벗 선택하기~O(nlogn), 병합 정렬~O(nlogn), 힙 정렬~O(nlogn), 도수 정렬, qsort()
7.집합
비트 벡터, symmetric difference
8.문자열 검색
문자열 리터럴, 브루트-포스법~O(mn)~O(n), KMP법~O(n), Boyer-Moore법~O(n)~O(n/m), strlen(), strchr(), strrchr(), strcmp(), strncmp(), strstr()
9.리스트
선형 리스트, 포인터로 만든 연결 리스트, 커서로 만든 연결 리스트-프리 리스트, 원형 리스트, 이중 연결 리스트, 원형 이중 연결 리스트
10.트리
너비 우선 탐색&깊이 우선 탐색, preorder&in order&postorder, 이진트리, 완전이진트리, 이진검색트리
11.해시법
Chaining, Open addressing
'개인공부용1 > cs' 카테고리의 다른 글
| 시작하세요! C# 12 프로그래밍 - 2부 (0) | 2024.07.14 |
|---|---|
| 정규표현식 (0) | 2024.07.11 |
| 혼자 공부하는 컴퓨터 구조 + 운영체제 (1) | 2024.06.18 |
| Bresenham's line algorithm (0) | 2024.02.07 |
| Portable Network Graphics (PNG) Specification (Third Edition) (0) | 2024.01.27 |
