[알고리즘] 탐색 알고리즘 (C언어 - 연결리스트 구현)

💻 오늘의 목표 : 탐색 알고리즘 완전 정복

 

😊 오늘 공부할 알고리즘은 탐색 알고리즘 😊

 

[탐색 알고리즘]

[탐색 알고리즘의 개념]

[탐색이란?]

• 탐색 : Search

• 여러 데이터들 중 내가 원하는 데이터를 찾는 과정

[탐색의 필요성]

• 사전에서 영어 단어 찾기, 도서관에서 책 찾기
• 데이터베이스나 리스트에서 원하는 데이터 찾기

많은 데이터나 자료에서 내가 원하는 값을 찾아내는 탐색은 어디에나 필요하다.

 

[탐색 알고리즘의 종류]

탐색 알고리즘에는 정말 많은 종류의 알고리즘이 있다.

• 순차 탐색
• 이진 탐색
• 너비 우선 탐색
• 깊이 우선 탐색
• 다익스트라 알고리즘

이 외에도 많은 알고리즘이 있으므로 때에 따라 알고리즘의 특징에 따라 원하는 알고리즘을 선택하여 구현하면 되는 것!

---

[순차 탐색(Sequential Search)]

가장 먼저 알아볼 탐색 알고리즘은 순차 탐색 알고리즘이다.

[순차 탐색이란?]

말 그대로 순차적으로 맨 앞에서부터 차례차례 모든 데이터를 비교하여 원하는 데이터를 찾는 알고리즘이다.

한쪽 방향으로만 탐색할 수 있는 알고리즘이어서 선형탐색이라고도 부른다.

• 순차 탐색 = 선형 탐색

말만 들어도 맨 앞에서부터 순차적으로 탐색하는 것은 별로 성능이 좋아 보이지는 않는다

 

[순차 탐색의 특징]

• 구현이 간단하다
• 정렬되지 않은 리스트에도 사용 가능하다
• 데이터가 많은 리스트는 비효율적일 수 있다.
• 최악의 경우 모든 원소를 다 확인해야 하므로 시간 복잡도는 O(n)이다.

[순차 탐색 C언어 구현]

순차 탐색 알고리즘은 배열, 연결리스트로 모두 어렵지 않게 구현할 수 있다.

 

배열로 구현한 경우

배열로 구현할 경우 맨 처음 배열의 0번 인덱스부터 쭉 순차적으로 확인하는 반복문만 만들어주면 어렵지 않게 구현할 수 있다.

 

연결리스트로 구현한 경우

(더 보기 클릭해서 전체 코드 보기)

#include <stdlib.h>
#include <stdio.h>

typedef int ElementType;

typedef struct makeNode {
	ElementType Data;
	struct makeNode* NextNode;
} Node;

Node* CreateNode(ElementType NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node));

	NewNode->Data = NewData;
	NewNode->NextNode = NULL;

	return NewNode;
}

void DestroyNode(Node* Node) {
	free(Node);
}

void AppendNode(Node** Head, Node* NewNode) {
	if ((*Head) == NULL) {
		*Head = NewNode;
	}
	else {
		Node* Tail = (*Head);
		while (Tail->NextNode != NULL) {
			Tail = Tail->NextNode;
		}
		Tail->NextNode = NewNode;
	}
}

Node* GetNodeAt(Node* Head, int Location) {
	Node* Current = Head;

	while (Current != NULL && (--Location) >= 0) {
		Current = Current->NextNode;
	}

	return Current;
}

void RemoveNode(Node** Head, Node* Remove) {
	if (*Head == Remove) {
		*Head = Remove->NextNode;
	}
	else {
		Node* Current = *Head;
		while (Current != NULL && Current->NextNode != Remove) {
			Current = Current->NextNode;
		}
		if (Current != NULL)
			Current->NextNode = Remove->NextNode;
	}
}

void InsertAfter(Node* Current, Node* NewNode) {
	NewNode->NextNode = Current->NextNode;
	Current->NextNode = NewNode;
}

void InsertNewHead(Node** Head, Node* NewHead) {
	if (Head == NULL)
		(*Head) = NewHead;
	else {
		NewHead->NextNode = (*Head);
		(*Head) = NewHead;
	}
}

int GetNodeCount(Node* Head) {
	int Count = 0;
	Node* Current = Head;

	while (Current != NULL) {
		Current = Current->NextNode;
		Count++;
	}

	return Count;
}

