[Day14] Recursion, Two-pointer

재귀 (Recursion)

• 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 기법
• 얼마나 반복되는지 모를 때 사용

  public class Test {
    public static void main(String[] args) {
        int n=10;
        printNos(n);
    }
  	
    public static void printNos(int n) {
        if(n > 0) {
            printNos(n - 1);
            System.out.print(n + " ");
        }
    }
  }
  

  재귀를 사용하는 사례

  분할 정복 (Divide and Conquer)

• 문제를 더 작은 하위 문제로 나누어 해결하는 방식이 필요할 때.
• (ex) 퀵 정렬 (Quick Sort) 및 병합 정렬 (Merge Sort): 배열을 여러 부분으로 나누고 각각을 정렬한 후 다시 합치는 방식입니다.

트리 및 그래프 탐색

• 트리나 그래프 구조에서 깊이 우선 탐색(DFS)과 같은 탐색 알고리즘이 필요할 때.
• (ex) 이진 트리의 순회 (전위, 중위, 후위 순회)

순열, 조합, 부분집합 생성

• 주어진 집합에서 가능한 모든 조합이나 순열을 생성해야 할 때.
• (ex) 특정 숫자의 조합을 구하는 문제

백트래킹 (Backtracking)

• 모든 가능한 경우를 탐색해야 하며, 특정 조건을 만족할 때 해결책을 찾는 경우
• (ex) N-Queens 문제, 미로 찾기, 스도쿠 해결 등.

피보나치 수열

• 앞의 두 수의 합이 바로 뒤의 수가 되는 수의 배열
• (ex) F(n) = F(n-1) + F(n-2)로 정의되는 피보나치 수열.

동적 프로그래밍

• 재귀적 구조가 필요한 문제에서 메모이제이션 기법을 사용할 경우
• (ex) 특정 문제를 재귀적으로 해결하면서 이전에 계산한 결과를 저장하여 성능을 개선하는 경우

factiorial

package recur;

public class FactorialTest {
	
	public static void main(String[] args) {
		int n=5;
		int result=factorial(n);
		System.out.println(result);
	}
	
	public static int factorial(int n) {
		if(n==0) return 1;
		return n * factorial(n-1);
	}
}

재귀의 장/단점

• 장점
  • 코드가 간결하고 이해하기 쉬움
  • 복잡한 문제를 쉽게 해결 가능
• 단점
  • 스택 메모리 사용 → 스택 오버플로우 발생 가능
  • 반복문보다 비효율적(성능 이슈)

투포인터

• 주로 배열이나 리스트와 같은 선형 자료 구조에서 사용되는 알고리즘
• 두 개의 포인터(left, right) 사용

/*
Q. 정렬된 배열 nums와 정수 target이 주어질 때, 두 수의 합이 target이 되는 두 수의 인덱스를 반환하세요
*/
public class TwoSum {

	public static void main(String[] args) {
		int []nums = {1,2,3,4,6};
		int target=6;
		
		int left=0;
		int right = nums.length-1;
		
		while(left<right) {
			int sum=nums[left]+nums[right];
			if(sum == target) {
				System.out.println(left+":"+right);
				break;
			}else if(sum < target) {
				left++;
			}else {
				right--;
			}
		}
	}

}

적용 사례

합을 찾는 문제

• 두 포인터를 사용하여 특정 합을 찾는 경우, 한 포인터는 시작 지점에서, 다른 포인터는 끝 지점에서 시작하여 두 포인터를 이동시키며 조건을 만족하는 경우를 찾음.

중복 제거

• 정렬된 배열에서 중복된 요소를 제거할 때, 하나의 포인터는 현재 위치를 가리키고 다른 포인터는 중복 여부를 확인하는 데 사용.

슬라이딩 윈도우

• 배열이나 리스트와 같은 선형 자료 구조에서 연속적인 부분 배열이나 부분 문자열을 처리하는 데 유용한 알고리즘
• 이 기법은 특정 범위를 효율적으로 탐색하고, 계산할 수 있음.

슬라이딩 윈도우는 두 개의 포인터 또는 인덱스를 사용하여 데이터의 일부를 선택하고, 이 선택된 범위를 “윈도우”라고 부름. 이 윈도우는 데이터의 특정 부분을 나타내며, 필요에 따라 크기나 위치를 조정할 수 있음.

