코드스테이츠 백엔드 부트캠프 21일차 - [자료구조/알고리즘] 재귀

wish17·2023년 1월 11일
Javasection_2알고리즘재귀코드스테이츠
0

코드스테이츠 백엔드 부트캠프

목록 보기
18/76
post-thumbnail

Section2 - [자료구조/알고리즘] 재귀

재귀 = 작은 문제를 해결함으로써 전체 문제를 해결하는 방법

재귀 함수란?

자기 자신을 호출하는 함수

재귀함수의 장점

  • 불필요하게 여러개의 반복문을 사용하지 않기 때문에, 코드가 간결해지고, 수정이 용이함.
  • 변수를 여러개 사용할 필요가 없다.

재귀함수의 단점

  • 반복문과 달리, 코드의 흐름을 직관적으로 파악하기 어렵다.

  • 반복하여 매서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장하게 된다. 이러한 과정은 반복문에 비해서 메모리를 더 많이 사용하게 된다.

  • 메서드를 호출하고 매서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생한다.

    • 컨텍스트 스위칭 비용 = 메모리 소모량이라고 생각하자.

재귀함수를 사용하기 위한 조건

  • 문제의 크기를 점점 작은 단위로 쪼갤수 있어야 한다.

  • 재귀 호출이 종료되는 시점이 존재해야 한다.

재귀로 문제를 해결하는 단계

  • 문제를 작게 쪼갠다.

  • 반복해서 가장 작은 단위로 문제를 쪼갠다.

  • 가장 작은 단위의 문제를 해결함으로써 전체 문제를 해결한다.

public int arrSum (int[] arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if (arr.length == 0) {
    return 0;
  }

  int[] tail = Arrays.copyOfRange(arr, 1, arr.length);
  //Arrays.copyOfRange(원본 배열, 복사할 시작인덱스, 복사할 마지막인덱스+1)

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr[0] + arrSum(tail);
}

재귀를 사용하기 적합한 상황

  • 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

  • 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

  • 변수 사용을 줄여 mutable state (변경 가능한 상태) 를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄이는 경우

재귀적 사고 연습하기

Guide : 재귀적으로 사고하기

  1. 재귀 함수의 입력값과 출력값 정의하기

  2. 문제를 쪼개고 경우의 수를 나누기

  3. 단순한 문제 해결하기

  4. 복잡한 문제 해결하기

  5. 코드 구현하기

일반적인 재귀 함수 형태