Node* SequentialSearch(Node* Head, int Target) {
	Node* Current = Head;
	Node* Match = NULL;

	while (Current != NULL) {
		if (Current->Data == Target) {
			Match = Current;
			break;
		}
		else
			Current = Current->NextNode;
	}
	return Match;
}

int main() {
	int A, B;
	scanf("%d %d", &A, &B);

	printf("%d %d", B - A, B);

	return 0;
}

 

Node* SequentialSearch(Node* Head, int Target) {
	Node* Current = Head;
	Node* Match = NULL;

	while (Current != NULL) {
		if (Current->Data == Target) {
			Match = Current;
			break;
		}
		else
			Current = Current->NextNode;
	}
	return Match;
}

 

순차 탐색을 연결리스트로 구현하는 경우도 어렵지 않다.

맨 처음 Head 노드부터 시작하여, 내가 원하는 데이터를 가진 요소에 도착할 때까지 다음 노드를 확인하는 반복문으로 쉽게 구현할 수 있다.

---

[자기 구성 순차 탐색 알고리즘]

이렇게 하나하나 차례대로 탐색하는 알고리즘은 데이터 양이 많아질수록 활용도가 떨어진다.

이 알고리즘을 발전시켜 보자!

 

[자기 구성법?]

자주 사용되는 항목을 데이터 앞쪽에 배치함으로써 순차 탐색의 검색 효율을 끌어올리는 방법

(출처 : 이것이 자료구조+알고리즘이다.)

 

• 전진 이동법
• 전위법
• 빈도 계수법

---

[전진 이동법]

전진 이동법이란 탐색된 항목을 데이터의 가장 앞으로 옮기는 방법이다.

 

 

주의해야 할 점은 전진 이동법은 한번 탐색된 항목이 다음에 또다시 검색될 가능성이 높은 데이터에 한해 사용해야 한다.

 

[전진 이동법 C언어 구현]

위에 구현한 연결리스트에 함수로 구현을 했다.

 

Node* MoveToFront(Node** Head, int Target) {
	Node* Current = (*Head);
	Node* Previous = NULL;
	Node* Match = NULL;

	while (Current != NULL) {
		if (Current->Data == Target) {
			Match = Current;
			if (Previous != NULL) {
				//찾아야하는 노드 앞노드를 다음 노드로 연결
				Previous->NextNode = Current->NextNode;
				//찾은 노드를 맨앞으로 옮김
				Current->NextNode = (*Head);
				(*Head) = Current;
			}
			break;
		}

		else {
			Previous = Current;
			Current = Current->NextNode;
		}
	}
	return Match;
}

 

만약 배열로 구현한다면, 탐색해서 찾을 노드와 맨 처음 노드를 바꾸는 형식으로 구현을 해야 할까...?

하나씩 자리 바꾸면서 앞으로 옮기는 작업은 매우 불필요한 작업이 될 것 같다....

 

---

[전위법]

전위법이란, 위치를 바꾸는 방법이다.

탐색된 항목과 이전 항목을 교환하는 알고리즘이다.

전진 이동법은 탐색이 되면 바로 앞으로 옮겨지지만, 전위법은 내가 많이 탐색하면 탐색할수록 점점 앞으로 오는 방법으로, 자주 탐색되는 항목들이 점점 앞쪽으로 모이게 될 것이다.

 

 

전진 이동법은 파일 탐색기의 '최근에 사용한 파일'에 활용될 것 같고, 전위법은 좌측에 자주 사용하는 파일들은 즐겨찾기 항목에 나오는 것에 활용되었을 것 같다.

 

[전위법 C언어 코드 구현(연결리스트)]

Node* Transpose(Node** Head, int Target) {
	Node* Current = (*Head);
	Node* PPrevious = NULL; //이전노드의 이전노드
	Node* Previous = NULL; //이전노드
	Node* Match = NULL;

	while (Current != NULL) {
		if (Current->Data == Target) {
			Match = Current;
			if (Previous != NULL) {
				if (PPrevious != NULL)
					PPrevious->NextNode = Current;
				else
					(*Head) = Current;

				Previous->NextNode = Current->NextNode;
				Current->NextNode = Previous;
			}
			break;
		}

		else {
			if (Previous != NULL)
				PPrevious = Previous;

			Previous = Current;
			Current = Current->NextNode;
		}
	}
	return Match;
}

 

전위법은 앞노드와 자리를 바꾸어주어야 하기 때문에 연결리스트는 이전노드의 이전노드도 저장을 해두어 자리를 바꿀 때, 이전노드의 이전노드에 현재 찾은 노드를 이어주어야 한다.