특징

• 연속성: 윈도우 내의 요소들은 항상 연속적.
• 효율성: 윈도우의 크기를 변경하면서 반복적으로 계산할 수 있어, 중복 계산을 피하고 시간 복잡도를 줄임.
• 상태 유지: 각 윈도우의 상태를 유지하면서 필요한 계산을 수행할 수 있음.
• 시간 복잡도 감소: O(n)
• 간결한 코드: 복잡한 중첩 루프를 줄이고, 코드의 가독성을 높임.

사용 예시

• 최대/최소 합의 부분 배열 찾기: 연속된 K 개의 요소의 최대 합을 찾는 문제.
• 문자열 문제: 주어진 문자열에서 특정 조건을 만족하는 부분 문자열의 길이나 개수를 찾는 문제.
• 중복 제거: 특정 조건을 만족하는 부분 배열에서 중복 요소를 제거하는 문제.

슬라이딩 윈도우의 유형

• 고정 크기 윈도우: 윈도우의 크기가 고정되어 있는 경우 (예: K 개의 요소).
• 가변 크기 윈도우: 윈도우의 크기가 동적으로 조정되는 경우 (예: 조건에 따라 요소를 추가하거나 제거).

/*
Q. 최대합이 되는 연속된 k개의 요소 찾기
*/
public class SlidingWindow {
	public static void main(String[] args) {
		int[] nums= {1,2,3,4,5};
		int k=3; //연속된 요소의 개수
		int result=maxSum(nums,k);
		System.out.println(result);
	}
	
	public static int maxSum(int[] nums, int k) {
		int n=nums.length;	
		if(n<k) {
			throw new IllegalArgumentException("배열의 길이가 k보다 커야합니다");
		}
		int maxSum=0;
		for (int i = 0; i < k; i++) {
			maxSum += nums[i];
		}
		int windowSum=maxSum;
		for (int i = k; i < n; i++) {
			windowSum += nums[i]-nums[i-k];
			maxSum=Math.max(maxSum, windowSum);
		}
		return maxSum;	
	}
}

Exception

예외 처리 방법에는 try-catch와 throws 두 가지가 있다.

public class Test {
	public static void main(String[] args)  {
		int x = 100;
		int y = 0;
			
		y = Integer.parseInt(args[0]);
		int result;
		// try-catch 사용
		try {
			result = Divider.divide(x, y);
			System.out.println(result);
		} catch (MyException e) {
			System.out.println(e.getMessage());
		}
		System.out.println("더 중요한 일...");
	}
}
class Divider{
	public static int divide(int x, int y) throws MyException{
		if(y==0) {
			throw new MyException("0을 입력하지 마세요");
		}
		return x/y;
	}
}
class MyException extends Exception{
	public MyException(String message) {
		super(message);
		// throws MyException을 사용하여 직접 예외를 정의하고 던질 수 있음
		// new MyException("0을 입력하지 마세요") 형태로 예외 발생 가능
	}
}

2차원 배열 다루기

행 우선 순회 (왼쪽 -> 오른쪽)

for (int i = 0; i < rows; i++) {
	int cols=arr[i].length;
    for (int j = 0; j < cols; j++) {
        System.out.print(arr[i][j] + " ");
    }
}

출력

1 2 3
4 5 6
7 8 9

열 우선 순회 (위 -> 아래)

int rows=arr.length;
int cols=arr[0].length;
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        System.out.print(arr[i][j] + " ");
    }
}

출력

1 4 7
2 5 8
3 6 9

지그재그 순회

for (int i = 0; i < rows; i++) {
    if (i % 2 == 0) { // 짝수 행: 왼쪽 → 오른쪽
        for (int j = 0; j < cols; j++) {
            System.out.print(arr[i][j] + " ");
        }
    } else { // 홀수 행: 오른쪽 → 왼쪽
        for (int j = cols - 1; j >= 0; j--) {
            System.out.print(arr[i][j] + " ");
        }
    }
    System.out.println();
}

출력

1 2 3
6 5 4
7 8 9

---

END