public type methodName(input1, input2, ...) {
  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // 반복되는(recursive) Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

Quiz

1번

수(num)를 입력받아 1부터 num까지의 합을 리턴하라.

나의 풀이

public class Solution { 
  public int sumTo(int num){
    if (num ==0) return 0;

    return num + sumTo(num--); // num-- x -> --num o
  }
}

-- 방향 잘못썻다.

public class Solution { 
  public int sumTo(int num){
    if (num ==0) return 0;

    return num + sumTo(--num);
  }
}

ans 동일

2번

수를 입력받아 홀수인지 여부를 리턴하라.

public class Solution { 
	public boolean isOdd(int num) {
    num = Math.abs(num);
    
    if(num==0) return false;

    return false==isOdd(--num);
  }
}

이렇게 했더니 재귀 횟수가 너무 많다고 나온다.

public class Solution { 
	public boolean isOdd(int num) {
    num = Math.abs(num);
    
    if(num==0) {
      return false;
    }else if(num==1){
      return true;
    }

    return true==isOdd(num-2);
  }
}

3번

수를 입력받아 n-factorial(n!; 엔-팩토리얼) 값을 리턴하라.

public class Solution { 
	public int factorial(int num){
    if(num==0) return 1;

    return num*factorial(--num);
  } 
}

4번

수(num)를 입력받아 피보나치 수열의 num번째 요소를 리턴하라.

public class Solution {
	public int fibonacci(int num){
    int result = 0;

    if(num==0) {
      return 0;
    }else if (num<3) {
      return 1;
    }else {
      result = fibonacci(num-2)+fibonacci(num-1);
    }
    return result;
	}
}

이것도 호출 횟수 오류...

public class Solution {
    int head = 1;
    int head2 = 0;
	public int fibonacci(int num){

    if(num==0) {
      return 0;
    }else if (num<3) { //여기가 문제였음
      return 1;
    }

    
    head = head + head2;

    return head + fibonacci(num-1);
	}
}

여기서 도저히 모르겠다...(호출 횟수 오류)

public class Solution {  
	public int fibonacci(int num){
    int result = 0;

		if(num==0) {
      return 0;
    }else if (num<2){
      return 1;
    }else {
      result = fibonacci(num-2)+fibonacci(num-1);
    }
    return result;
	}
}

num < 2만해도 된다.. (근데 num<3이 수행 횟수가 더 적음... 따라서 더 좋은건데... 막혀있다...)

5번

배열을 입력받아 모든 요소의 합을 리턴하라.

public class Solution { 
	public int arrSum(int[] arr){
    if(arr.length == 0) return 0;

    int[] tail = Arrays.copyOfRange (arr, 1, arr.length);

    return arr[0] + arrSum(tail);
  }
}

6번

배열을 입력받아 모든 요소의 곱을 리턴하라.

public class Solution {  
	public int arrProduct(int[] arr){
    if(arr.length == 0) return 1;

    int[] tail = Arrays.copyOfRange (arr, 1, arr.length);

    return arr[0]*arrProduct(tail);
	} 
}

7번

배열을 입력받아 그 길이를 리턴하라.

public class Solution { 
	public int arrLength(int[] arr){
    if(arr.length == 0) return 0;

    int[] tail = Arrays.copyOfRange (arr, 1, arr.length);

    return 1 + arrLength(tail);
	} 
}

8번

수(num)와 배열을 입력받아 차례대로 num개의 요소가 제거된 새로운 배열을 리턴하라.

public class Solution { 
	public int[] drop(int num, int[] arr){
    if(arr.length == 0) return new int[]{};
    
    int[] tail = Arrays.copyOfRange (arr, 1, arr.length);

    if(num==0) return tail;
    

    return drop(--num,tail);
	} 
}

이렇게 하면 하나 더 빼는게 된다.

public class Solution { 
	public int[] drop(int num, int[] arr){
    if(arr.length == 0) return new int[]{};

    if(num==0) return arr;
    

    return drop(--num,Arrays.copyOfRange (arr, 1, arr.length));
	} 
}

9번

수(num)와 배열을 입력받아 차례대로 num개의 요소만 포함된 새로운 배열을 리턴하라.

public class Solution { 
	public int[] drop(int num, int[] arr){
    if(arr.length == 0 || num==0) return arr;

    return drop(--num, Arrays.copyOfRange (arr, 0, arr.length-1));
	} 
}

범위 밖에서 오류남... == 초기화버튼 누름 됨

public class Solution {
	public int[] take(int num, int[] arr){
    if(arr.length ==0|| num>=arr.length) return arr;
    
    //return take(--num, Arrays.copyOfRange (arr, 0 , arr.length-1)); // 괜히 num을 건드려서 개고생.. 무조건 건드리는거 아니다./..

    int[] dest = Arrays.copyOfRange(arr, 0, arr.length -1); // num과 arr의 길이가 같아질 때 까지 줄여나가기.

    return take(num,dest);
	} 
}

습관적으로 num값을 빼버려서 찾느라 고생했다..

ans

import java.util.*;

// public class Solution { 
//     public int[] take(int num, int[] arr){
//     //재귀 함수를 사용하여, 새로운 배열에 기존 입력된 arr 배열의 마지막 인덱스의 값부터 넣어줍니다.

//     //base case : 문제를 더 이상 쪼갤 수 없는 경우
//     if(arr.length == 0 || num == 0) { //입력된 배열이 빈 배열인 경우, 입력된 num이 0인 경우
//       return new int[]{}; //빈 배열을 반환합니다.
//     }

//     //recursive Case : 그렇지 않은 경우

//     //배열의 가장 첫번째 요소만을 가지고 있는 head 배열을 선언, 할당합니다.
//     int[] head = Arrays.copyOfRange(arr, 0, 1);

//     //남은 요소를 가지고 있는 tail 배열을 선언, 할당하고, 해당 배열의 요소가 모두 제거될 때까지 재귀함수를 호출합니다.
//     //한번 호출될 때마다, num을 하나씩 줄여줍니다. head 배열에 현재 선택된 요소가 있기 때문에, 앞으로 선택할 요소를 나타내는 num을 1씩 줄여서 재귀함수가 실행되어야 합니다.
//     int[] tail = take(num - 1, Arrays.copyOfRange(arr, 1, arr.length));

//     //재귀함수가 모두 호출된 이후에, 할당된 head배열과 tail 배열을 합친 새로운 배열을 선언, 할당합니다.
//     //새로운 배열을 선언합니다. 배열의 크기는 head.length와 tail.length를 합친 크기로 선언합니다.
//     int[] dest = new int[head.length + tail.length];
    
//     //System.arraycopy메서드를 사용하여, head, tail 두 배열의 요소를 모두 dest 배열에 복사합니다.
//     System.arraycopy(head, 0, dest, 0, head.length);
//     System.arraycopy(tail, 0, dest, head.length, tail.length);

//     return dest;
//     } 
// }

public class Solution { 
    public int[] take(int num, int[] arr){
    //base Case : 더 이상 쪼개어 생각할 수 없는 경우
    //선택할 요소의 갯수(num)가 배열의 전체 요소의 갯수보다 많은 경우, 입력된 배열을 반환합니다.
    if(num >= arr.length) {
      return arr;
    }
    //선택할 요소의 갯수(num)가 0인 경우, 입력된 배열의 요소가 아무것도 없는 경우에는 빈 배열을 반환합니다.
    if(num == 0 || arr.length == 0) {
      return new int[]{};
    }

    //맨 뒷부분의 요소를 제외한 나머지 배열을 tail이라는 변수에 할당합니다.
    int[] tail = Arrays.copyOfRange(arr, 0, arr.length -1);

    //제외한 배열을 포함하여 다시 재귀함수를 실행합니다.
    return take(num, tail);
    } 
}

10번

배열을 입력받아 모든 요소의 논리곱(and)을 리턴하라.

public class Solution {  
	public boolean and(boolean[] arr){
    if (arr.length==0) return true;

    return arr[0]&&and(Arrays.copyOfRange (arr, 1, arr.length));
	} 
}

11번

배열을 입력받아 모든 요소의 논리합(or)을 리턴하라.

public class Solution { 
	public boolean or(boolean[] arr){
    if (arr.length==0) return false;

    return arr[0]||or(Arrays.copyOfRange (arr, 1, arr.length));
	} 
}

12번

배열을 입력받아 순서가 뒤집힌 배열을 리턴하라.

public class Solution { 
	public int[] reverseArr(int[] arr){

    if (arr.length==0||count==arr.length) return arr;
    
    int[] tail=Arrays.copyOf(arr, arr.length+1);
    tail[tail.length-1] = arr[0];
    tail = Arrays.copyOfRange (tail, 1, tail.length);

    if(tail.length>=3||tail[0]==arr)

    return reverseArr(tail);
	} 
}

이렇게 하면 탈출지점을 못찾는다..

아예 방법을 바꿔서 기존 배열을 뜯어서 다시 붙이는 방식으로 해봤다.

public class Solution { 
  int count =1;
	public int[] reverseArr(int[] arr){
    if(arr.length==0||count==arr.length) return arr;

    int[] head = reverseArr(Arrays.copyOfRange(arr, 0, 1));
    int[] tail = reverseArr(Arrays.copyOfRange(arr, 1, arr.length));
    int[] dest = new int[arr.length];

    System.arraycopy(head,0,dest,arr.length-1,1);
    System.arraycopy(tail,0,dest,0,tail.length);

    count++;

    return dest;
	} 
}

기능은 정상적으로 수행되는데 재귀 호출횟수가 많다고 나온다.

public class Solution { 
  int count =1;
	public int[] reverseArr(int[] arr){
    if(arr.length==0||count==arr.length) return arr;

    int[] head = Arrays.copyOfRange(arr, 0, 1);
    int[] tail = reverseArr(Arrays.copyOfRange(arr, 1, arr.length));
    int[] dest = new int[arr.length];

    System.arraycopy(head,0,dest,arr.length-1,1);
    System.arraycopy(tail,0,dest,0,tail.length);

    count++;

    return dest;
	} 
}

head는 굳이 재귀시킬 필요 없었다.

public class Solution { 
	public int[] reverseArr(int[] arr){
    if(arr.length==0) return arr;

    int[] head = Arrays.copyOfRange(arr, 0, 1);
    int[] tail = reverseArr(Arrays.copyOfRange(arr, 1, arr.length));
    int[] dest = new int[arr.length];

    if(tail.length==0) return arr;

    System.arraycopy(head,0,dest,arr.length-1,1);
    System.arraycopy(tail,0,dest,0,tail.length);
    
    return dest;
	} 
}

count도 별로 필요 없었다.

public class Solution { 
	public int[] reverseArr(int[] arr){
    if(arr.length==0) return arr;

    int[] head = Arrays.copyOfRange(arr, 0, 1);
    int[] tail = reverseArr(Arrays.copyOfRange(arr, 1, arr.length));
    int[] dest = new int[arr.length];

    System.arraycopy(head,0,dest,arr.length-1,1);
    System.arraycopy(tail,0,dest,0,tail.length);
    
    return dest;
	} 
}

메서드 자체에 tail배열이 input값으로 들어가기 때문에
추가적인 if문도 필요 없었다.

ans

public class Solution { 
	public int[] reverseArr(int[] arr){
    //재귀 함수를 사용하여, 새로운 배열로 기존 입력된 arr 배열의 마지막 인덱스의 값부터 넣어줍니다.

    //base case : 문제를 더 이상 쪼갤 수 없는 경우
      if(arr.length == 0) { //입력된 배열이 빈 배열인 경우
        return new int[]{}; //빈 배열을 반환합니다.
      }
    //recursive Case : 그렇지 않은 경우

      //배열의 가장 마지막 요소만을 가지고 있는 head 배열을 선언, 할당합니다.
      int[] head = Arrays.copyOfRange(arr, arr.length - 1, arr.length);

      //남은 요소를 가지고 있는 tail 배열을 선언, 할당하고, 해당 배열의 요소가 모두 제거될 때까지 재귀함수를 호출합니다.
      int[] tail = reverseArr(Arrays.copyOfRange(arr, 0, arr.length - 1));

      //재귀함수가 모두 호출된 이후에, 할당된 head배열과 tail 배열을 합친 새로운 배열을 선언, 할당합니다.
      //새로운 배열을 선언합니다. 배열의 크기는 head.length와 tail.length를 합친 크기로 선언합니다.
      int[] dest = new int[head.length + tail.length];
      
      //System.arraycopy메서드를 사용하여, head, tail 두 배열의 요소를 모두 dest 배열에 복사합니다.
      System.arraycopy(head, 0, dest, 0, head.length);
      System.arraycopy(tail, 0, dest, head.length, tail.length);

      return dest;
	} 
}

저는 0번 인덱스를 뽑아 마지막 인덱스 자리에 붙이는 방식으로 했는데,
답지는 마지막 인덱스를 뽑아 0번인덱스부터 순차적으로 붙이는 방식으로 풀었다.































profile
wish17
.
이전 포스트

코드스테이츠 백엔드 부트캠프 20일차 - Section1회고

다음 포스트

코드스테이츠 백엔드 부트캠프 22일차 - 재귀, JSON

0개의 댓글