재귀

package recur;

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

 

재귀를 사용하는 사례

  • 분할 정복 (Divide and Conquer): 문제를 더 작은 하위 문제로 나누어 해결하는 방식이 필요할 때. 
    • 퀵 정렬 (Quick Sort) 및 병합 정렬 (Merge Sort): 배열을 여러 부분으로 나누고 각각을 정렬한 후 다시 합치는 방식입니다.
  • 트리 및 그래프 탐색: 트리나 그래프 구조에서 깊이 우선 탐색(DFS)과 같은 탐색 알고리즘이 필요할 때. 예: 이진 트리의 순회 (전위, 중위, 후위 순회)
  • 순열, 조합, 부분집합 생성: 주어진 집합에서 가능한 모든 조합이나 순열을 생성해야 할 때. 예: 특정 숫자의 조합을 구하는 문제
  • 백트래킹 (Backtracking): 모든 가능한 경우를 탐색해야 하며, 특정 조건을 만족할 때 해결책을 찾는 경우.예: N-Queens 문제, 미로 찾기, 스도쿠 해결 등.
  • 피보나치 수열: 앞의 두 수의 합이 바로 뒤의 수가 되는 수의 배열. 
    예: F(n) = F(n-1) + F(n-2)로 정의되는 피보나치 수열.
  • 동적 프로그래밍: 재귀적 구조가 필요한 문제에서 메모이제이션 기법을 사용할 경우.예: 특정 문제를 재귀적으로 해결하면서 이전에 계산한 결과를 저장하여 성능을 개선하는 경우.

 

Factorial 예제

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);
	}
	

/* for 문 */
	
//	public static void main(String[] args) {
//		int n = 5;
//		int result = 1;
//		
//		for(int i = 1; i <= n; i++) {
//			result *= i;
//		}
//		
//		System.out.println(result);
//
//	}

}

 

재귀 장/단점

장점

  • 코드를 간결하게 작성할 수 있음
  • 복잡한 문제를 쉽게 해결할 수 있음

단점

  • 함수 호출 시마다 시스템 스택 메모리를 사용하므로 스택오버플로우가 발생될 수 있음
  • 성능이 비효율적, 반복문으로 대체할 수 있는지 고려

 

배열

1차원 배열 - 투포인터

투 포인터(Two Pointers) 기법은 주로 배열이나 리스트와 같은 선형 자료 구조에서 사용되는 알고리즘 기법. 이 방법은 두 개의 포인터를 사용하여 문제를 해결.

 

적용 예)

  • 합을 찾는 문제: 두 포인터를 사용하여 특정 합을 찾는 경우, 한 포인터는 시작 지점에서, 다른 포인터는 끝 지점에서 시작하여 두 포인터를 이동시키며 조건을 만족하는 경우를 찾음.
  • 중복 제거: 정렬된 배열에서 중복된 요소를 제거할 때, 하나의 포인터는 현재 위치를 가리키고 다른 포인터는 중복 여부를 확인하는 데 사용.
  • 슬라이딩 윈도우: 연속된 부분 배열의 합이나 최댓값을 찾는 문제에서 두 포인터를 사용하여 윈도우의 크기를 조절.

➡️ 이 기법은 시간 복잡도를 줄이고, 공간 복잡도도 절약할 수 있어 매우 효율적

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

package array1;

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--;
			}
			
		}

	}

}

 

슬라이딩 윈도우

슬라이딩 윈도우(Sliding Window) 기법은 주로 배열이나 리스트와 같은 선형 자료 구조에서 연속적인 부분 배열이나 부분 문자열을 처리하는 데 유용한 알고리즘 기법. 이 기법은 특정 범위를 효율적으로 탐색하고, 계산할 수 있음.
  • 슬라이딩 윈도우는 두 개의 포인터 또는 인덱스를 사용하여 데이터의 일부를 선택하고, 이 선택된 범위를 "윈도우"라고 부름. 이 윈도우는 데이터의 특정 부분을 나타내며, 필요에 따라 크기나 위치를 조정할 수 있음.

📍 주요 특징

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

 

📍 사용 예시

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

 

📍 슬라이딩 윈도우의 유형

  • 고정 크기 윈도우: 윈도우의 크기가 고정되어 있는 경우 (예: K 개의 요소).
  • 가변 크기 윈도우: 윈도우의 크기가 동적으로 조정되는 경우 (예: 조건에 따라 요소를 추가하거나 제거).
