1️⃣ DP 동적 프로그래밍 이란?

DP(Dynamic Programming)이란 - 큰 문제를 작은 문제로 나누고, 중복되는 문제를 저장해두었다가 재사용하는 걸 말한다!

즉, 쉽게 정리하자면 다음과 같다.

큰 문제 → 작은 문제로 쪼개고 → 작은 문제의 답을 저장 → 조합해서 큰 문제 해결
ex) 피보나치
     dp[1] = 1;
     dp[2] = 1;
     dp[3] = dp[1] + dp[2]; // → 2    
     dp[4] = dp[2] + dp[3]; // → 3
     dp[5] = dp[3] + dp[4]; // → 5
- 즉, dp[n] = dp[n-1] + dp[n-2]
- 초기값(dp[1], dp[2])이 있어야 그다음 값들을 계산 🅾️

메모이제이션 or 탐다운/바텀업 접근을 사용하여 계산을 줄인다고 하는데- 그렇다면, 이 세가지의 개념을 알고 넘어가야겠다.

• 메모이제이션 - 계산 결과를 저장해 중복 계산을 피하는 방식
• 탑다운/바텀업
  • 탑다운 - 함수를 위에서부터 재귀적으로 호출
  • 바텀업 - 아래에서부터 반복적으로 계산

💡 메모이제이션 + 탑다운 방식 (재귀)

static int[] memo = new int[100];

static int TopDown(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n]; // 저장된 값이 있으면 그대로 반환
    return memo[n] = TopDown(n - 1) + TopDown(n - 2); // 계산 후 저장
}

💡 바텀업 방식 (반복문 기반)

static int BottomUp(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // 이전 값들을 반복문으로 계산
    }
    return dp[n];
}

🔍 핵심 정리

2️⃣ 탐욕 알고리즘 이란?

탐욕 알고리즘(Greedy Algorithm)이란 - 매 순간 최선의 선택을 하는 방식이다! 즉, 실시간에 가장 좋아 보이는 것만 골라서 문제를 해결한다는 것!

쉽게 정리하자면 다음과 같다.

항상 그 순간 최선의 선택 → 그 선택이 전체에서도 최선이 될 것이라 믿고 진행
ex) 회의실 배정 문제
    회의들.sortBy(끝나는시간); // 1. 정렬(끝나는 시간 순)
        for (회의 : 회의들) {
            if (회의.시작 >= 현재시간) { // 2. 조건에 맞는 회의만 선택
            count++;
            현재시간 = 회의.끝;
             }
        }
👉 총 count 개의 회의를 겹치지 않게 선택하여 회의실 배정하는 게 최적!

✨ 언제 무엇을 써야 할지 고민이라면?

• 문제를 보고 "부분 문제의 결과를 재사용할 수 있나?" 생각하면 → DP
• 문제를 보고 "현재 최선의 선택이 전체도 최선이 될까?" 생각하면 → Greedy

🥹 알고리즘 문제를 풀다보면 재귀함수를 호출해야하는 경우가 많은데, 이번 글에서 확실하게 풀고 넘어가려고 한다.
(이제부터 헷갈리기는 이 글을 마지막으로 꼭 끝내자!)

📌재귀 호출이란?

재귀 호출이라 하면 알다시피 함수 내에서 또 해당 함수가 호출되는 것을 뜻한다. 그러면 내가 어려워하는 부분은 무엇일까? 

재귀함수는 계속해서 반복하는 함수이기 때문에, 꼭 '기저조건'이 필요하다. 즉 함수를 끝낼 수 있는 조건을 말한다.

간단한 재귀 예제를 풀고 이해해보자. 다음은 팩토리얼을 재귀함수를 이용한 코드 풀이이다.

👉 팩토리얼 (Factorial) 재귀함수 코드

public class FactorialExample {
    public static int factorial(int n) {
        if (n == 1) return 1;  // 기저 조건 (Base Case)
        return n * factorial(n - 1);  // 재귀 호출
    }

    public static void main(String[] args) {
        System.out.println(factorial(5)); // 출력: 5! = 120
    }
}

위 코드를 시각화 하면 다음과 같다.

factorial(5)
→ 5 * factorial(4)
→ 5 * (4 * factorial(3))
→ 5 * (4 * (3 * factorial(2)))
→ 5 * (4 * (3 * (2 * factorial(1))))
→ 5 * 4 * 3 * 2 * 1 → 120

즉, 이렇게 반복되어 호출되는 것을 재귀호출이라고 한다. 하지만, 이보다 더 복잡한 코드에 쓰이는 재귀함수도 있다.

백준 2961번의 부분집합(Subset) 문제를 예를 들어보자. 이 문제의 재귀함수 부분 풀이는 다음과 같다.

👉 부분집합(Subset) 재귀함수 코드

🛠 예제: N = 3일 때 부분집합 구하는 과정 (select[i] 배열을 이용해 true(선택 O), false(선택 X)로 부분집합을 만든다.)

// 부분집합을 구하는 재귀 호출
void subset(int idx) {
    if (idx == N) {
        // 선택된 조합 출력
        return;
    }

    select[idx] = true;  // 선택 O
    subset(idx + 1);
    
    select[idx] = false; // 선택 X
    subset(idx + 1);
}

