연습문제

※ 스스로 풀어 보세요. 해법은 따로 제공하지 않습니다.

1. 널리 사용되는 프로그래밍 언어로 잘 구현된 리스트들이 있지만, 직접 구현하는 것이 더 유익하고 어렵지 않으니 구현해 보라. 기본 아이디어는 그림 2-13과 2-15에 있다. 빈 리스트는 NULL을 가리키는 포인터다. 리스트의 헤드에 아이템을 삽입할 때 새로운 헤드를 가리키게 리스트를 갱신하고 삽입된 새 헤드는 삽입 전에 가리키던 노드인 이전 헤드나 NULL을 가리키게 한다. 기존에 있던 아이템 다음에 아이템을 삽입하려면 이전 아이템의 링크가 새로 삽입된 아이템을 가리키게 하고, 새로 삽입된 아이템은 삽입 전에 이전 아이템이 가리키던 것을 가리키게 한다. 리스트에 있는 아이템을 검색하려면 헤드에서 시작하여 각 아이템을 검사하여 찾고자 했던 것을 찾거나 NULL을 만날 때까지 링크를 따라간다. 아이템을 제거하려면 먼저 제거할 아이템을 찾고, 아이템을 찾으면 제거할 아이템을 가리키던 포인터가 다음 아이템을 가리키게 하거나 마지막 아이템을 제거한다면 NULL을 가리키게 한다.

2. 큐는 배열로 구현할 수 있는데, 배열로 구현한 큐에서는 큐의 헤드 h와 테일 t의 인덱스를 관리한다. 초기에는 헤드와 테일의 인덱스 모두 0이다.

큐에 아이템을 삽입하면 테일의 인덱스가 증가하고 큐에서 아이템을 제거하면 헤드의 인덱스가 증가한다. 5, 6, 2, 9를 삽입했다가 5를 제거하면 배열은 다음과 같아진다.

배열에 n개의 아이템이 있다면 헤드 또는 테일이 (n - 1) 번째 아이템에 도달했을 때 위치 0으로 되돌아간다. 그래서 몇 번의 삽입과 삭제 이후에 큐는 다음과 같은 모습이 된다.

이러한 아이디어로 만들어진 큐를 구현해 보라. 헤드가 테일에 도달하면 큐는 빈 상태가 되고, 테일이 헤드를 만나 덮으면 큐가 가득 찬다.

3. 인접 리스트 대신에 인접 행렬 표현으로 깊이 우선 탐색(재귀 용법은 자유로이 선택 사용)과 너비 우선 탐색 알고리즘을 구현해 보라.

4. 깊이 우선 탐색은 단지 미로를 탐색하기 위해서가 아니라 미로를 생성하는 데 사용할 수 있다. 격자로 배열된 n × n 노드의 그래프로 시작한다. 예를 들어, n = 10이고 (x, y)의 위치로 노드를 명명한 다음 그림과 같은 그래프가 있다고 하자.

그래프의 임의의 노드에서 출발하여 방문했던 노드를 표시하고 무작위로 이웃을 방문한다. 아직 방문하지 않은 노드라면 미방문 노드 각각을 탐색할 링크를 기록하고 해당 노드로 가서 재귀적으로 탐색을 계속한다. 즉, 무작위로 이웃을 방문하는 깊이 우선 탐색을 수행하되 뒤따를 링크를 계속 기록한다. 깊이 우선 탐색을 마치면 새로운 그래프를 얻게 되는데, 이것은 같은 n × n 노드들과 탐색한 원래 링크들의 부분 집합으로 구성된다. 이것은 미로다. 이러한 미로를 생성하는 프로그램을 작성해 보라.

5. 그림 2-10에서 보는 바와 같이 단순히 눈으로 봐서 그래프가 이분 그래프인지를 판단하기가 쉽지 않다. 대신에 다음 과정을 수행할 수 있다. 그래프를 탐색하며 두 개의 다른 색상으로 노드를 색칠한다. 노드에 색을 입힐 때 실제로 색칠하지는 않는다. 다만, 그 색을 갖는다는 것을 표시할 뿐이다. 빨강과 초록을 사용한다면 첫 번째 노드를 빨강, 다음 노드를 초록, 이런 식으로 색을 입힌다. 탐색 과정에서 현재 노드에 사용된 색과 같은 색의 이웃을 만나면 그래프는 이분 그래프가 아니다. 이러한 발견 없이 탐색이 끝나면 이 그래프는 이분 그래프다. 이렇게 이분 그래프를 탐지하는 알고리즘을 구현해 보라.