JAVA 자료구조 (재귀와 귀납적 사고) - 재귀 구조 예

 

2.재귀 구조의 예

3. 선택정렬

배열 A[0..n-1]에 n개의 원소가 주어지고 이를 크기순으로 정렬하려고 한다. 여러 정렬 알고리즘 중 가장 기초적인 알고리즘인 선택 정렬의 예를 살펴보자.

 

[알고리즘 2-5]의 선택정렬 알고리즘에서 먼저 전체를 한 번 훑어 가장 큰 원소를 찾는다.(2️⃣) 이 원소를 제일 오른쪽 원소와 맞바꾼다.(3️⃣) 그러면 맨 오른쪽 제일 큰 원소가 자리하게 되고 이 원소는 더 이상 자리를 바꿀 필요가 없다. 즉, 제일 큰 원소에 관한 한 정렬이 끝난 것이다. 이제 맨 오른쪽 원소를 관심 대상에서 제외한다. 그러면 A[0...n-2]에 n-2개 짜리 정렬 문제가 남는다. 즉, 가장 큰 뭔소를 찾아 맨 오른ㅉ고 원소와 맞바꾸는 수고를 하고나면 자신과 성격이 똑같지만 크기가 하나만큼 작은 정렬 문제를 만나게 된다. 재귀적 구조다.

 

알고리즘에서 1️⃣의 for 루프가 한 바퀴 돌 때마다 문제의 크기가 하나씩 작아 진다. n개짜리 문제로 시작해서 총n-1 바퀴를 돌고 나면 1개짜리 문제가 남는다. 즉,A[0]만 남는다.1개짜리 무제는 원소가 하나뿐이라 정렬할 것이 없다. [알고리즘 2-5](선택정렬)는 재귀알고리즘은 아니지만 앞에서 설명했듯이 논리 구조상 재귀성이 포함되어 있다

 

 

. 이를 명시적으로 재귀를 포함하는 알고리즘으로 바꾼 것이 [알고리즘 2-6]이다. [알고리즘 2-6]의 재귀 버전 선택 정렬 알고리즘에서는 2️⃣,3️⃣에서 가장 큰 원소를 찾아 맨 오른쪽 원소와 맞바꾸는 작업을 한다. 그리고 4️⃣에서 자기 보다 작은 선택정렬 문제를 호출한다. 크기가 n인 선택 정렬 문제가 크기가 n-1인 선택 정렬 문제를 호출한다. 즉, 배열 A[0...n-1]을 대상으로 한 정렬 문제가 배열A[0... n-2]를 대상으로 하는 정렬 문제를 호출한다. 이렇게 자기호출을 반복하다가 언젠가는 끝내야 한다. 1️⃣은 경계조건이다. 1️⃣은 문제의 크기가 1보자 클 때만 자기호출을 하라는 뜻이다. 즉, 문제의 크기가 1이되면 자기호출의 반복을 멈춘다.

 

💡tip) 어떤 것이 더 편한가?

[알고리즘 2-5]를 더 편하게 받아들이는 사람도 있고, [알고리즘 2-6]을 더 편하게 받아들이는 사람도 있을 것이다. 대체적으로 [알고리즘 2-5]와 같은 스타일을 더 편하게 여긴다. 시간이 지나면서 [알고리즘2-6]과 같은 스타일을 더 편하게 여기는 것이 바람직한데, 이는 귀납적 사고가 틀이 잡혀가고 있다는 의미이다.

 

 

4. 중위, 전위, 후위 표현법

우리에게 익숙한 A+B와 같이 연산자(+)가 피연산자(A와 B)사이에 놓이는 수식 모양을 중위 표현법(Infix Expression)이라고 한다. 우리는 우연히 이런 형태의 수식에 친숙해졌을 뿐이며, 다르게 표현할 수도 있다. +A B 처럼 연산자를 앞에 둔 모양을 전위 표현법(Prefix Expression)이라 하고, A B+처럼 연산자를 뒤에 둔 모양응 후위 표현법 Postfix Expression이라 한다. 즉, 연산자의 위치가 다르다.

 

좀 더 긴 식을 살펴보자. A+B*C-2는 *,/ 연산자가 +,- 연산자보다 우선순위가 높아 A+(B*C)-2의 의미를 갖고 있다. 괄호가 없어도 우선순위에 의해 해석된다. 반면 (A + B)*(C - 2)는 괄호가 없으면 표현이 불가능하다. 우리에게 익숙한 중위 표현법은 이런 번거로움을 안고 있다.  반면 전위 표현법이나 후위 표현법에서는 우선순위를 설정할 필요가 없어서 괄호도 필요 없다.

 

그림 2-4 재귀가 포함된 중위, 전위, 후위 표현법의 형식언어

 

