* 공부용의 자유로운 글씨😀
『가장 쉬운 독학 알고리즘 첫걸음 - C&자바편』 공부용이다.
재귀 호출 : 함수 안에서 자기 자신을 호출해서 반복 처리를 실현하는 것!
(반복 호출이라 짜기는 편하지만 계승 문제를 풀 때는 효율성 검사 통과 못 함!)
그리고 퀵 정렬은 재귀 호출을 사용해서 프로그램을 작성하는 대량 데이터 정렬이라 같이 챕터에 포함되었나 보다.
팩토리얼을 보통 재귀호출 예제로 사용하기 때문에 교재에서도 그걸 사용했다.
이러면 5*4*3*2*1이 된다!
이걸 자바로 구현하면 아래와 같다.
public class 팩토리얼 {
public static int factorial(int n){
if(n==0){
System.out.println(n+"값이라 1을 반환");
return 1; //0의 계승이 1이라 1을 반환하고, 여기서 재귀가 끝남
}else{
System.out.println(n+"값!");
return n * factorial(n-1);
}
}
public static void main(String[] args) {
int ans;
ans = factorial(5);
System.out.println(ans);
}
}
5값!
4값!
3값!
2값!
1값!
0값이라 1을 반환
120
이렇게 동작한다.
처음에 factorial(5) 호출되고, f(4) f(3) f(2) f(1) f(0) 을 호출시킨다.
그래서 1 -> 1 -> 2 -> 6 -> 24 -> 120이 반환된다.
추적 코드를 추가해 보면 아래와 같다.
public class 팩토리얼 {
public static int factorial(int n){
System.out.println("factorial" + n + " 호출");
if(n==0){
System.out.println(n+"값이라 1을 반환");
return 1; //0의 계승이 1이라 1을 반환하고, 여기서 재귀가 끝남
}else{
int returnVal = n * factorial(n-1);
System.out.println(n+"값! " + returnVal);
return returnVal;
}
}
public static void main(String[] args) {
int ans;
ans = factorial(5);
System.out.println(ans);
}
}
factorial5 호출
factorial4 호출
factorial3 호출
factorial2 호출
factorial1 호출
factorial0 호출
0값이라 1을 반환
1값! 1
2값! 2
3값! 6
4값! 24
5값! 120
120
결과는 이렇게 된다.
5 -> 4- > 3 -> 2 ->1 을 호출시키고, 반환 순서대로 sysout이 출력된다.
이걸 공부한 뒤에 나오는 퀵 정렬은 대량 데이터를 효율적으로 정렬하는 것인데,
기준값이 되는 요소를 하나 선택해서 나머지 요소들을 기준값보다 작은 값과 큰 값으로
그룹 나누기를 반복해서 전체를 정렬한다.
그룹으로 나누어진 데이터가 하나일 때 까지 계속한다.
1. 기준값이 되는 요소를 하나 선택한다.
2. 나머지 요소를 기준값보다 작은 값과 큰 값으로 그룹 나누기를 반복한다.
3. 그룹으로 나누아진 데이터가 하나가 될 때까지 1과 2를 반복한다.
1) 그룹 나누기 함수 (divideArray)
2) 1)로 정렬을 수행하는 함수 (sortArray)
sortArray 함수에서 divideArray를 사용할 거고 , sortArray 함수 내에서 재귀 호출을 사용할 것이다.
인수로 지정된 a[start] ~ a[end] 배열을 정렬한다.
배열의 요소 수가 2개 이상이라는 조건에서 배열의 요소 그룹 나누기를 수행한 후,
앞쪽 그룹을 인수로 지정해 sortArray 함수를 호출하는 재귀 호출과,
뒤쪽 그룹을 인수로 지정해 sortArray 함수를 호출하는 재귀 호출을 수행한다.
a[head] ~ a[tail] 범위의 배열을 두 그룹으로 나누어 기준값의 인덱스를 반환한다.
기준값보다 앞쪽에는 기준값보다 작은 요소가 있고,
기준값보다 뒤쪽에는 기준값보다 큰 요소가 있다.
만약에 a[0] ~ a[6]을 두 그룹으로 나누어 3이 반환되면 a[3]이 기준값이며,
a[0]~a[2]는 a[3] 보다 작은 요소를 넣고, a[4]~a[6]은 a[3]보다 큰 요소를 넣으면 된다.
break 될 때까지는 무한 반복하는 구조이다.
자바 코드로 구현하면 아래와 같다.
public class 퀵정렬 {
public static void printArray(int [] a){
for(int i : a){
System.out.print("[" + i + "] ");
}
System.out.println("배열 인쇄 끝");
}
public static void sortArray(int [] a, int start, int end){
int pivot;
if(start < end){
//기준값 대소 관계에 따라 그룹 나누기
pivot = divideArray(a, start, end);
sortArray(a, start, pivot-1); //기준값보다 <<<
sortArray(a, pivot+1, end); // 기준값보다 >>> (끝까지)
}
}
private static int divideArray(int[] a, int head, int tail) {
int left, right, temp;
left = head+1; //첫요소 +1부터 뒤까지 >>>
right = tail; //끝 -> 앞까지 <<<
//기준값 a[head]보다 작은 요소를 <<< 큰 요소를 >>>
while(true){
while(left < tail && a[head] > a[left]){
//첫요소 +1 부터 >>>> 으로 이동
left++;
}
while(a[head] < a[right]){
//끝 -> 앞으로 가다가 기준값보다 작은 요소 찾기
right--;
}
if(left >= right){
//찾다가 확인할 거 없으면 종료
break;
}
temp = a[left];
a[left] = a[right];
a[right] = temp;
//기준값보다 큰 a[left]랑
//기준값보다 작은 a[right]를 교환함
left++;
right--;
}
temp = a[head];
a[head] = a[right];
a[right] = temp;
//기준값이랑 a[right]를 교환함
return right; //현재 기준값 위치를 반환함
}
public static void main(String[] args) {
int [] a = {4, 7, 1, 6, 2, 5, 3};
printArray(a);
sortArray(a, 0, a.length-1);
printArray(a);
}
}
[4] [7] [1] [6] [2] [5] [3] 배열 인쇄 끝
[1] [2] [3] [4] [5] [6] [7] 배열 인쇄 끝
divideArray 함수는 먼저 배열 a, 기준값 인덱스를 뜻하는 head랑
배열 끝 요소 인덱스를 뜻하는 tail을 인수로 사용한다.
또한 함수 안에는 첫 요소 +1부터 뒷 요소를 훑는 변수 left
뒷 요소부터 앞 요소까지 훑는 right
임시 변수인 temp가 있다.
while(true)안에 while문 2개랑 if문이 있는데,
첫번째 while문은 첫 요소 +1 부터 기준값보다 큰 요소를 찾으므로,
배열 뒷 요소 인덱스가 끝 요소보다 작고, 기준값이 배열 앞 요소값보다 큰 조건을 만족할 때, left 를 1 증가시키는 것이고,
두 번째 while문은 기준값이 배열 끝 요소값보다 작을 때 right를 1 감소시키는 것이다.
if문은 left >= right라는 조건이기 때문에, 반복시마다 기준값보다 큰 a[left]와 기준값보다 작은 a[right]를 교환한다.
sortArray는 배열 a, 정렬 기준 위치, 정렬 끝 요소 end를 사용한다.
또한 기준값 인덱스를 뜻하는 pivot 변수를 사용한다.
sortArray함수의 if문 안에는 (정렬 기준 위치가 정렬할 끝 요소보다 작아야 한다)
기준값의 대소 관계를 반복해서 판단하려고 재귀를 사용한다.
1) sortArray 함수의 start에 따라 기준값 중심으로 배열 요소를 정렬한 divideArray를 실행한다.
2) 기준값보다 작은 그룹용 sortArray를 실행한다
3) 기준값보다 큰 용 sortArray를 실행한다.
추적 코드를 삽입하면 아래와 같다.
public class 퀵정렬 {
public static void printArray(int [] a){
for(int i : a){
System.out.print("[" + i + "] ");
}
System.out.println("배열 인쇄 끝");
}
public static void sortArray(int [] a, int start, int end){
System.out.println("sortArray 호출 head 값 : " + start + " end 값 : " + end);
printArray(a);
int pivot;
if(start < end){
//기준값 대소 관계에 따라 그룹 나누기
pivot = divideArray(a, start, end);
System.out.println(pivot + " 기준값 ");
sortArray(a, start, pivot-1); //기준값보다 <<<
sortArray(a, pivot+1, end); // 기준값보다 >>> (끝까지)
}
}
private static int divideArray(int[] a, int head, int tail) {
System.out.println("divideArray 호출 head 값 : " + head + " tail 값 : " + tail);
int left, right, temp;
left = head+1; //첫요소 +1부터 뒤까지 >>>
right = tail; //끝 -> 앞까지 <<<
//기준값 a[head]보다 작은 요소를 <<< 큰 요소를 >>>
while(true){
while(left < tail && a[head] > a[left]){
//첫요소 +1 부터 >>>> 으로 이동
left++;
}
while(a[head] < a[right]){
//끝 -> 앞으로 가다가 기준값보다 작은 요소 찾기
right--;
}
if(left >= right){
//찾다가 확인할 거 없으면 종료
break;
}
temp = a[left];
a[left] = a[right];
a[right] = temp;
//기준값보다 큰 a[left]랑
//기준값보다 작은 a[right]를 교환함
left++;
right--;
}
temp = a[head];
a[head] = a[right];
a[right] = temp;
//기준값이랑 a[right]를 교환함
System.out.println(right + " 현재 기준값 위치");
return right; //현재 기준값 위치를 반환함
}
public static void main(String[] args) {
int [] a = {4, 7, 1, 6, 2, 5, 3};
sortArray(a, 0, a.length-1);
}
}
sortArray 호출 head 값 : 0 end 값 : 6
[4] [7] [1] [6] [2] [5] [3] 배열 인쇄 끝 //처음 호출 시 배열 상태
divideArray 호출 head 값 : 0 tail 값 : 6
3 현재 기준값 위치 //divideArray 한 번 돌렸을 때 기준값 상태
3 기준값 // 처음 divideArray 돌리고 난 기준값
sortArray 호출 head 값 : 0 end 값 : 2
[2] [3] [1] [4] [6] [5] [7] 배열 인쇄 끝
divideArray 호출 head 값 : 0 tail 값 : 2
1 현재 기준값 위치 //앞 부분 정렬이 끝난 상태임
1 기준값
sortArray 호출 head 값 : 0 end 값 : 0
[1] [2] [3] [4] [6] [5] [7] 배열 인쇄 끝
sortArray 호출 head 값 : 2 end 값 : 2
[1] [2] [3] [4] [6] [5] [7] 배열 인쇄 끝
sortArray 호출 head 값 : 4 end 값 : 6
[1] [2] [3] [4] [6] [5] [7] 배열 인쇄 끝
divideArray 호출 head 값 : 4 tail 값 : 6
5 현재 기준값 위치// 뒷 부분 정렬이 끝난 상태
5 기준값
sortArray 호출 head 값 : 4 end 값 : 4
[1] [2] [3] [4] [5] [6] [7] 배열 인쇄 끝
sortArray 호출 head 값 : 6 end 값 : 6
[1] [2] [3] [4] [5] [6] [7] 배열 인쇄 끝
이런 식으로 동작한다.
이거 사실 Arrays.sort() 쓰고 싶은데
요즘 프로그래머스에서 굳이 이런 식으로 짜는 것을 원해서? 공부해 보았다...
시간복잡도의 세계
댓글
댓글 쓰기