코딩은제정신에해로워

1일 1포스트를 계획했으나... 이래저래 명절 등으로 늦어버렸다 ^^ 각설하고 

오늘은 linked list에 대해서 복습하였다. 

먼저 array로 구현해보았다.

typedef int LData;

typedef struct __Arraylist {
	LData arr[100];
	int numOfData;
	int curPosition;
}Arraylist;

리스트는 데이터를 담을 arr, numOfData(데이터 수), curPostion(현재 가리키고 있는 위치)를 인스턴스로 가지는 구조체이다. LData는 여러 자료형을 사용하기 위해서 선언해주었다, 위 예시에서는 int를 사용한다.

void ListInit(List *plist); //리스트 초기화
void LInsert(List *plist, LData data); //데이터 삽입

int LFirst(List *plist, LData *pdata); //첫 번째 데이터 가리키기
int LNext(List *plist, LData * pdata); //다음 데이터 가리키기

LData LRemove(List *plist); //cursor가 가리키는 데이터 삭제
int LCount(List *plist); //현재 데이터 수

다음과 같은 함수들을 선언하고, 만들어주었다. 자료구조를 처음 배울 때는 잘 몰랐는데, 객체지향프로그래밍을 조금 접하고 나니 왜 Class가 편한지 새삼 느껴진다... ㅎㅎ

실제로 여기서 주목해야할 함수는 LFirst, LNext, LRemove의 세 가지이다. 

먼저 LFirst를 살펴보자

int LFirst(List *plist, LData *pdata) {//pdata에 조회값 저장됨
	if (plist->numOfData == 0)
		return false;
	else {
		plist->curPosition = 0;
		*pdata = plist->arr[0];
		return true;
	}
}

함수의 반환형 int는 데이터가 있는지 없는지만을 확인하기 위해 쓰인다.

중요한 것은 pdata로 인자를 포인터로 받는다. 

그리고서는 조회된 데이터를 pdata에 저장시킨다. 포인터를 이용해서 받았기 때문에, 굳이 pdata를 return 하는 식으로 만들 필요가 없다. (개인적으로는 이 부분에서 조금 놀랐다. 함수 자체는 데이터의 유무만, 실 데이터는 포인터로 처리할 생각을 크게 해본 적이 없는데, 이렇게 만들면 참 편하고 괜찮아 보인다.)

다음은 LNext이다.

int LNext(List *plist, LData * pdata) {//pdata에 조회값 저장됨
	if (plist->curPosition >= (plist->numOfData) - 1) //curPosition이 계속 증가할텐데, data 수보다 커지면 조회할게 없음
		return false;
	(plist->curPosition)++;
	*pdata = plist->arr[plist->curPosition];
	return true;
}

기본적으로는 LFirst와 동일한데, 얘는 데이터를 조회할 때마다 curPosition을 증가시켜서 다음 부분을 가리킨다. 즉 이전에 조회한 값의 다음 값을 조회할 수 있다. 이런 식의 코드가 왜 필요한지는 값을 조회할 때 빛을 발한다.

	if (LFirst(&list, &data)) {
		if (data == 22)
			LRemove(&list);
		while (LNext(&list, &data)) {
			if (data == 22)
				LRemove(&list);
		}
	}

만약 값이 22인 데이터를 조회해 삭제한다고 한다면 다음과 같이 처음 값을 조회했다가, 그 다음 그 다음 값을 순차적으로 조사한다. 나였다면 단순히 arr[n]에서 n++ 과 같은 식으로 찾았을텐데, 별거 아니지만 참 많이 배운 부분이다. 

array로 구현하였지만 linked list라고 부를 수 있는 이유를 다음과 같은 코드에서 알아볼 수 있는 것 같다.

다시 LRemove로 돌아오자.

LData LRemove(List *plist) {
	int rpos = plist->curPosition;//현재 삭제할 위치
	int num = plist->numOfData;
	int i;
	LData rdata = plist->arr[rpos];

	for (i = rpos; i < num - 1; i++)
		plist->arr[i] = plist->arr[i+1];
	(plist->numOfData)--;
	(plist->curPosition)--;
	return rdata;
}

굉장히 간단한 코드이다. 

위 코드는 실제로 이런 결과를 만든다. n+1 위치의 arr 값들이 모두 n의 위치로 덮어쓰기(저장)되고

curPosition을 하나 앞당긴다. 

이제 얼른 node로 구현된 linked list를 만들어봐야겠다.

하노이의 타워는 재귀함수의 효율을 잘 보여주는 예시 중 하나이다. 

하노이의 타워는 다음과 같은 규칙을 지켜야한다.

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

크기 순으로 1, 2, 3 이라고 원판을 불러보자. 

원판 3이 마지막 막대에 들어가기 위해서는 원판 1,2 가 탑을 이루는 과정이 필요하다.

만약 원판이 하나 더 있다고 가정해보자. 위 파란 글씨의 방식을 생각해본다면

원판 4는 원판 1,2,3이 탑을 이루고 있다면 마지막 막대로 이동할 수 있다.

그 이후는 다음과 같은 과정을 이룰 것이다.

1. 원판 4는 막대 C (막대를 순서대로 A, B, C라고 명명)에 올라간다.

2. 원판 1,2,3은 막대 B에 위치한 상태

3. 원판 4는 제일 크기 때문에 처음부터 없는 상태라고 가정 가능

4. 원판 1,2,3만 존재하는 하노이의 타워의 방법을 취할 수 있음

즉 원판의 갯수가 몇개라고 할 지라도 이러한 연속적인 과정을 통해서 이동 시킬 수 있다.

이러한 연속적인 과정은 재귀함수에서 굉장히 유리하다. 

#include <iostream>
using namespace std;

void HanoiTowerMove(int num, char a, char b, char c) {
	//num개의 원반을 b를 거쳐 a에서 c로 이동한다.
	if (num == 1)
		printf("원판1을 %c에서 %c로 이동\n", a, c);
	else {
		HanoiTowerMove(num - 1, a, c, b);	//부분1
		printf("원판%d를 %c에서 %c로 이동\n", num, a, c); //부분2
		HanoiTowerMove(num - 1, b, a, c);	//부분3
	}
}
int main() {
	int input;
	cout << "원판의 갯수 입력:";
	cin >> input;
	HanoiTowerMove(input, 'A', 'B', 'C');
	system("pause");
	return 0;
}

HanoiTowerMove 함수는 세 부분으로 나눌 수 있다.

1. 맨 아래의 원판을 제외하고 A에서 B로 이동시키기

2. 맨 아래의 원판을 A에서 C로 이동시키기

3. B로 이동한 원판들을 모두 C로 이동시키기

이런 과정을 통해서 재귀적으로 모든 원판을 이동시킬 수 있다.

마지막으로 백준에서 하노이의 탑 문제를 소개하고 마친다.

https://www.acmicpc.net/problem/1914

ps... 만들고 보니 하노이의 탑보다는 biginteger문제가 더 문제인 문제였다..