2023. 12. 17. 20:53ㆍ프로그래밍 공부/Data Structure
3.3 이중 연결 리스트
앞 절에서 보았듯이 단일 연결 리스트의 맨 앞에 있는 요소를 제거하는 것은 쉬운 일이 아니다.
실제로 제거하고자 하는 노드 앞에 있는 노드에 빠르게 접근할 수 있는 방법이 없기 때문에
단일 연결 리스트에서 헤드 이외의 노드를 제거하는 것은 시간이 많이 걸린다.
실제로 이전 노드에 빠르게 접근할 수 없는 많은 응용 프로그램이 있다.
이러한 응용 프로그램의 경우 연결 리스트에서 양방향으로 이동하는 방법이 있으면 좋을 것이다.
이중 연결 리스트(doubly linked list): 전진과 후진의 양방향으로 이동할 수 있는 연결 리스트
이러한 리스트는 양 끝과 중간에 삽입과 제거를 포함한
매우 다양한 빠른 업데이트 작업을 가능하게 한다.
이중 연결 리스트의 노드는
리스트의 다음 노드를 가리키는 다음 링크와
리스트의 이전 노드를 가리키는 이전 링크의 두 가지 참조를 저장한다.
코드 조각 3.17은 이중 연결 리스트의 노드를 자바로 구현한 것으로, 요소를 문자열로 가정한다.
5장에서는 임의의 요소 타입에 대한 노드를 정의하는 방법에 대해 설명한다.
코드 조각 3.17: 문자열을 저장하는 이중 연결 리스트의 노드를 나타내는 Java 클래스 DNode.
/** Node of a doubly linked list of strings. */
public class DNode {
private String element; // String element stored by a node
private DNode next, prev; // Pointers to next and previous nodes
/** Constructor that creates a node with given fields */
public DNode(String e, DNode p, DNode n) {
element = e;
prev = p;
next = n;
}
/** Returns the element of this node. */
public String getElement() { return element; }
/** Returns the previous node of this node. */
public DNode getPrev() { return prev; }
/** Returns the next node of this node. */
public DNode getNext() { return next; }
/** Sets the element of this node. */
public void setElement(String newElem) { element = newElem; }
/** Sets the previous node of this node. */
public void setPrev(DNode newPrev) { prev = newPrev; }
/** Sets the next node of this node. */
public void setNext(DNode newNext) { next = newNext; }
}
헤더 및 트레일러 센티넬
프로그래밍을 단순화하기 위해서는
이중 연결 리스트의 양쪽 끝에 특수한 노드를 추가하는 것이 편리하다:
헤더(header) 노드: 리스트의 헤드 바로 앞에 있는 노드
트레일러(trailer) 노드: 리스트의 테일 바로 뒤에 있는 노드
이러한 "더미"나 센티넬(sentinel) 노드는 어떤 요소도 저장하지 않는다.
헤더에는 유효한 next 참조가 있지만 null prev 참조가 있다.
트레일러에는 유효한 prev 참조가 있지만 null next 참조가 있다.
이러한 센티넬이 있는 이중 연결 리스트는 그림 3.14에 나와 있다.
연결 리스트 객체는 이 두 개의 센티넬에 대한 참조와 size 카운터만 저장하면 된다.
size 카운터: 리스트에 있는 요소의 수를 추적한다. (센티넬은 카운트하지 않음)
그림 3.14: 리스트의 끝을 표시하는 센티넬인
헤더 및 트레일러가 있는 이중 연결 리스트이다.
빈 리스트은 이 센티넬들이 서로를 가리킬 것이다.
우리는 null prev 포인터를 보여주지 않는다
또한 트레일러의 null next 포인터를 표시하지 않다.
이중 연결 리스트의 양쪽 끝에 요소를 삽입하거나 제거하는 것은 바로 할 수 있다.
실제로, prev 링크는 테일 바로 앞의 노드에 도달하기 위해 리스트를 횡단할 필요가 없다.
우리는 그림 3.15의 이중 연결 리스트의 끝 부분에서 제거를 보여주고
코드 조각 3.18에서 이 작업에 대한 세부 정보를 보여준다.
그림 3.15: 헤더 및 트레일러 센티넬이 있는
이중 연결 리스트의 끝에 있는 노드 제거:
(a) 테일에서 삭제하기 전; (b) 테일에서 삭제하기 전; (c) 삭제 후.
코드 조각 3.18: 이중 연결 리스트의 마지막 노드를 제거한다.
변수 size는 리스트의 현재 요소 수를 추적한다.
이 방법은 리스트에 크기가 1인 경우에도 사용할 수 있다.
Algorithm removeLast():
if size = 0 then
Indicate an error: the list is empty.
v ← trailer.getPrev() {last node}
u ← v.getPrev() {node before the last node}
trailer.setPrev(u)
u.setNext(trailer)
v.setPrev(null)
v.setNext(null)
size = size - 1
마찬가지로 그림 3.16 및 코드 조각 3.19와 같이
이중 연결 리스트의 시작 부분에 새로운 요소를 쉽게 삽입할 수 있다.
그림 3.16: 앞에 요소 추가: (a) 하는 동안; (b) 이후.
코드 조각 3.19: 이중 연결 리스트의 처음에 새 노드 v를 삽입한다.
변수 size는 리스트의 현재 요소 수를 추적한다.
이 방법은 빈 리스트에서도 작동한다.
Algorithm addFirst(v):
w ← header.getNext() {first node}
v.setNext(w)
v.setPrev(header)
w.setPrev(v)
header.setNext(v)
size = size + 1
3.3.1 이중 연결 리스트 중간 삽입
그러나 이중 연결 리스트는
단순히 리스트의 헤드와 테일에 요소를 넣고 제거하는 것 이상으로 유용하다.
또한 요소의 리스트를 유지하면서
리스트 중간에 삽입하고 제거하는 데도 편리하다.
이 연결 리스트의 노드 v가 주어지면,
v 직후에 새 노드 z를 쉽게 삽입할 수 있다.
구체적으로, 노드 w를 v 다음에 올 수 있다고 한다.
우리는 다음 단계를 수행한다:
1. z의 prev 링크가 v를 참조하도록 한다
2. z의 next 링크가 w를 참조하도록 한다
3. w의 prev 링크가 z를 참조하도록 한다
4. v의 next 링크가 z를 참조하도록 한다
이 방법은 코드 조각 3.20에 자세히 나와 있으며, 그림 3.17에 나와 있다.
헤더와 트레일러 센티넬을 사용한 점을 상기시켜 보면,
이 알고리즘은 v가 테일 노드(트레일러 직전 노드)인 경우에도 작동한다.
코드 조각 3.20: 이중 연결 리스트에서
주어진 노드 v 뒤에 새로운 노드 z를 삽입한다.
Algorithm addAfter(v,z):
w ← v.getNext() {node after v}
z.setPrev(v) {link z to its predecessor, v}
v.setNext(w) {link z to its successor, w}
w.setPrev(z) {link w to its new predecessor, z}
v.setNext(z) {link v to its new successor, z}
size ← size + 1
그림 3.17: JFK를 저장하는 노드 뒤에 새 노드 추가:
(a) 요소 BWI로 새 노드를 생성하고 연결한다.
(b) 삽입 후
3.3.2 이중 연결 리스트의 중간 제거
마찬가지로 이중 연결 리스트의 중간에 있는 노드 v를 쉽게 제거할 수 있다.
v의 getPrev와 getNext 방법을 사용하여
v의 양쪽에 있는 노드 u와 w에 접근한다.
노드 v를 제거하려면 단순히 v 대신 u와 w가 서로를 가리킨다.
우리는 이 연산을 v로부터의 연결(linking out)이라고 한다.
또한 리스트에 오래된 참조를 유지하지 않도록
v의 prev와 next 포인터를 제거한다.
이 알고리즘은 코드 조각 3.21에 나와 있으며 그림 3.18에 나와 있다.
코드 조각 3.21: 이중 연결 리스트에서 노드 v를 제거한다.
이 방법은 v가 처음, 마지막 또는 센티넬이 아닌 노드인 경우에도 작동한다.
Algorithm remove(v):
u ← v.getPrev() {node before v}
w ← v.getNext() {node after v}
w.setPrev(u)
u.setNext(w)
v.setPrev(null) {null out of the field of v}
v.setNext(null)
size ← size - 1 {decrement the node count}
그림 3.18: PVD를 저장하는 노드 제거:
(a) 제거 전; (b) 오래된 노드 연결; (c) 제거 후(및 쓰레기 수거).
3.3.3 이중 연결 리스트의 구현
코드 조각 3.22–3.24에서는
문자열 요소를 저장하는 노드와 이중 연결 리스트의 구현을 보여준다.
코드 조각 3.22-3.24: 노드가 문자열을 저장하는 클래스 DNode의 객체인
이중 연결 리스트에 대한 Java 클래스 DL리스트(코드 조각 3.17 참조).
/** Doubly linked list with nodes of type DNode storing strings. */
public class DList {
protected int size; // number of elements
protected DNode header, trailer; // sentinels
/** Constructor that creates an empty list */
public DList() {
size = 0;
header = new DNode(null, null, null); // create header
trailer = new DNode(null, header, null); // create trailer
header.setNext(trailer); // make header and trailer point to each other
}
/** Returns the number of elements in the list. */
public int size() { return size; }
/** Returns whether the list is empty */
public boolean isEmpty() { return (size == 0); }
/** Returns the first node of the list. */
public DNode getFirst() throws IllegalStateException {
if (isEmpty()) throw new IllegalStateException("List is empty");
return header.getNext();
}
/** Returns the last node of the list. */
public DNode getLast() throws IllegalStateException {
if (isEmpty()) throw new IllegalStateException("List is empty");
return trailer.getPrev();
}
/** Returns the node before the given node v.
* An error occurs if v is the header */
public DNode getPrev(DNode v) throws IllegalArgumentException {
if (v == header) throw new IllegalStateException
("Cannot move back past the header of the list");
return v.getPrev();
}
/** Returns the node before the given node v.
* An error occurs if v is the header */
public DNode getNext(DNode v) throws IllegalArgumentException {
if (v == trailer) throw new IllegalStateException
("Cannot move forward past the trailer of the list");
return v.getNext();
}
/** Inserts the given node z before the given node v.
* An error occurs if v is the header */
public void addBefore(DNode v, DNode z) throws IllegalArgumentException {
DNode u = getPrev(v); // may throw an IllegalArgumentException
z.setPrev(u);
z.setNext(v);
v.setPrev(z);
u.setNext(z);
size++;
}
/** Inserts the given node z after the given node v.
* An error occurs if v is the header */
public void addAfter(DNode v, DNode z) {
DNode w = getPrev(v); // may throw an IllegalArgumentException
z.setPrev(v);
z.setNext(w);
w.setPrev(z);
v.setNext(z);
size++;
}
/** Inserts the given node at the head of the list. */
public void addFirst(DNode v){
addAfter(header, v);
}
/** Inserts the given node at the tail of the list. */
public void addLast(DNode v){
addBefore(trailer, v);
}
/** Removes the given node v from the list.
* An error occurs if v is the header or trailer*/
public void remove(DNode v) {
DNode u = getPrev(v); // may throw an IllegalArgumentException
DNode w = getPrev(v); // may throw an IllegalArgumentException
// unlink the node from the list
w.setPrev(u);
u.setNext(w);
v.setPrev(null);
v.setNext(null);
size--;
}
/** Returns whether a given node has a previous node. */
public boolean hasPrev(DNode v) { return v! = header; }
/** Returns whether a given node has a next node. */
public boolean hasNext(DNode v) { return v! = trailer; }
/** Returns a string representation of the list */
public String toString() {
String s = "";
DNode v = header.getNext();
while(v != trailer) {
s += v.getElement();
v = v.getNext();
if (v! = trailer)
s += ",";
}
s += "]";
return s;
}
}
위의 클래스 DList에 대해 다음과 같은 관찰을 한다.
• String 요소를 저장하는 클래스 DNode의 객체는
header 및 trailer 센티넬을 포함한 리스트의 모든 노드에 사용된다.
• 클래스 DList는 String 객체만의 이중 연결 리스트에 사용할 수 있다.
객체의 다른 타입의 연결 리스트를 만들면 일반 선언을 사용할 수 있으며,
이 선언은 5장에서 설명한다.
• 메소드 getFirst 및 getLast를 사용하면
리스트의 첫 번째 노드와 마지막 노드에 직접 액세스할 수 있다.
• 메소드 getPrev 및 getNext에서 리스트를 순회할 수 있다.
• 메소드 hasPrev 및 hasNext에서 리스트의 경계를 탐지한다.
• 메소드 addFirst 및 addLast에서 리스트의 시작 또는 끝에 새 노드를 추가한다.
• 메소드 addBefore 및 addAfter에서 기존 노드 이전 또는 이후에 새 노드를 추가한다.
• L.remove(L.getFirst()) 또는 L.remove(L.getLast())를 각각 실행하여
이중 연결 리스트 L의 시작 또는 끝에서 제거할 수 있으므로
단일 제거 메소드인 remove만 갖는 것은 실제로 제한 사항이 아니다.
• 전체 리스트를 문자열로 변환하는 메소드 toString은 테스트 및 디버깅에 유용하다.
3.4 원형 연결 리스트 및 연결 리스트 정렬
이 섹션에서는 연결 리스트의 일부 응용 프로그램 및 확장을 연구한다.
3.4.1 원형 연결 리스트와 Duck, Duck, Goose
아이들의 게임 "Duck, Duck, Goose(오리, 오리, 거위)"는 많은 문화권에서 진행된다.
(한국에서는 수건돌리기 게임이다)
원형 연결 리스트이라고 불리는 이 단일 연결 리스트의 변형은
"오리, 오리, 거위"와 같은 원 게임과 관련된 많은 응용 프로그램에 사용된다.
우리는 이런 타입의 리스트와 원 게임 응용 프로그램에 대해 다음에 논의한다.
원형 연결 리스트는 단일 연결 리스트와 같은 종류의 노드를 가지고 있다.
즉, 원형 연결 리스트의 각 노드는 다음 포인터와 원소에 대한 참조를 가지고 있다.
하지만 원형 연결 리스트에는 헤드나 테일이 없다.
원형 연결 리스트에서 마지막 노드의 다음 포인터가 null이 되도록 하는 대신 첫 번째 노드로 되돌아간다.
따라서 첫 번째 노드나 마지막 노드는 없다.
next 포인터를 따라 임의의 노드에서 원형 연결 리스트의 노드를 순회한다면,
우리는 그 노드를 순회할 것이다.
원형 연결 리스트에는 시작이나 끝이 없지만,
그럼에도 불구하고 우리는 특별한 노드로 표시될 어떤 노드가 필요한데, 이것을 커서라고 부른다.
커서(cursor) 노드: 우리가 원형 연결 리스트을 횡단해야 할 때 처음부터 시작할 장소를 가질 수 있게 해준다.
그리고 우리가 이 시작점을 기억한다면,
우리가 시작할 때 커서 노드였던 노드로 되돌아갔을 때
원형 연결 리스트의 횡단이 언제 끝났는지 알 수도 있다.
원형 연결 리스트의 업데이트 메소드
add(v): 커서 바로 뒤에 새 노드 v를 삽입한다.
리스트가 비어 있으면 v가 커서가 되고 next 포인터가 자신을 가리킨다.
remove(): 커서 바로 뒤에 노드 v를 제거하고 반환한다
(유일한 노드가 아닌 경우에는 커서 자체가 아님).
리스트가 비어 있으면 커서가 null로 설정된다.
advance(): 커서를 리스트의 다음 노드로 이동한다.
코드 조각 3.25에서는 코드 조각 3.12의 노드 클래스를 사용하고
리스트의 문자열 표현을 생성하기 위한 toString 메소드를 포함하는
원형 연결 리스트의 Java 구현을 보여준다.
코드 조각 3.25: 단순 노드가 있는 원형 연결 리스트 클래스.
/** Circulaly linked list with nodes of type Node storing strings. */
public class CircleList {
protected Node cursor; // the current cursor
protected int size; // the number of nodes in the list
/** Constructor that creates an empty list */
public CircleList() { cursor = null; size = 0; }
/** Returns the current size */
public int size() { return size; }
/** Returns the cursor */
public Node getCursor() { return cursor; }
/** Returns the cursor forward. */
public void advance() { cursor = cursor.getNext(); }
/** Adds a node after the cursor */
public void add(Node newNode){
if (cursor == null) { // list is empty
newNode.setNext(newNode);
cursor = newNode;
}
else {
newNode.setNext(cursor.getNext());
cursor.setNext(newNode);
}
size++;
}
/** Removes the node v after the cursor */
public void remove() {
Node oldNode = cursor.getNext(); // the node being removed
if (oldNode = cursor)
cursor = null; list is becoming empty
else {
cursor.setNext(oldNode.getNext()); //link out of the old node
oldNode.setNext(null)
}
size--;
return oldNode;
}
/** Returns a string representation of the list, starting from the cursor */
public String toString() {
if (cursor == null) return "[]";
String s = "[..." + cursor.getElement();
Node oldCursor = cursor;
for(advance(); oldCursor != cursor; advance()) {
s += ", " + cursor.getElement();
}
return s + "...]";
}
}
CircleList 클래스에 대한 일부 관측치
CircleList 클래스에 대해 우리가 할 수 있는 몇 가지 관찰 사항이 있다.
이 프로그램은 우리가 곧 보여줄 Duck, Duck, Goose 같은 원 게임을
시뮬레이션하기에 충분한 기능을 제공할 수 있는 간단한 프로그램이다.
하지만 이것은 강력한 프로그램은 아니다.
특히, 원형 리스트가 비어 있으면,
리스트에서 advance나 remove를 호출하면 예외가 발생한다.
Duck, Duck, Goose
어린이 게임인 Duck, Duck, Goose는 한 무리의 어린이들이 원을 그리며 앉아 있다.
그들 중 한 명이 "it"으로 선택되고 그 사람은 원의 바깥쪽을 걸어 다닌다.
"it"인 사람은 "it"인 사람이 "Goose"라고 식별하는 어린이에게
닿을 때까지 매번 "Duck"라고 말하며 각 어린이의 머리를 쓰다듬는다.
이 시점에서 "Goose"와 "it"인 사람이 원을 경주하면서 정신나간 쟁탈전이 벌어진다.
Goose의 이전 자리로 가장 먼저 돌아오는 사람은 원에 남을 수 있다.
이 경주의 패배자는 다음 라운드의 "it"인 사람이다.
이 게임은 아이들이 지루해지거나 어른이 그들에게 간식 시간이라고 말할 때까지 계속되고,
그 시점에서 게임은 끝난다. (그림 3.19 참조)
그림 3.19: Duck, Duck, Goose 게임:
(a) "Goose" 선택; (b) "Goose"와 "it" 사람 사이의 "Goose"의 장소로 가는 경주.
이 게임을 시뮬레이션하는 것은 원형 연결 리스트의 이상적인 응용이다.
아이들은 리스트에서 노드를 나타낼 수 있다.
"it" 사람은 커서 뒤에 앉은 사람으로 식별될 수 있고,
행진하는 것을 시뮬레이션하기 위해 원에서 제거될 수 있다.
우리는 "it" 사람이 식별하는 각각의 "Duck"으로 커서를 전진시킬 수 있고,
이것은 임의의 결정으로 시뮬레이션 할 수 있다.
일단 'Goose'는 식별되면, 이 노드를 리스트에서 제거하고,
무작위로 선택하여 "Goose" 또는 it" 사람이 경주에서 승리하는지 시뮬레이션한 후,
승자를 리스트에 다시 삽입할 수 있다.
그런 다음, 커서를 전진시키고 "it" 사람을 다시 삽입하여 이 과정을 반복할 수 있다
(또는 게임을 마지막으로 하는 경우 완료).
Duck, Duck, Goose를 시뮬레이션하기 위해 원형 연결 리스트 사용하기
코드 조각 3.26의 Duck, Duck, Goose의 시뮬레이션을 위해 자바 코드를 제공한다.
코드 조각 3.26: Duck, Duck, Goose 어린이 게임을 시뮬레이션하기 위해
원형 연결 리스트를 사용하는 프로그램의 주요 메소드.
/** Simulation of Duck, Duck, Goose with a circulaly linked list */
public static void main(String[] args) {
CircleList C = new CircleList();
int N = 3; // number of iteration of the game;
Node it; // the player who is "it"
Node goose; // the goose
Random rand = new Random();
rand.setSeed(System.currentTimeMillis()); //use current time as seed
// The players...
String[] names = {"Bob", "Jen", "Pam", "Tom", "Ron", "Vic", "Sue", "Joe"};
for(int i = 0; i < names.length; i++) {
C.add(new Node(names[i], null));
C.advance();
}
for(int i = 0; i < N; i++) { // play Duck, Duck, Goose N times
System.out.println("Playing Duck, Duck, Goose for " + C.toString());
it = C.remove();
System.out.println(it.getElement() + " is it.");
while (rand.nextBoolean() || rand.nextBoolean())) { //march around circle
C.advance(); //advance with probability 3/4
System.out.println(C.getCursor().getElement() + " is a duck.");
}
goose = C.remove();
System.out.println(goose.getElement() + " is the goose!");
if (rand.nextBoolean()) {
System.out.println("The goose won!");
C.add(goose); // add the goose back in its old place
C.advance(); // now the cursor is on the goose
C.add(it); // The "it" person will be it again in next round
}
else {
System.out.println("The goose lost!");
C.add(it); // addT who's "it" back at the goose's place
C.advance(); // now the cursor will be "it" in next round
}
System.out.println("Final circle is " + C.toString());
}
}
일부 샘플 출력
그림 3.20에서 Duck, Duck, Goose 프로그램의 실행에서 출력된 예시를 보여준다.
그림 3.20: Duck, Duck, Goose 프로그램의 샘플 출력.
Playing Duck, Duck, Goose for [...Joe, Bob, Jen, Pam, Tom, Ron, Vic, Sue...]
Bob is it.
Jen is a duck.
Pam is a duck.
Tom is a duck.
Ron is the goose!
The goose won!
Playing Duck, Duck, Goose for [...Ron, Bob, Vic, Sue, Joe, Jen, Pam, Tom...]
Bob is it.
Vic is the goose!
The goose won!
Playing Duck, Duck, Goose for [...Vic, Bob, Sue, Joe, Jen, Pam, Tom, Ron...]
Bob is it.
Sue is a duck.
Joe is a duck.
Jen is a duck.
Pam is a duck.
Tom is a duck.
Ron is a duck.
Vic is a duck.
Sue is the goose!
The goose won!
Playing Duck, Duck, Goose for [...Bob, Sue, Joe, Jen, Pam, Tom, Ron, Vic...]
이 프로그램의 특정한 실행에서 각각의 반복은 상이한 초기 구성과
오리와 거위를 식별하기 위한 임의의 선택의 사용으로 인해 다른 결과를 생성한다는 것을 주목하자.
마찬가지로, "Duck"가 경주에서 승리하는지 또는 "Goose"가 승리하는지 또한 임의의 선택에 따라 다르다.
이 실행은 "it" 사람이 즉시 "Goose"로 식별된 후에
다음 아이가 "Goose"로 식별되는 상황뿐만 아니라
"it" 사람이 "Goose"를 식별하기 전에
아이들의 그룹 전체를 걸어 다니는 상황을 보여준다.
이러한 상황은 또한 "Duck, Duck, Goose"와 같은 원형 게임을 시뮬레이션하기 위해
원형 연결 리스트을 사용하는 것의 유용성을 보여준다.
3.4.2 연결 리스트 정렬
저희는 코드 조각 3.27에서
이중 연결 리스트에 대한 삽입 정렬 알고리즘(섹션 3.1.2)을 보여준다.
자바 구현은 코드 조각 3.28에 나와 있다.
코드 조각 3.27: 이중 연결 리스트의 삽입 정렬에 대한 높은 수준의 의사 코드 설명.
Algorithm InsertionSort(L):
Input: An doubly linked list L of comparable elements
Output: The list L with elements rearranged in non-decreasing order
if L.size() <= 1 then
return
end ← L.getFirst()
while end is not the last node in L do
pivot ← end.getNext()
Remove pivot from L
ins ← end
while ins is not the header and ins's element is greater than pivot's do
ins ← ins.getPrev()
Add pivot just after ins in L
if ins = end then {We just added pivot after end in this case}
end ← end.getNext()
코드 조각 3.28: 클래스 DList로 표현되는
이중 연결 리스트에 삽입 정렬 알고리즘의 자바 구현
(코드 조각 3.22–3.24 참조).
/** Insertion-sort for a doubly linked list of a class DList. */
public static void sort(DList L) {
if (L.size() <= 1) return; // L is already sorted in this case
DNode pivot; // pivot node
DNode ins; // insertion point
DNode end = L.getFirst(); // end of run
while (end != L.getLast()) {
pivot = end.getNext(); // get the next pivot node
L.remove(pivot); // remove it
ins = end; // start searching from the end of the sorted run
while (L.hasPrev(ins) &&
ins.getElement().compareTo(pivot.getElement()) > 0)
ins = ins.getPrev(); // move left
L.addAfter(ins,pivot); // add the pivot back, after insertion point
if (ins == end) // we just added pivot after end in this case
end = end.getNext(); // so increment the end marker
}
}
3.5 재귀
우리는 반복문은 for문이나 while문과 같이 루프를 작성함으로써 달성될 수 있다는 것을 보았다.
반복을 달성하는 또 다른 방법은 재귀를 통해서이다.
재귀(recursion): 함수가 자신을 호출할 때 발생한다.
우리는 다른 메소드를 호출하는 메소드의 예를 보았으므로
자바를 포함한 대부분의 현대 프로그래밍 언어에서
메소드가 자신을 호출하도록 허용하는 것은 놀라운 일이 아니다.
이 절에서 우리는 이 기능이 반복 작업을 수행할 때
우아하고 강력한 대안을 제공하는 이유를 알아볼 것이다.
팩토리얼 함수
재귀를 설명하기 위해
간단한 팩토리얼 함수(factorial function)의 값을 계산하는 예로 시작하겠다.
(양의 정수 n의 팩토리얼) = n! = (1부터 n까지의 정수의 곱)
n = 0이면 n!은 관례에 따라 1로 정의된다.
좀 더 공식적으로는 임의의 정수 n ≥ 0에 대하여,
n! = 1 if n = 0
n! = n · (n-1) · (n-2) ··· 3 · 2 ·1 if n ≥ 1
예를 들어, 5! = 5·4·3·2·1 = 120이다.
메소드와의 연관성을 더 명확하게 하기 위해,
n!을 나타내기 위해, 우리는 factorial(n)을 사용한다.
계승 함수는 재귀적 공식을 제안하는 방식으로 정의될 수 있다.
이를 보려면 다음을 관찰하자
factorial(5) = 5 · (4 · 3 · 2 · 1) = 5 · factorial(4).
따라서, 우리는 factorial (5)를 factorial (4)의 용어로 정의할 수 있다.
일반적으로 양의 정수 n에 대하여,
우리는 factorial (n)을 n·factorial(n - 1)으로 정의할 수 있다.
이는 다음과 같은 재귀적 정의(recursive definition)로 이어진다.
factorial(n) = 1 if n = 0
factorial(n) = n · factorial(n - 1) if n ≥ 1
이 정의는 많은 재귀적 정의의 전형이다.
1. 하나 이상의 기본 경우를 포함한다.
기본 경우(base case): 고정된 양으로 비재귀적으로 정의된다.
이 경우 n = 0이 기본 경우이다.
2. 하나 이상의 재귀적 경우를 포함한다.
재귀적 경우(recursive case): 정의되는 함수의 정의에 호소하여 정의된다.
함수가 호출될 때마다 인수가 1만큼 작기 때문에 이 정의에는 순환성이 없다.
팩토리얼 함수의 재귀적 구현
코드 조각 3.29에 나온 팩토리얼 함수를
recursivefactorial()이라는 이름으로 자바로 구현해 보자.
여기서는 루프를 사용할 필요가 없음을 주목하라.
반복되는 재귀적 호출은 루프를 대신한다.
코드 조각 3.29: factorial 함수의 재귀적 구현.
public static int recursiveFactorial(int n) { // recursive factorial function
if (n == 0) return 1; // basis case
else return n · recursiveFactorial(n - 1); // recursive casse
}
우리는 재귀적 함수 정의의 실행을
재귀 추적(recursion trace)을 통해 설명할 수 있다.
추적의 각 항목은 재귀적 호출에 해당한다.
각각의 새로운 재귀적 함수 호출은 새로 호출된 함수에 화살표로 표시된다.
함수가 반환될 때 이 반환을 나타내는 화살표가 그려지고
이 화살표로 반환값이 표시될 수 있다.
추적의 예는 그림 3.21과 같다.
재귀를 사용하는 것의 장점은 무엇일까?
팩토리얼 함수의 재귀적 구현이 반복 버전보다 다소 간단하지만,
이 경우에는 반복보다 재귀를 선호하는 강력한 이유가 없다.
그러나 일부의 경우 재귀적인 구현은 반복적인 구현보다 훨씬 간단하고 이해하기 쉽다.
그런 예는 다음과 같다.
그림 3.21: recursiveFactorial(4) 호출에 대한 재귀 추적.
영국식 자 그리기
재귀를 사용하는 더 복잡한 예로,
전형적인 영국식 자의 표식을 그리는 방법을 생각해 보자.
자는 1인치 간격으로 나뉘는데,
각 간격은 1/2인치, 1/4인치 등의 간격으로 놓여진
눈금(tick)의 집합으로 이루어져 있다.
간격의 크기가 절반으로 줄어들면서,
눈금의 길이는 1개씩 줄어든다. (그림 3.22 참조)
그림 3.22: 자 그리기 함수의 세 가지 샘플 출력:
(a) 주요 눈금 길이가 4인 2인치 자;
(b) 주요 눈금 길이가 5인 1인치 자;
(c) 주요 눈금 길이가 3인 3인치 자.
1인치의 각 배수에는 숫자 라벨도 있다.
주요 눈금 길이(major tick length): 가장 긴 눈금 길이
그러나 우리는 실제 거리에 대해 걱정하지 않고 한 줄에 하나의 눈금만 인쇄할 것이다.
자 그리기에 대한 재귀적 접근
이러한 자를 그리는 우리의 접근 방식은 세 가지 함수로 구성된다.
1. 주 함수 drawRuler()
전체 자를 그린다.
이 함수의 인수는 자의 총 인치의 수 nInches와 주요 눈금 길이 majorLength이다.
2. 유틸리티 함수 drawOneTick()
주어진 길이의 단일 눈금을 그린다.
선택적인 정수 라벨을 부여할 수 있다.
음수가 아닌 경우 인쇄된다.
3. 재귀 함수 drawTicks()
어떤 구간 내에서 눈금의 수열을 그린다.
이 함수의 유일한 인수는 구간의 중앙 눈금와 관련된 눈금 길이이다.
그림 3.22(b)에 표시된 주요 눈금 길이가 5인 1인치 자를 생각해 보자.
0과 1을 포함하는 선을 무시하고,
이 선들 사이에 놓여 있는 눈금의 수열을 그리는 방법을 생각해 보겠다.
중앙 눈금(1/2인치)의 길이는 4이다.
이 중앙 눈금의 위와 아래에 있는 두 가지 눈금 패턴이 동일하고
각각 길이가 3인 중앙 눈금을 가지고 있음을 관찰하자.
일반적으로 중앙 눈금 길이가 L인 구간은 다음과 같이 구성된다:
• 중앙 눈금 길이가 L - 1인 구간
• 길이 L의 단 하나의 눈금
• 중앙 눈금 길이가 L - 1인 간격이다.
재귀적인 호출을 할 때마다 길이는 1씩 줄어든다.
길이가 0으로 줄어들면, 우리는 그냥 되돌아간다.
그 결과, 재귀적인 과정은 항상 종료된다.
이것은 drawTicks(L - 1)를 재귀적으로 호출하여
첫 번째와 마지막 단계를 수행하는 재귀적 과정을 나타낸다.
중간 단계는 함수 drawOneTick(L)을 호출하여 수행된다.
이 재귀적인 공식은 코드 조각 3.30에 나와 있다.
팩토리얼 예에서와 같이, 코드는 기본 경우를 갖는다 (L = 0인 경우).
이 경우에는 함수에 재귀적인 호출을 두 번 수행한다.
코드 조각 3.30: 자를 그리는 함수의 재귀적 구현.
// draw a tick with no label
public static void drawOneTick(int tickLength) { drawOneTick(tickLength, -1); }
// draw one tick
public static void drawOneTick(int tickLength, int tickLabel) {
for (int i = 0; i < tickLength; i++)
System.out.print("-");
if (tickLabel >= 0) System.out.print(" " + tickLabel);
System.out.print("\n");
}
public static void drawTicks(int tickLength) { // draw ticks of given length
if (tickLength > 0) { // stop when length drops to 0
drawTicks(tickLength-1); // recursively draw left ticks
drawOneTick(tickLength); // draw center tick
drawTicks(tickLength-1); // recursively draw right ticks
}
}
public static void drawRuler(int nInches, int majorLength) { // draw ruler
drawOneTick(majorLength, 0); // draw tick 0 and its label
for (int i = 1; i <= nInches; i++) {
drawTicks(majorLength-1); // draw ticks for this inch
drawOneTick(majorLength; // draw tick i and its label
}
}
재귀 추적을 사용한 자 그리기 예시
위에서 정의한 재귀적 drawTicks 함수의 재귀적 실행은 재귀 추적을 사용하여 시각화할 수 있다.
그러나 drawTicks의 추적은
각 인스턴스가 두 번의 재귀 호출을 하기 때문에 팩토리얼 예제보다 복잡하다.
이를 설명하기 위해 문서의 개요를 연상시키는 형태로 재귀 추적을 보여줄 것이다.
그림 3.23을 참조하자.
그림 3.23: drawTicks(3)에 대한 부분 재귀 추적.
drawTicks(2)에 대한 두 번째 호출 패턴은 표시되지 않았지만 첫 번째와 동일하다.
이 책 전체에서 우리는
재귀가 자료 구조와 알고리즘 설계에 어떻게 사용될 수 있는지에 대한
다른 많은 예를 볼 것이다.
재귀의 추가 그림
재귀(recursion): 자기 자신에게 호출하는 방법을 정의하는 개념
재귀적 호출(recursive call): 어떤 메소드가 자기 자신을 호출하는 것
또한 어떤 메소드 M이 다른 메소드를 호출하여
궁극적으로 다시 M으로 호출하는 경우에도 재귀적이라고 생각한다.
알고리즘 설계에 대한 재귀적 접근법의 장점
1. 많은 문제에 존재하는 반복 구조를 활용할 수 있다는 것이다.
재귀적 접근을 통해 복잡한 사례 분석과 중첩 루프를 피할 수 있다.
이 접근법은 효율적이면서도 알고리즘 설명을 더 쉽게 읽을 수 있도록 유도할 수 있다.
2. 또한 재귀는 아래의 예제들과 같이
반복적으로 유사한 구조 형태를 갖는 개체를 정의하는 데 유용한 방법이다.
예제 3.1: 현대 운영 체제에서는
파일 시스템 디렉터리(폴더라고도 함)를 재귀적인 방식으로 정의한다.
즉, 파일 시스템은 최상위 디렉터리로 구성되며,
이 디렉터리의 내용은 파일과 기타 디렉터리로 구성되며,
파일과 기타 디렉터리 등을 포함할 수 있다.
파일 시스템의 기본 디렉터리는 파일만 포함하지만,
이 재귀적인 정의를 사용하면 운영 체제에서 디렉터리를 임의로 깊게 중첩할 수 있다
(메모리에 충분한 공간이 있는 한).
예제 3.2: 현대 프로그래밍 언어에서
구문의 많은 부분이 재귀적인 방식으로 정의된다.
예를 들어 자바에서 인수 리스트를 다음과 같은 표기법으로 정의할 수 있다:
argument-list:
argument
argument-list, argument
즉, 인수 리스트는 (i) 인수 또는 (ii) 인수 리스트 뒤에 쉼표와 인수로 구성된다.
즉, 인수 리스트는 쉼표로 구분된 인수 리스트로 구성된다.
마찬가지로 산술 표현은 초기 형태(변수 및 상수)와 산술 표현식으로 재귀적으로 정의될 수 있다.
예 3.3: 예술과 자연에는 많은 재귀의 예들이 있다.
예술에서 사용되는 재귀의 가장 고전적인 예들 중 하나는 러시아의 마트료시카 인형이다.
각각의 인형은 단단한 나무로 만들어졌거나 속이 비어있고
그 안에 또 다른 마트료시카 인형이 들어있다.
3.5.1 선형 재귀
가장 간단한 형태의 재귀는 선형 재귀이다.
선형 재귀(linear recursion): 메소드는 호출될 때마다 최대 한 번의 재귀 호출을 수행하도록 정의된다.
이 재귀 유형은 알고리즘 문제를
처음 또는 마지막 요소와 원래 집합과 동일한 구조를 가진 나머지 집합의 관점에서 볼 때 유용하다.
배열 요소 재귀적 합산
예를 들어, 합하고자 하는 n개의 정수 배열 A가 주어졌다고 가정해 보자.
만약 n = 1이면 A의 모든 n개 정수의 합은 A[0],
또는 A의 처음 n - 1개 정수에 마지막 원소를 더한 합은 A[0]과 같음을 관찰함으로써
이 합 문제를 해결할 수 있다.
특히 코드 조각 3.31에 기술된 재귀적 알고리즘을 사용하여 이 합 문제를 해결할 수 있다.
코드 조각 3.31: 선형 재귀를 사용하여 배열의 요소를 합한다.
Algorithm LinearSum(A, n):
Input: A integer array A and an integer n ≥ 1,such that A has at least n elements
Output: The sum of the first n integers in A
if n = 1 then
return A[0]
else
return LinearSum(A, n-1) + A[n-1]
이 예는 재귀적 방법이 항상 가져야 하는 중요한 속성이
메소드가 종료됨을 보여준다.
1) n = 1인 경우에 대해 비재귀적 문을 작성함으로써 이를 보장한다.
2) 또한 주어진 (n)보다 작은 매개 변수 (n - 1)에 대해
항상 재귀적 호출을 수행하므로 (재귀의 "하단"에 있는)
어느 시점에서 (재귀적 부분) 비재귀적 부분을 수행한다.
일반적으로 선형 재귀를 사용하는 알고리즘은 일반적으로 다음과 같은 형태를 가진다:
• 기본 사례에 대한 테스트한다.
먼저 기본 사례들의 집합에 대한 테스트를 시작한다.
이러한 기본 사례들은 가능한 모든 재귀적 호출들이
결국 기본 사례에 도달하도록 정의되어야 하며,
각 기본 사례를 다루는 것은 재귀를 사용해서는 안 된다.
• 반복.
기본 사례를 검사한 후에 하나의 재귀적 호출을 수행한다.
이 재귀적 단계는 여러 재귀적 호출 중에서
어떤 호출을 수행할 것인지를 결정하는 검사를 포함할 수 있지만,
이 단계를 수행할 때마다 최종적으로 하나의 호출만 수행하도록 선택해야 한다.
또한, 우리는 가능한 각각의 재귀적 호출을 정의하여 기본 사례로 발전시켜야 한다.
재귀 추적을 이용한 재귀 알고리즘 분석
재귀 추적(recursion trace): 재귀적 알고리즘을 분석할 수 있는 시각적 도구
예를 들어, 3.5절의 재귀적 피보나치 함수를 분석하고 시각화하기 위해 재귀 추적을 사용했고,
11.1절과 11.2절의 재귀적 정렬 알고리즘도 마찬가지로 재귀 추적을 사용할 것이다.
우리는 재귀 추적을 그리기 위해
메소드의 각 인스턴스에 대한 상자를 만들고 메소드의 매개변수들로 라벨을 붙인다.
또한 우리는 호출한 메소드의 상자에서 호출된 메소드의 상자로
화살표를 그려서 재귀 호출을 시각화한다.
예를 들어, 우리는 그림 3.24에
코드 조각 3.31의 LinearSum 알고리즘의 재귀 추적을 보여준다.
우리는 이 호출에 사용된 매개변수들로 이 추적의 각 상자에 라벨을 붙인다.
우리는 재귀 호출을 할 때마다 재귀 호출을 나타내는 상자에 선을 그린다.
이 다이어그램을 사용하여 알고리즘의 단계를 시각화할 수도 있는데,
이것은 n에 대한 호출에서
n - 1에 대한 호출, n - 2에 대한 호출 등으로 진행되기 때문이다.
마지막 호출이 끝나면
값을 2에 대한 호출로 돌려주고,
이 부분합을 n - 1에 대한 호출이
부분합을 n에 대한 호출로 돌려줄 때까지 3에 대한 호출로 돌려준다.
그림 3.24: 입력 매개변수 A = {4,3,6,2,5} 및 n = 5를 사용하여
LinearSum(A,n)을 실행하기 위한 재귀 추적.
그림 3.24에서 알고리즘 LinearSum은
크기 n의 입력 배열에 대해 n번의 호출을 수행하는 데 일정한 시간이 소요되므로
대략 n에 비례하는 시간이 소요된다
각 호출에서 비재귀적인 부분이다.
또한 최종 재귀적 호출을 수행할 때
추적에 있는 n개의 상자 각각에 대해 일정한 양의 메모리 공간이 필요하므로
알고리즘이 사용하는 메모리 공간도 n에 대략 비례한다는 것을 알 수 있다(n = 1).
재귀에 의한 배열 뒤집기
다음으로 배열의 n개 원소 A를 반대로 하는 문제를 생각해 보자,
첫 번째 원소는 마지막 원소가 되고,
두 번째 원소는 마지막 원소보다 두 번째 원소가 되는 문제 등을 생각해 보자.
1. 배열의 반대가 첫 번째 원소와 마지막 원소를 교환한다.
2. 배열의 나머지 원소를 재귀적으로 반대로 돌리면 된다.
이를 관찰함으로써 선형재귀를 이용하여 이 문제를 해결할 수 있다.
우리는 코드 조각 3.32에서
이 알고리즘을 처음으로 ReverseArray(A,0,n - 1)라고 부르는 규칙을 사용하여
이 알고리즘에 대해 자세히 설명한다.
코드 조각 3.32: 선형 재귀를 사용하여 배열의 요소를 반전시킨다.
Algorithm ReverseArray(A, i, j):
Input: An array A and nonnegative integer indices i and j
Output: The reversal of the elements in A starting at index i and ending at j
if i < j then
Swap A[i] and A[j]
ReverseArray(A, i+1, j-1):
return A[0]
else
return LinearSum(A, n-1) + A[n-1]
이 알고리즘에서 실제로 두 개의 기본 경우,
즉 i = j일 때와 i > j일 때가 있다.
또한 원소가 0이거나 한 원소가 있는 수열은
그것의 반전과 사소하게 같기 때문에
두 경우 모두 단순히 알고리즘을 종료한다.
또한 재귀적 단계에서는 이 두 개의 기본 경우 중 하나로 진행하는 것이 보장된다.
n이 홀수이면 결국 i = j일 때가 되고,
n이 짝수이면 결국 i > j일 때가 된다.
위의 논의는 코드 조각 3.32의 재귀적 알고리즘이 종료되는 것이 보장됨을 즉시 의미한다.
재귀를 용이하게 하는 방법으로 문제 정의하기
주어진 문제에 대한 재귀적 알고리즘을 설계하기 위해
우리가 이 문제를 세분화하여
원래의 문제와 같은 일반적인 구조를 갖는 문제들을 정의할 수 있는
다른 방법들을 생각해 보는 것이 유용하다.
이 과정은 때때로 우리가 유사해 보이는 하위 문제들을 용이하게 하기 위해
원래의 문제를 재정의해야 한다는 것을 의미한다.
예를 들어, 우리는 ReverseArray 알고리즘을 사용하여 매개변수 i와 j를 추가하여
배열 A의 내부 부분을 역으로 하는 재귀적 호출이
A의 모든 것을 역으로 하는 호출과 같은 구조(그리고 같은 구문)를 갖도록 하였다.
그러면 일단은
처음에는 알고리즘을 ReverseArray(A)라고 부르고,
처음에는 ReverseArray(A,0,n-1)라고 부른다.
일반적으로 재귀적 알고리즘을 설계하는 데 필요한 반복 구조를 찾기 어려우면
몇 가지 구체적인 예를 들어 문제를 해결하여
하위 문제를 어떻게 정의해야 하는지 확인하는 것이 유용할 때가 있다.
꼬리 재귀
재귀를 사용하는 것은
종종 우아하고 짧은 정의를 가진 알고리즘을 설계하는 데 유용한 도구가 될 수 있다.
하지만 이런 유용성은 적은 비용으로 나타나기도 한다.
재귀적 알고리즘을 사용하여 문제를 해결할 때,
우리는 컴퓨터의 메모리 위치 중 일부를 사용하여 각 재귀적 호출의 상태를 추적해야 한다.
컴퓨터 메모리가 프리미엄급인 경우에는
재귀적 알고리즘으로부터 비재귀적 알고리즘을 유도하는 것이 유용한 경우도 있다.
5.1절에서 살펴본 스택 자료 구조를 이용하여
재귀적 알고리즘을 비재귀적 알고리즘으로 변환할 수 있지만,
이러한 변환을 좀 더 쉽고 효율적으로 수행할 수 있는 예가 있다.
특히 꼬리 재귀를 이용하는 알고리즘을 쉽게 변환할 수 있다.
꼬리 재귀(tail recursion): 재귀 함수의 한 종류로 함수를 호출한 후 더 이상의 계산이 없는 경우
만약 선형 재귀를 이용하고 알고리즘이 재귀적 호출을 하는 것을 마지막 동작으로 한다면,
알고리즘은 꼬리 재귀를 이용한다.
예를 들어 코드 조각 3.32의 알고리즘은 꼬리 재귀를 이용하여 배열의 요소를 역으로 변환한다.
그러나 메소드 정의의 마지막 문장에 재귀적 호출이 포함되어 있는 것만으로는 충분하지 않다.
메소드가 꼬리 재귀를 사용하려면 재귀적 호출이 메소드가 수행하는 마지막 작업이어야 한다.
예를 들어 코드 조각 3.31의 알고리즘은
마지막 문장에 재귀적 호출이 포함되어 있지만 꼬리 재귀를 사용하지 않다.
이 재귀적 호출은 메소드가 실제로 수행하는 마지막 작업이 아니다.
재귀적 호출에서 반환된 값을 받은 후
이 값을 A [n - 1]에 더하고 이 합계를 반환한다.
즉 이 알고리즘이 마지막으로 수행하는 작업은 재귀적 호출이 아니라 추가이다.
알고리즘이 꼬리 재귀를 사용하는 경우,
재귀적인 호출을 명시적으로 호출하는 것이 아니라
재귀적인 호출을 통해 반복함으로써 재귀적 알고리즘을 비재귀적 알고리즘으로 변환할 수 있다.
배열의 요소를 반대로 하는 문제를 다시 검토하여 이러한 변환 유형을 설명한다.
코드 조각 3.33에서는 코드 조각 3.32의 알고리즘의 재귀적 호출을 반복함으로써
이 작업을 수행하는 비재귀적 알고리즘을 제시한다.
처음에는 이 알고리즘을 IterativeReverseArray(A, 0,n - 1)이라고 부른다.
코드 조각 3.33: 반복을 사용하여 배열의 요소를 반전시킨다.
Algorithm IterativeReverseArray(A, i, j):
Input: An array A and nonnegative integer indices i and j
Output: The reversal of the elements in A starting at index i and ending at j
while i < j do
i ← i + 1
j ← j - 1
return
3.5.2 이진 재귀
이진 재귀(binary recursion): 어떤 알고리즘이 두 번의 재귀적인 호출을 하는 경우
예를 들어, 영국식의 자를 그리기 위해 3.5절에서 했던 것처럼,
이 호출들은 어떤 문제의 비슷한 절반의 두 개를 푸는 데 사용될 수 있다.
이진 재귀의 또 다른 예로 정수 배열 A의 n개 원소의 합 문제를 다시 살펴본다.
이 경우,
(i) A의 전반부에 있는 원소들을 재귀적으로 합하는 것;
(ii) A의 후반부에 있는 원소들을 재귀적으로 합하는 것;
그리고 (iii) 이 두 값을 합하는 것으로 A의 원소들을 합할 수 있다.
코드 조각 3.34의 알고리즘에 자세히 나와 있으며,
처음에는 BinarySum(A,0,n)이라고 한다.
코드 조각 3.34: 이진 재귀를 사용하여 배열의 요소를 합한다.
Algorithm BinarySum(A, i, n):
Input: An array A and integers i and n
Output: The sum of the n integers in A starting at index i
if n = 1 then
return A[i]
return BinarySum(A, i, ⌈n/2⌉) + BinarySum(A, i + ⌈n/2⌉, ⌊n/2⌋ )
알고리즘 BinarySum을 분석하기 위해
간단히 n이 2의 거듭제곱인 경우를 고려한다.
그림 3.25는 메소드 BinarySum(0,8)의 실행의 재귀 추적을 보여준다.
각 상자에는 매개변수 i와 n이 표시된다.
매개 변수 i: 반전할 요소 시퀀스의 시작 인덱스
매개 변수 n: 반전할 요소 시퀀스의 길이
추적의 화살표는 (i,n)에서 (i,n/2) 또는 (i + n/2,n/2)로 표시된 다른 상자로 이동한다.
즉, 매개 변수 n의 값은 재귀 호출 시마다 절반으로 줄어든다.
따라서 재귀 깊이는 1 + log2n이 된다.
재귀 깊이: 동시에 활성화되는 메소드 인스턴스의 최대 수
따라서 알고리즘 BinarySum은 이 값에 대략 비례하는 추가 공간을 사용한다.
이것은 코드 조각 3.31의 LinearSum 메소드에 의해 필요한 공간보다 크게 향상된 것이다.
그러나 알고리즘 "BinarySum"의 실행 시간은 여전히 n에 대략 비례하는데,
알고리즘의 실행을 거칠 때 각 상자가 일정한 시간에 방문되고 2n - 1개의 상자가 있기 때문이다.
그림 3.25: BinarySum(0,8) 실행을 위한 재귀 추적.
이진 재귀를 통한 피보나치 수 계산
k번째 피보나치 수를 계산하는 문제를 생각해 보겠다.
2.2.3절에서 피보나치 수는 다음과 같이 재귀적으로 정의된다는 것을 기억하자:
F0 = 0
F1 = 1
Fi =Fi−1 +Fi−2 for i<1.
이 정의를 직접 적용하여 코드 조각 3.35에 표시된
알고리즘 BinaryFib은 이진 재귀를 사용하여 피보나치 수열을 계산한다.
코드 조각 3.35: 이진 재귀를 이용한 k번째 피보나치 수 계산하기
Algorithm BinaryFib(k):
Input: Nonnegative integer k
Output: The kth Fibonacci number Fk
if k ≤ 1 then
return k
return BinaryFib(k - 1) + BinaryFib(k - 2)
불행하게도, 피보나치 정의가 이진 재귀처럼 보이지만,
이 기법을 사용하는 것은 비효율적이다.
실제로 이런 방식으로 k번째 피보나치 수를 계산하려면
기하급수적으로 많은 호출이 필요하다.
nk = (BinaryFib(k) 실행에서 수행된 호출 수)
라고 정의한다.
그러면, nk에 대해 다음과 같은 값이 있다:
n0 = 1
n1 = 1
n2 = n1 +n0 +1 = 1+1+1 = 3
n3 = n2 +n1 +1 = 3+1+1 = 5
n4 = n3 +n2+1 = 5+3+1 = 9
n5 = n4 +n3 +1 = 9+5+1 = 15
n6 = n5+n4 +1 = 15+9+1 = 25
n7 = n6 +n5 +1 = 25+15+1 = 41
n8 = n7 +n6 +1 = 41+25+1 = 67.
패턴을 그대로 따라가면
연속된 두 인덱스마다 호출 횟수가 두 배 이상 증가하는 것을 볼 수 있다.
n4는 n2의 2배 이상이고,
n5가 n3의 2배 이상이고,
n6은 n4의 2배 이상이다.
따라서 nk > 2^(k/2),
즉 BinaryFib(k)가 k에서 지수 함수적인 호출을 하는 수가 많다는 것을 의미한다.
즉, 피보나치 수를 계산하기 위해 이진 재귀를 사용하는 것은 매우 비효율적이다.
선형 재귀를 통한 피보나치 수 계산
위 접근법의 가장 큰 문제점은
이진 재귀를 기반으로 피보나치 수를 계산하는 것이 실제로 선형 재귀 문제라는 것이다.
이진 재귀를 사용하기에는 좋은 후보가 아니다.
단순히 k번째 피보나치 수 Fk가 이전의 두 값 Fk-1과 Fk-2에 의존하는 방식 때문에
이진 재귀를 사용하려는 유혹에 빠졌다.
하지만 선형 재귀를 사용하면 Fk를 훨씬 더 효율적으로 계산할 수 있다.
그러나 선형 재귀를 사용하기 위해서는 문제를 약간 재정의해야 한다.
이러한 변환을 수행하는 한 가지 방법은 F-1 = 0이라는 규칙을 사용하여
연속된 피보나치 수 쌍(Fk,Fk-1)을 계산하는 재귀 함수를 정의하는 것이다.
그러면 코드 조각 3.36과 같은 선형 재귀 알고리즘을 사용할 수 있다.
코드 조각 3.36: 선형 재귀를 사용하여 k번째 피보나치 수를 계산한다.
Algorithm LinearFibonacci(k):
Input: A nonnegative integer k
Output: Pair of Fibonacci numbers (Fk, Fk_1)
if k ≤ 1 then
return (k, 0)
else
(i, j) ← LinearFibonacci(k - 1)
return (i + j, i)
코드 조각 3.36에 주어진 알고리즘은
선형 재귀를 사용하여 피보나치 수를 계산하는 것이
이진 재귀를 사용하는 것보다 훨씬 효율적임을 보여준다.
LinearFibonacci에 대한 재귀 호출은 각각의 인수 k를 1씩 감소시키므로
원래 호출된 LinearFibonacci(k)는 일련의 k - 1 추가 호출을 발생시킨다.
즉, 선형 재귀를 통해 k번째 피보나치 수를 계산하려면 k개의 메소드 호출이 필요하다.
이러한 성능은
코드 조각 3.35에 주어진
이진 재귀를 기반으로 한 알고리즘이
필요로 하는 지수 시간보다 훨씬 빠르다.
따라서 이진 재귀를 사용할 때는
먼저 문제를 두 개로 완전히 분할하거나
(배열의 요소를 합할 때처럼)
중복 재귀 호출이 정말 필요한지 확인해야 한다.
일반적으로 이전 값을 추적하기 위해 메모리를 더 많이 사용하면
중복되는 재귀 호출을 제거할 수 있다.
사실 이 접근법은 다이나믹 프로그래밍이다.
다이나믹 프로그래밍(dynmic programing)은 재귀와 관련있고 12.5.2절에서 설명한다.
3.5.3 다중 재귀
다중 재귀(multiple recursion): 어떤 방법이 잠재적으로 두 개 이상의 재귀 호출을 여러 번 할 수 있을 때 사용한다.
이런 종류의 재귀의 가장 일반적인 응용 중 하나는
우리가 퍼즐 조합을 풀기 위해 다양한 구성을 열거하려고 할 때 사용된다.
예를 들어, 다음은 모두 퍼즐합(summation puzzel)의 예이다:
pot+pan=bib
dog+cat=pig
boy+girl=baby
그러한 퍼즐을 풀기 위해서,
우리는 방정식을 사실로 만들기 위해
방정식의 각 문자에 고유한 숫자(즉, 0,1,...,9)를 할당해야 한다.
일반적으로, 우리는 우리가 풀려고 하는 특정한 퍼즐에 대한 인간의 관찰을 사용하여,
실현 가능한 구성을 제거하고,
각 구성의 정확성을 테스트하면서,
구성의 정확성을 검사할 수 있을 때까지(즉, 가능한 부분적인 숫자 할당)
그러한 퍼즐을 해결한다.
그러나 가능한 구성의 수가 너무 많지 않다면,
우리는 컴퓨터를 사용하여 인간의 관찰을 사용하지 않고
모든 가능성을 열거하고 각 구성을 테스트할 수 있다.
또한 그러한 알고리즘은 여러 번의 재귀를 사용하여 구성을 체계적으로 수행할 수 있다.
우리는 코드 조각 3.37에서 그러한 알고리즘에 대한 의사 코드를 보여준다.
알고리즘은 다른 퍼즐들과 함께 사용할 수 있을 만큼
충분히 일반적인 설명을 유지하기 위해 주어진 집합 U의 원소들을 반복하지 않고
모든 k 길이의 수열을 열거하고 테스트한다.
우리는 k개 원소들의 수열을 다음 단계를 통해 구성한다:
1. k - 1개 원소의 시퀀스를 재귀적으로 생성한다
2. 각 시퀀스에 이미 포함되지 않은 요소를 추가한다.
알고리즘을 실행하는 내내 집합 U를 사용하여
현재 시퀀스에 포함되지 않은 요소를 추적하므로
e가 U에 있는 경우에만 e 요소가 아직 사용되지 않았다.
코드 조각 3.37의 알고리즘을 살펴보는 또 다른 방법은
U의 가능한 모든 크기 k의 정렬된 부분 집합을 열거하고
각 부분 집합이 퍼즐의 가능한 해결책인지 테스트하는 것이다.
퍼즐합의 경우 U = {0,1,2,3,4,5,6,7,8,9} 이며
수열의 각 위치는 주어진 문자에 해당한다.
ex) 첫 번째 위치는 b, 두 번째 위치는 o, 세 번째 위치는 y 등을 나타낸다.
코드 조각 3.37: 가능한 모든 구성을 열거하고 테스트하여 퍼즐 조합을 푸는 것.
Algorithm PuzzleSolve(k,S,U):
Input: An integer k, sequence S, and set U
Output: An enumeration of all k-length extensions to S using elements in U without repetitions
for each e in U do
Remove e from U {e is now being used}
Add e to end of S
if k = 1 then
Test whether S is a configuration than solves the puzzle
if S solves the puzzle then
return "Solution found: " S
else
PuzzleSolve(k - 1,S,U)
Add e back to u {e is now unused}
Remove e from the end of S
그림 3.26에서는 S는 비어있고 U = {a, b, c}일 때
PuzzleSolve(3,S,U)로 호출한 재귀적인 추적을 보여준다.
실행하는 동안 세 문자의 모든 순열이 생성되고 테스트된다.
초기 호출은 세 번의 재귀적 호출을 수행하고,
각 호출은 두 번의 재귀적 호출을 수행한다.
만약 네 개의 원소로 구성된 집합 U에서 PuzzleSolve(3,S,U)를 실행했다면,
초기 호출은 네 번의 재귀적 호출을 수행했을 것이고,
각 호출은 그림 3.26과 같은 추적을 가질 것이다.
그림 3.26: PuzzleSolve (3,S,U)의 실행을 위한 재귀 추적.
여기서 S는 비어 있고 U = {a,b,c}.
이 실행은 a,b,c의 모든 순열을 생성하고 테스트한다.
각 상자 바로 아래에 생성된 순열을 보여준다.
'프로그래밍 공부 > Data Structure' 카테고리의 다른 글
| 5장 스택과 큐 (1) | 2023.12.20 |
|---|---|
| 4장 분석 도구 (1) | 2023.12.19 |
| 3장 배열, 연결 리스트, 재귀(1) (0) | 2023.12.16 |
| 2장 객체 지향 디자인 (0) | 2023.12.15 |
| 1장 자바 프로그래밍 기초(2) (0) | 2023.12.13 |