SEB_BE 21일차 - Section2 재귀

• 오늘은 섹션2에 들어가는 날이다. 오늘부터 계속 매일 오전에 Daily coding이 있다. 문제를 풀고 헷갈렸던 것을 기록하려고 한다.

Daily coding

HashMap<String, String> result = new HashMap<>(); //해시맵 선언
arr[0], arr[arr.length-1] // 배열의 첫번째와 마지막 요소

💡 오늘의 학습목표

• 재귀
• 재귀 연습문제

📔 재귀 함수

• 자기 자신을 호출하는 함수
• 메모리를 많이 차지함 (실무에서는 잘 쓰지 않음)

  • 자연수 배열의 합을 구하는 알고리즘
    문제를 가장 작은 단위로 쪼개서 해결해보기

    재귀함수로 해결

    public int arrSum (int[] arr) {
    //빈 배열을 받으면 0을리턴
    	if (arr.lingth ==0) return 0;
    // 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
    	int[] tail = Arrays.copyOfRange(arr, 1, arr.length);
    // 배열 첫번째 요소 + 나머지 요소의 배열을 받는 arrSum함수
    // -> 재귀를 통해 문제를 작게 쪼개나가기
    	return arr[0] + arrSum(tail);
    }

📖 재귀 함수의 동작 원리

1. 재귀함수의 입력값과 출력값 정의하기
arrSum: [int] -> int int 타입을 요소로 갖는 배열을 입력 받고 int 타입 리턴
2. 문제를 쪼개고 경우의 수를 나누기
문제를 쪼갤 기준(일반적으로 입력값으로 기준 정함)
경우의 수 (문제를 더 이상 쪼갤 수 없는 경우/ 그렇지 않은 경우)

• 함수 arrSum은 입력값이 빈 배열 / 그렇지 않은 경우 각각 다른 방식 처리
• arrSum: [number] => arrSum(new int[]{}) / arrSum(new int{e1, e2, ...,en})

3. 단순한 문제 해결하기
가장 해결하기 쉬운 문제부터 해결 (재귀의 기초(재귀의 탈출조건 구성))

• 더이상 쪼갤 수 없는 경우는 빈 배열일 경우 이때 arrSum(new int[]{}) 의 리턴은 0

4. 복잡한 문제 해결하기
길이가 1 이상인 배열이 함수 arrSum에 입력된 경우, 맨 앞 요소 결과를 따로 구하고(head), 나머지 요소를 새로운 입력값으로 갖는 문제로 구분, 이 결과를 head에 더하기

• arrSum: [num] => numberarrSum(new int[]{}) = 0 /
  arrSum([e1, e2, ..., en]) = arrSum(new int[]{e1} + arrSum(new int[]{e2,...,en})

5. 코드 구현하기
일반적인 재귀 함수의 템플릿

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

📜 예제 - 구구단

📜 예제 - 팩토리얼

📜 예제 - 피보나치수열

if (num == 0) return 0;
if (num == 1) return 1;
	return fibonacci(num-1) + fibonacci(num-2);

📜 문제풀이

• 홀수 여부 리턴

if (num ==0) return false; // num이 0이면 false 리턴
if (num ==1) return true; // num이 1이면 true 리턴
	return ex(num-2); // num에서 2를 계속 빼면서 홀수 여부 확인 
    //num이 5라면 조건을 거쳐 ex(3)이 되고 다시 조건을 거쳐서 1이 되면 true 리턴

• num개만큼 제거된 배열 만들기

if (num == 0 || arr.length ==0) return arr; // 0이거나 빈배열일 경우 그대로 배열 리턴
	return ex(num-1, Arrays.copyOfRange(arr, 1, arr.length)); // 나머지 배열 리턴

• n개 만큼의 el포함된 새 배열 리턴

if (num == 0 || arr.length ==0) return new int[]{};
  
    // arr의 처음 요소를 가져온다.
    // 그 요소와 나머지 부분을 take 재귀함수에 num-1 
    int[] front = Arrays.copyOf(arr,1); // 배열 첫번째 원소 가져오기
    int[] behind = take(num-1, Arrays.copyOfRange(arr,1,arr.length)); // 나머지 요소
  // return IntStream.concat(Array.stream(front),Araays.stream(behind))
    //                  .toArray(); //스트림풀이
   int[] answer = new int[front.length + behind.length]; // 결과 배열 생성
    System.arraycopy(front, 0, answer ,0, front.length);
    System.arraycopy(behind,0,answer,front.length,behind.length); // 배열 합쳐주기 
return answer;

• 순서가 반대로 된 배열 리턴

// arr의 마지막 요소 복사 (Arrays.copyOfRange(arr, arr.length-1, arr.length);
//+ 나머지 요소(ex(Arrays.copyOf(arr,arr.length-1));
//arraycopy로 두개 붙이기

회고

오늘부터 새로운 섹션을 시작하면서 난이도도 그렇고 전체적인 학습콘텐츠? 도 조금씩 바뀌었다. 이번섹션은 알고리즘 문제풀이가 많은데 너무 걱정이다.. 오늘은 운좋게 엄청 잘하시는 페어분을 만나서 1대1 강습수준으로 받았다..ㅋㅋㅋ같이 한 페어분께 너무 죄송스럽고 내가 잘 이해하는지 친절히 알려주셔서 너무 감사했다. 아마 혼자였다면 손도 못댔을것 같다. 재귀라는 개념 자체도 힘들고 그걸 어떻게 써야하는지도 너무 어렵다🤣