오히려 이건 배열로 구현할 때가 더 간단하게 구현할 수 있을 것 같다.

(temp 정수형 변수 선언해서 그냥 swap만 간단하게 해 주면 해결되기 때문...)

 

[계수법]

계수법은 데이터의 각 요소가 탐색된 횟수를 별도의 공간에 저장하고, 탐색 횟수가 높은 순서대로 데이터를 재구성하는 방법이다.

전위법은 극단적으로 생각해 봤을 때, 데이터가 100만 개가 있다고 하면, 맨 뒤에 있는 요소는 100만 번을 검색해야지만 맨 앞으로 올 수가 있다... 정작 맨 앞 요소는 그냥 한두 번 검색될 뿐인데 맨 위 중요한 요소는 100만 번의 검색이 필요한 것...

 

이를 해결해기 위한 방법으로 계수법이 있지만, 계수법은 탐색 횟수를 저장해야 하는 공간이 따로 필요하기 때문에 메모리 공간 비용이 더 많이 소요될 것이다.

 

[계수법 C언어 코드 구현]

계수법은 각각의 노드에 탐색 횟수를 저장해야 할 것이다.

 

typedef struct makeNode {
	ElementType Data;
	int cnt;
	struct makeNode* NextNode;
} Node;

Node* CreateNode(ElementType NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node));

	NewNode->Data = NewData;
	NewNode->cnt = 0;
	NewNode->NextNode = NULL;

	return NewNode;
}

 

그래서 일단 노드 안에 cnt라는 변수를 추가했고, CreateNode 부분에 cnt를 0으로 초기화해 줬다.

 

Node* FrequencyCount(Node** Head, int Target) {
	Node* Current = (*Head);
	Node* Previous = NULL; //이전노드
	Node* Match = NULL;

	while (Current != NULL) {
		if (Current->Data == Target) {
			Match = Current;
			//cnt 1증가
			Match->cnt++;
			if (Previous != NULL) {
				//찾아야하는 노드 앞노드를 다음 노드로 연결
				Previous->NextNode = Current->NextNode;
			}
			break;
		}

		else {
			Previous = Current;
			Current = Current->NextNode;
		}
	}

	//현재 Match에 찾은 노드 저장되어있음
	//순서대로 앞에서부터 탐색하면서
	//찾은 노드의 cnt 보다 작은 노드 바로 앞에 다시 저장
	Node* Current = (*Head);
	Node* Previous = NULL; //이전노드

	while (Current != NULL) {
		//찾았는데도 맨 뒤에 노드보다 적게 세어진 경우
		if (Current->NextNode == NULL) {
			Current->NextNode = Match;
		}

		//들어갈 자리 찾은 경우
		if (Current->cnt > Current->NextNode->cnt) {
			if (Previous != NULL) {
				//맞는 자리가 집어넣기
				Current->NextNode = Previous->NextNode;
				Previous->NextNode = Current;
			}
			break;
		}

		else {
			Previous = Current;
			Current = Current->NextNode;
		}
	}
	
	return Match;
}

 

그러고 나서 위와 같은 계수법 함수를 만들었다.

1. 내가 찾아야 하는 노드를 먼저 찾는다

2. 그 노드의 탐색 횟수를 1 증가시킨 후 연결리스트에서 따로 빼둔다.

3. 앞에서부터 차례대로 탐색하면서 찾은 노드가 들어가야 할 자리에 끼워주기

 

노드를 탐색하면서 자리까지 바꿔주면 제일 좋겠지만 탐색 횟수가 변경되고 나면 다시 들어갈 자리를 탐색해주어야 하기 때문에 위와 같은 코드를 구현해 주었다.

 

[최종 연결리스트 탐색 코드]

(더보기 누르기)

 

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

typedef int ElementType;

typedef struct makeNode {
	ElementType Data;
	int cnt;
	struct makeNode* NextNode;
} Node;

Node* CreateNode(ElementType NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node));

	NewNode->Data = NewData;
	NewNode->cnt = 0;
	NewNode->NextNode = NULL;

	return NewNode;
}

void DestroyNode(Node* Node) {
	free(Node);
}

void AppendNode(Node** Head, Node* NewNode) {
	if ((*Head) == NULL) {
		*Head = NewNode;
	}
	else {
		Node* Tail = (*Head);
		while (Tail->NextNode != NULL) {
			Tail = Tail->NextNode;
		}
		Tail->NextNode = NewNode;
	}
}