중위, 전위, 후위 표현법을 컴퓨터 과학의 형식 언어에서 사용하는 문법으로 표현하면 [그림 2-4]와 같다. 예를 들어 후위 표현법에서 <postfix>는<변수>하나일 수도 있고, <연산자> 앞에 후위 표현 2개가 앞서 있을 수도 있다는 뜻이다. <postfix>안에 <postfix>가 2개 포함되어 있다. 즉, <postfix> 안에 성격은 똑같지만 자신보다 크기가 작은 표현이 2개 포함되어 있으므로 재귀적이다. ([그림 2-4]에서 |는 or (또는)를 의미한다. 예를 들면, "<연산자 > = + | - | * | /"는 "<연산자>"는 + 또는 -또는 * 또는 /"라는 뜻이다.) 그리고 "<변수> = A | B | ... Z"는 "<변수>는 영문 대문자 중 하나" 라는 뜻이다.

 

5.깊은 우선 탐색(Depth-First Seach, DFS)

 

그림 2-5 깊이 우선 탐색의 예

 

[그림 2-5]는 모든 노드를 방문하는 방법을 찾는 그래프 알고리즘에서 유명한 기초 문제다. 왼쪽 그림의 0번 도느에서 방문할 수 있는 모든 노드와 해당 노드에 이르는 경로를 별색으로 표시한 것이 오른쪽 그림이다.(각 노드에 이르는 유일한 경로는 아니다.)

 

모든 노드를 방문하는 다양한 방법 중 깊이 우선 탐색(Depth-First Search)을 소개한다. 워낙 유명해서 DFS라는 약칭으로 불린다. DFS도 재귀를 상징하는 대표적인 예다.

 

https://dodote10.tistory.com/551

자료구조(그래프 탐색) - 깊이 우선 탐색(Depth-First Seach, DFS)

 

[알고리즘 2-7]의 DFS 알고리즘에서 DFS()가 DFS()를 호출하고 있다. 재귀 알고리즘이다. 이 알고리즘이 갖고 있는 재귀적 구조를 살펴보자. 먼저 노드 x가 방문되었다고 표시한다.(1️⃣) 그런 다음 x에서 화살표로 연결된 노드 중 아직 방문이 아된 노드가 있으면 그들 중 하나를 입의로 택하여 DFS()를 수행한다.(2️⃣) 2️⃣의 if 문에 의해 이미 방문된 노드는 절대로 다시 DFS()를 수행하지 않는다. 즉, 방문된 노드는 DFS()의 대상에서 제외된다.

 

[그림 2-5]에서 0번 노드로부터 DFS(0)를 시작하면 0번 노드가 방문되었다고 표시한 다음 0번에 연결된 노드 중(2번과 3번) 아직 방문되지 않은 것(2,3번이 다 해당됨)중에서 하나를 골라(2번을 골랐다고 하자) DFS(2)를 호출한다.이는 모든 노드를 포함하는 DFS 문제가 0번 노드를 제외한 DFS 문제를 호출한것이다. 즉, 크기(노드 수)가 8인 DFS문제가 자기자신보다 크기가 하나 작은 DFS 문제를 호출한 것이다. 달리 표현하면, 시작 노드가 방문되었다고 표시하는 수고를 하고 나면 자신과 성격은 똑같지만 크기가 하나 작은 문제를 만나게된다.

 

0번 노드를 시작으로 DFS(0)가 수행되는 과정

그림 2-6 DFS()의 수행

(a)  주어진 그래프다.

 

(b)  0번 노드를 시작으로 DFS(0)이 호출되고, DFS(0)은 DFS(2)를 호출한다. DFS(2)는 DFS(4)를 호출하고, DFS(4)는 DFS(1)을 호출한다. 이 시점까지 완료되지 않은 즉 끝나지 않고 살아 있는 함수의 호출 체인은  DFS(0) → DFS(2) → DFS(4) → DFS(1) 이다.  DFS(1)로 들어가니  1번 노드에서는 연결된 노드가 없다. 즉 2️⃣의 DFS(y)를 수행할 수 있는 노드가 없다. DFS(1)가 종료된다

 

(c)  DFS(1)을 호출한 4번 노드로 돌아간다.(DFS(4)가 DFS(1)을 호출했었다.) 4번 노드중에서 연결된 노드중 방문되지 않은 노드(7번 노드)가 있다. DFS(7)을 호출한다. 7번 노드로 가보니 더 이상 연결된 노드가 없다. DFS(7)이 종료된다.

 

(d)  7번에서 막혀, 왔던 길로 후퇴한다. 4번으로 돌아가니 4번에서 연결된 노드 중 더이상 방문되지 않은 노드가 없다. DFS(4)가 종료되고 이를 호출한 2번 노드로 돌아간다. 2번에서 연결된 노드 중에 아직 방문 되지 않은 노드는 없다.  DFS(2)가 종료되고 이를 호출한 0번 노드로 간다.

 

(e)  0번 노드에 와보니 연결된 노드중 아직 방문 되지 않은 노드(3번)가 있다. DFS(3)을 호출한다. DFS(3)은 DFS(5)를 호출한다. 5번 노드에와 보니 연결된 노드가 있긴 한데(2번)이미 방문된 것이다. 그러니 2️⃣의 DFS(y)를 수행할 수 있는 노드 y가 없다 DFS(5)가 종료된다.

 

(f)  후퇴한다. 3번 노드에서 더 갈 곳이 없다. DFS(3)이 끝나면 0번 노드로 돌아간다. 0번 노드에서 더이상 갈 곳이 없으므로 DFS(0)가 끝나면서 알고리즘이 종료된다.

 

DFS는 개성이 강하고 중요한 알고리즘으로, 이와 같은 방식으로 탐색하는 것을 총칭하여 백크래킹(Backtracking)이라 부르기도 한다. 

  

 

 

[출처 - 쉽게 배우는 자료구조 with 자바,  저 문병로]
https://www.hanbit.co.kr/store/books/look.php?p_code=B7033044159

IT CookBook, 쉽게 배우는 자료구조 with 자바