/*
Q. 최대합이 되는 연속된 k개의 요소 찾기
*/

package array1;

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;
	}

}

 

2차원 배열

행우선순회

/*
    1 2 3 
    4 5 6 
    7 8 9 
*/

package array2;

public class 행우선순회 {

	public static void main(String[] args) {
		int [][]array= {
				{1,2,3},
				{4,5,6},
				{7,8,9}
		};
		
		trave(array);

	}
	
	public static void trave(int [][] arr) {
		int rows=arr.length;
		
		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]+" ");
			}
			System.out.println();
		}
	}

}

열우선순회

/*
    1 4 7 
    2 5 8 
    3 6 9 
*/

package array2;

public class 열우선순회 {

	public static void main(String[] args) {
		int [][]array= {
				{1,2,3},
				{4,5,6},
				{7,8,9}
		};
		
		trave(array);

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

}

지그재그순회

/*
    1 2 3 
    6 5 4 
    7 8 9 	
*/

package array2;

public class 지그재그순회 {

	public static void main(String[] args) {
		int [][]array= {
				{1,2,3},
				{4,5,6},
				{7,8,9}
		};
		
		trave(array);

	}
	
	public static void trave(int [][] arr) {
		int rows=arr.length;
		int cols=arr[0].length;
		
		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 4 7 
    8 5 2 
    3 6 9 
*/

public class ReverseZigzagTraversal {
    public static void main(String[] args) {
        // 2차원 배열 정의 및 초기화
        int[][] array = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        // 역방향 지그재그 순회를 위한 메서드 호출
        traverseReverseZigzag(array);
    }

    // 2차원 배열을 역방향 지그재그 방식으로 순회하는 메서드
    public static void traverseReverseZigzag(int[][] array) {
        // 배열의 행 길이
        int rows = array.length;

        // 배열의 열 길이
        int cols = array[0].length;

        // 각 열을 순회
        for (int j = 0; j < cols; j++) {
            // 홀수 열일 때 (1, 3, ...)는 아래에서 위로 순회
            if (j % 2 == 0) {
                for (int i = 0; i < rows; i++) {
                    System.out.print(array[i][j] + " ");
                }
            } 
            // 짝수 열일 때 (0, 2, ...)는 위에서 아래로 순회
            else {
                for (int i = rows - 1; i >= 0; i--) {
                    System.out.print(array[i][j] + " ");
                }
            }
        }
    }
}

 

Exception

Exception 처리 기법

1️⃣ try~catch

package exception;

public class Test {

	public static void main(String[] args) {
		int x = 100;
		int y = 0;
		
		try {
			y = Integer.parseInt(args[0]);
			System.out.println(x / y);
		} catch(ArrayIndexOutOfBoundsException e) {
			System.out.println("args[0]을 제공해야 합니다.");
			y = 1;
		} catch(ArithmeticException e) {
			
		} catch(NumberFormatException e) {
			System.out.println("args[0]은 Integer 타입이어야 합니다.");
		} catch(Exception e) { // 최상위 Exception, 정교한 복구 불가능(보안에 나쁨)
			
		}
		
		System.out.println("중요한 일");
		
	}

}

2️⃣ throws

package exception;

public class Test {

	public static void main(String[] args) {
		int x = 100;
		int y = 0;
		
        y = Integer.parseInt(args[0]);

        int result;
        try {
            result = Divider.divide(x, y);
            System.out.println(result);
        } catch (ArithmeticException e) {
 
        }
		
		System.out.println("중요한 일");
		
	}

}

class Divider {
	public static int divide(int x, int y) throws Exception {
    	// ... Exception 처리
		return x / y;
		
	}
}

 

User define Exception

  • RuntimeException ➡️ Checked Exception
  • Exception Message 간단, 명확 전달
package exception;

public class Test {

	public static void main(String[] args) {
		int x = 100;
		int y = 0;

        y = Integer.parseInt(args[0]);

        int result;
        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);
		
	}
	
}
728x90
반응형

'LG 유플러스 유레카 SW > Java' 카테고리의 다른 글

[#13] Java Generic & Collection  (0) 2025.02.12
[#12] Java 코드 성능 & 가독성 높이는 법  (0) 2025.02.11
[#11] Java 다형성 + Class 다이어그램 그려보기  (0) 2025.02.10
[#10] Java 들어가기 + 알고리즘 스터디  (0) 2025.02.07
[#9] Java 들어가기 전에..  (0) 2025.02.06

티스토리툴바