Node* GetNodeAt(Node* Head, int Location) {
	Node* Current = Head;

	while (Current != NULL && (--Location) >= 0) {
		Current = Current->NextNode;
	}

	return Current;
}

void RemoveNode(Node** Head, Node* Remove) {
	if (*Head == Remove) {
		*Head = Remove->NextNode;
	}
	else {
		Node* Current = *Head;
		while (Current != NULL && Current->NextNode != Remove) {
			Current = Current->NextNode;
		}
		if (Current != NULL)
			Current->NextNode = Remove->NextNode;
	}
}

void InsertAfter(Node* Current, Node* NewNode) {
	NewNode->NextNode = Current->NextNode;
	Current->NextNode = NewNode;
}

void InsertNewHead(Node** Head, Node* NewHead) {
	if (Head == NULL)
		(*Head) = NewHead;
	else {
		NewHead->NextNode = (*Head);
		(*Head) = NewHead;
	}
}

int GetNodeCount(Node* Head) {
	int Count = 0;
	Node* Current = Head;

	while (Current != NULL) {
		Current = Current->NextNode;
		Count++;
	}

	return Count;
}

Node* SequentialSearch(Node* Head, int Target) {
	Node* Current = Head;
	Node* Match = NULL;

	while (Current != NULL) {
		if (Current->Data == Target) {
			Match = Current;
			break;
		}
		else
			Current = Current->NextNode;
	}
	return Match;
}

Node* MoveToFront(Node** Head, int Target) {
	Node* Current = (*Head);
	Node* Previous = NULL;
	Node* Match = NULL;

	while (Current != NULL) {
		if (Current->Data == Target) {
			Match = Current;
			if (Previous != NULL) {
				//찾아야하는 노드 앞노드를 다음 노드로 연결
				Previous->NextNode = Current->NextNode;
				//찾은 노드를 맨앞으로 옮김
				Current->NextNode = (*Head);
				(*Head) = Current;
			}
			break;
		}

		else {
			Previous = Current;
			Current = Current->NextNode;
		}
	}
	return Match;
}

Node* Transpose(Node** Head, int Target) {
	Node* Current = (*Head);
	Node* PPrevious = NULL; //이전노드의 이전노드
	Node* Previous = NULL; //이전노드
	Node* Match = NULL;

	while (Current != NULL) {
		if (Current->Data == Target) {
			Match = Current;
			if (Previous != NULL) {
				if (PPrevious != NULL)
					PPrevious->NextNode = Current;
				else
					(*Head) = Current;

				Previous->NextNode = Current->NextNode;
				Current->NextNode = Previous;
			}
			break;
		}

		else {
			if (Previous != NULL)
				PPrevious = Previous;

			Previous = Current;
			Current = Current->NextNode;
		}
	}
	return Match;
}

Node* FrequencyCount(Node** Head, int Target) {
	Node* Current = (*Head);
	Node* Previous = NULL; //이전노드
	Node* Match = NULL;

	while (Current != NULL) {
		if (Current->Data == Target) {
			Match = Current;
			//cnt 1증가
			Match->cnt++;
			if (Previous != NULL) {
				//찾아야하는 노드 앞노드를 다음 노드로 연결
				Previous->NextNode = Current->NextNode;
			}
			break;
		}

		else {
			Previous = Current;
			Current = Current->NextNode;
		}
	}

	//현재 Match에 찾은 노드 저장되어있음
	//순서대로 앞에서부터 탐색하면서
	//찾은 노드의 cnt 보다 작은 노드 바로 앞에 다시 저장
	Node* Current = (*Head);
	Node* Previous = NULL; //이전노드

	while (Current != NULL) {
		//찾았는데도 맨 뒤에 노드보다 적게 세어진 경우
		if (Current->NextNode == NULL) {
			Current->NextNode = Match;
		}

		//들어갈 자리 찾은 경우
		if (Current->cnt > Current->NextNode->cnt) {
			if (Previous != NULL) {
				//맞는 자리가 집어넣기
				Current->NextNode = Previous->NextNode;
				Previous->NextNode = Current;
			}
			break;
		}

		else {
			Previous = Current;
			Current = Current->NextNode;
		}
	}
	
	return Match;
}

 

---

컴퓨터 프로그래밍 전공하는 대학생이 공부했던 내용을 정리하기 위해 적는 소소한 블로그입니다.
잘못된 내용은 댓글에 달아주시면 피드백 감사히 받겠습니다!

[참고한 도서]
- 데이터 구조 원리와 응용
- 이것이 자료구조 + 알고리즘이다
- 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략