[TIL] 99클럽 코테 스터디 21일차 TIL + 오늘의 학습 키워드

* 오늘의 학습 키워드 : 동적 계획법(Dynamic Programming, DP)

 - 복잡한 문제를 간단한 하위 문제로 분할하고, 그 하위 문제들을 각각 풀어서 전체 문제의 해답을 구하는 알고리즘

• 핵심 개념
  
  1. 메모이제이션(Memoization) : 이미 계산한 하위 문제의 결과를 메모리에 저장하여 동일한 하위 문제가 다시 계산될 때 저장된 값을 재사용.
  2. 탑다운(Top - Dwon) 접근법 : 문제를 상위 문제에서 하위 문제로 재귀적으로 분할하면서 푸는 방식.
  3. 바텀업(Bottom - Up) 접근법 : 문제를 하위 문제부터 풀어나가면서 점진적으로 상위 문제의 해를 구하는 방식, 일반적으로 반복문을 사용하며, 결과를 저장하기 위해 테이블(배열)을 사용함.

---

* 예제 문제 : 피보나치 수열

 - 재귀적 접근법 : 동일한 계산이 여러 번 반복되기 때문에 비효율적

public int fibonacci(int n) {
	if(n <= 1) {
    	return n;
    }
    return fibonacci(n-1) + fibonacci(n-2);
}

 

 - 탑다운 접근법(메모이제이션) : 계산한 결과를 배열에 저장하여 중복 계산 피함.

public class Fibonacci{
	private int[] memo;
    
    public int fibonacci(int n){
    	memo = new int[n+1];
        return fibonacciMemo(n);
    }
    
    public int fibonacciMemo(int n) {
    	//n이 0 또는 1일 경우 그 값을 반환
        if(n <= 1) {
        	return n;
        }
        if(memo[n] != 0) {
        	return memo[n];
        }
        memo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
        return mem0[n];
    }
}

 

- 바텀업 접근법 : 작은 문제부터 차례대로 해결

public int fibonacci(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];
}​

---

* leetcode 1277. Count Square Submatrics with All Ones : https://leetcode.com/problems/count-square-submatrices-with-all-ones/description/

class Solution {
    public int countSquares(int[][] matrix) {
        //행의 수
        int m = matrix.length;
        //열의 수
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int totalSquares = 0;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == 1) {
                    if(i == 0 || j == 0) {
                        //첫 행이나 첫 열의 경우
                        dp[i][j] = 1;
                    } else{
                        //위, 왼쪽, 왼쪽 위 대각선 확인
                        dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
                    }
                    totalSquares += dp[i][j];
                }
            }
        }
        return totalSquares;
    }
}