<뇌를 자극하는 알고리즘 #7>: 순차 탐색(Sequential Search) 퀴즈풀이

퀴즈에 등장하는 개념 요약 // 해당 도서를 읽지 않으시는 분들도 생각하고 풀어보실 수 있습니다.

---

# 전진 이동법

 전진 이동법(Move to front method)은 어느 항목이 한 번 탐색되고 나면, 그 항목을 데이터 집합의 가장 앞(링크드 리스트에서는 헤드)에 위치시키는 방법이다. 이렇게 하면 한 번 찾은 항목을 연이어 또 찾는 경우 단번에 탐색을 완료할 수 있다. MS 워드의 '최근 문서'기능과 같은 원리로 동작한다고 생각하면 이해가 쉽다. 전진이동법의 한계는 한 번 탐색된 항목이 곧 이어 또다시 검색될 가능성이 높은 데이터 집합에서만 사용해야한다 점이다.

# 전위법

 전위법(Transpose method)은 탐색된 항목을 바로 이전 항목과 교환한다는 것 말고는 기본적으로 전진 이동법과 같은 전략을 취하는 알고리즘이다. 전진 이동법은 탐색된 항목을 무조건 앞으로 옮기는데 반해, 전위법은 '자주' 탐색된 항목들이 데이터 집합의 앞쪽으로 모이게 된다. 전위법은 발견이 될 때마다 해당 데이터를 한 칸씩 데이터 집합의 앞으로 옮기기 때문이다.

Vitamin Quiz // 문제가 2개로 이루어져 있습니다.

---

 문제 1) 기존의 단일연결리스트에 적용할 수 있던 전진 이동 순차탐색 알고리즘을 int형 배열에 사용 가능한 전진 이동 순차 탐색 코드로 재구성하라. // 기존의 코드는 바로 밑에 있는 코드다.

/*************************************************
 ** 전진 이동 순차 탐색 코드 (SLL ver)
*************************************************/

typedef struct Node{
	int data;
	struct Node *NextNode;
} Node;

Node* SLL_MoveToFront(Node **head, int target) // 단일연결리스트(SLL)용 전진이동 순차탐색 알고리즘
{
	Node *current = *head;
	Node *previous = NULL;
	Node *match = NULL;

	while (current != NULL)
	{
		if (current->data = target)
		{
			match = current; // 찾고자 하는 노드의 주소를 저장
			if (previous != NULL) // 전 노드가 NULL이 아니라면
			{	// current는 
				previous->NextNode = current->NextNode;
				
				current->NextNode = *head;
			}
			break;
		}
		else // 찾고자 하는 값이 없을 때
		{
			previous = current;
			current = current->NextNode;
		}
		return match;
	}
}

/*************************************************
 ** End Line
*************************************************/

 문제2) SLL_Tranpose( ) 함수의 배열 버전을 구현하라. 아래 단일연결리스트를 기반으로 작성되어 있는 코드를 배열 버전으로 수정하라.

/*************************************************
 ** 기존의 단일연결리스트(SLL) 버전의 전위법 알고리즘
*************************************************/

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

typedef struct Node {
	int data;
	struct Node *NextNode;
} Node;

Node* SLL_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) // 2단계 전 노드가 NULL이 아닐 경우
					pPrevious->NextNode = current; // 2단계 전 노드가 현재 노드를 가리키게 설정
				else
					*head = current;

				// 이제 current는 한 칸 앞으로 전진해야하므로 더이상 previous의 다음 노드가 아니다.
				// 직전 노드가 current가 아닌 다음 노드를 가리키게 수정
				previous->NextNode = current->NextNode;

				// current가 한 칸 앞으로 왔으므로, 이전노드가 current의 다음 노드가 된다.
				current->NextNode = previous;
			}
			// 원하는 작업을 마쳤으니 루프를 빠져나간다.
			break;
		}
	}
}

/*************************************************
 ** End Line
*************************************************/

풀이1 // 풀이1과 풀이2는 구현이 너무 간단하여 별도의 소스코드 첨부는 하지 않겠습니다.

---

 원하는 요소를 발견하면, 일단 그 요소를 따로 저장해둔다. 0번째부터 지금 인덱스까지 한 칸 뒤로 요소들을 옮긴다. 그렇게 0번째 위치에 빈자리가 생기면, 저장해둔 정보를 옮겨주기만 하면 된다.

/*************************************************
 ** int형 배열을 매개변수로한 전진 이동 순차 탐색 알고리즘
*************************************************/

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

void ARY_MoveToFront(int dataSet[], int target, int size)
{
	int i;
	int value = 0;
	for (i = 0; i < size; i++)
	{
		if (dataSet[i] == target)
		{
			value = dataSet[i];
			memmove(&dataSet[1], // 첫 번째 매개변수는 이사할 새로운 주소 
				&dataSet[0], // 두 번째 매개변수는 이사할 데이터가 어디서 부터인지를 나타내는 주소
				sizeof(dataSet[0]) * i); // 세 번째 매개변수는 얼마만큼 옮길건지를 표현하는 byte
			dataSet[0] = value;
		}
	}
}

int main()
{
	int i;
	int dataSet[] = { 71,5,13,1,2,48,222,136,3,15 };
	int size = sizeof dataSet / sizeof dataSet[0];

	ARY_MoveToFront(dataSet, 48, size);
	
	/* 정렬된 배열 출력 */
	for (i = 0; i < size; i++)
	{
		printf("%d ", dataSet[i]);
	}

	printf("\n");
}

/*************************************************
 ** End Line
*************************************************/

풀이2

---

 원하는 값을 찾았다면 해당 값을 바로 직전 원소와 자리바꿈만 해주면 된다. 구현이 매우 간단하다.

/*************************************************
 ** 배열 버전 전위법(Transpose) 알고리즘
*************************************************/

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

void ARY_Transpose(int dataSet[], int target, int size)
{
	int i;
	int temp; // 원소간의 값 교환시 사용될 변수
	for (i = 0; i < size; i++)
	{
		// 만약 i가 0이라면 따로 교환해줄 필요가 없으므로 i > 0 조건 추가
		if (i > 0 && dataSet[i] == target)
		{
			temp = dataSet[i - 1];
			dataSet[i - 1] = dataSet[i];
			dataSet[i] = temp;

			break; // 목적을 달정했으니 빠져나온다.
		}
	}
}

int main()
{
	int i;
	int dataSet[] = { 71,5,13,1,2,48,222,136,3,15 };
	int size = sizeof dataSet / sizeof dataSet[0];

	for (i = 0; i < 5; i++)
	{	// 48을 5번 찾았다고 가정, 48은 맨 앞으로 이동될 것이다.
		ARY_Transpose(dataSet, 48, size);
	}

	/* 정렬된 배열 출력 */
	for (i = 0; i < size; i++)
	{
		printf("%d ", dataSet[i]);
	}

	printf("\n");
}

/*************************************************
 ** End Line
*************************************************/