subset(0)
→ select[0] = true → subset(1)
  → select[1] = true → subset(2)
      → select[2] = true → subset(3) → [O O O] ✅
      → select[2] = false → subset(3) → [O O X] ✅
  → select[1] = false → subset(2)
      → select[2] = true → subset(3) → [O X O] ✅
      → select[2] = false → subset(3) → [O X X] ✅
  → select[0] = false → subset(1)
    → select[1] = true → subset(2)
      → select[2] = true → subset(3) → [X O O] ✅
      → select[2] = false → subset(3) → [X O X] ✅
    → select[1] = false → subset(2)
      → select[2] = true → subset(3) → [X X O] ✅
      → select[2] = false → subset(3) → [X X X] ✅

이렇게 모든 조합을 방문하는 것을 재귀함수라고 한다. 먼저 첫번째 재귀함수를 방문하고 모두 ture가 되면, 다음 재귀함수 코드로 이동해 하나씩 false를 만들어 조합하는 과정이다.

🚀 위 코드의 재귀 호출 흐름 다시 확인해보자!

1. select[0] = true부터 시작해서 끝까지 true를 채움
2. 그다음 false로 하나씩 변경하면서 모든 경우의 수 탐색

📌 핵심 흐름 요약

1. select[0] = true로 두고, 끝까지 내려가서 모두 true로 방문

2. select[2]부터 false로 바꿔 하나씩 조합 생성

3. select[1] = false로 변경하고 다시 select[2]를 true/false로 바꿔가며 조합

4. 마지막으로 select[0] = false로 변경 후, select[1], select[2] 조합을 반복

동기와 비동기는 호출하는 함수의 작업 완료를 기다리는지 여부의 차이가 있다.

• 동기 ) 함수 A가 동기로 함수 B를 호출하면, A는 B의 작업이 완료될 때까지 기다려야 함.
  ➡️ 작업이 순차적으로 진행 O
• 비동기 ) 함수 A가 비동기로 함수 B를 호출하면 A는 B의 작업의 완료를 신경 쓰지 않고 따로 동작 함.
  ➡️ 작업이 순차적으로 진행 X 

<관련 질문>

1. 블로킹과 동기는 어떤 차이가 있을까?

두 개념은 유사하면서도 다르다.

• 동기 호출 ) 호출된 함수가 완료할 때까지  호출한 함수가 기다림
  ➡️ 작업이 순차적으로 진행되는 것을 의미
• 블로킹 호출 ) 함수가 호출된 후, 호출한 함수의 결과를 기다리기 위해 실행을 멈추는 상태를 의미
  ➡️ 제어권이 반환되지 않고 대기하는 상황

2. 스프링에서 비동기 처리는 어떻게 하며 무엇을 주의해야 하는가?

스프링에서는 `@ASync` 어노테이션을 사용하여 비동기 처리를 수행한다.

주의점 )

1️⃣ 기본적으로 `@ASync`가 적용된 메서드에서 발생하는 예회는 호출자에게 전파되지 않음

      ➡️ 별도의 예외처리를 사용해야 함

2️⃣ `@ASync` 어노테이션은 프록시 기반으로 동작함

      ➡️ 같은 클래스 내부에서 직접 호출하는 경우 별도의 스레드에서 메서드가 실행 X

3️⃣ 비동기 메서드 내에서 생성한 트랜잭션은 상위 트랜잭션과 무관한 생명주기를 가짐.

프록시?

Proxy는 이름 그대로 대리자 역할을 한다. 즉, 클라이언트가 사용하려고 하는 실제 대상인 것처럼 위장해서 클라이언트의 요청을 받아주는 역할이다.

=> 프록시 패턴은 즉, 프록시 객체가 객체를 감싸서 클라이언트의 요청을 처리하게 하는 패턴이다. (접근제어, 부가 기능 추가 등의 이유로 사용)

프록시를 먼저 작성한 이유는 스프링 AOP(Aspect Oriented Programming)을 설명하기 위함이다. 스프링 AOP가 프록시 기반으로 동작하기 때문이다.

스프링 AOP는 관점 지향 프로그래밍이며 즉, 어떤 로직을 기준으로 '핵심 관점(핵심 비즈니스 로직)', '부가 관점(DB 연결, 로깅 등)'으로 나눠서 모듈화 하는 것을 뜻한다. *흩어진 관심사를 Aspect로 모듈화하고 핵심적인 비즈니스 로직에서 분리하여 재사용하겠다는 것이 AOP의 취지이다.

특징 )

1️⃣ 프록시 패턴 기반의 AOP 구현체, 프록시 객체를 쓰는 이유는 접근 데어 및 부가기능을 추가하기 위함

2️⃣ 스프링 빈에만 AOP를 적용

*흩어진 관심사: 소스 코드 상에서 반복적으로 사용되는 코드들 발견

Reference

[매일메일] https://www.maeil-mail.kr/question/77

https://kghworks.tistory.com/161

References

• https://yjg-lab.tistory.com/139 https://velog.io/@dayon_log/이진-탐색-트리
• https://yjg-lab.tistory.com/139