[Do it! 알고리즘 코딩 테스트 자바] 6주차 기록. 동적 계획법(DP)

벌써 스터디 마지막 주차인 6주차다.

이번 주차는 코테의 꽃이라고도 할 수 있는 동적 계획법이다.

아마 가장 중요하고 출제 빈도가 높은 문제지 않을까 싶다.

 

---

[26일차]

[동적 계획법] Dynamic Programming

: 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법

 

- 핵심 이론?

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 함.
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용.
   → 이를 메모이제이션(Memoization)기법이라 함.
4. 동적 계획법은 탑-다운(Top-Down)과 바텀 업(Bottom-Up)방식으로 구현 가능.

예시로 '피보나치 수열'로 설명

피보나치 공식 : D[N] = D[N - 1] + D[N - 2]    →    N번째 수열 = N - 1번째 수열 + N - 2번째 수열

 

예로 6번째 피보나치 수열은 5번째 수열과 4번째 수열의 합이다.
즉, 6번 째 수열 문제는 5번째 수열과 4번째 수열 구하는 작은 문제로 나눌 수 있다.

 

*점화식
점화식을 세울 때는 전체 문제를 논리적으로 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 게 중요.

피보나치에서는 공식 자체가 점화식이므로 점화식으로 바로 사용.

 

*메모이제이션 원리

메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고, 다음에 같은 문제가 나왔을 때 재계산하지 않고
DP 테이블의 값을 이용하는 것을 말함.

 

즉, 6번째 피보나치를 구할 때 5번 피보나치, 4번 피보나치가 필요하고,
5번째 피보나치를 구할 때 4번 피보나치, 3번 피보나치가 필요하므로,
5번을 구하면서 4번이 구해지므로, 6번째 피보나치는 5번과 4번을 다시 구할 필요없이 이미 구해진 값이 저장돼있는
DP 테이블에서 읽어오기만 하면 된다는 뜻이다. ( O(1) )

 

- 구현 방식의 차이

구현 방식은 말했듯, 탑-다운과 바텀-업 방식이 있고 접근 방식이 다르므로 각각의 특징을 이해하자.
[1] 탑-다운 방식

: 탑-다운 방식은 위에서부터 문제를 파악해 내려오는 방식이다. 주로 재귀 함수 형태로 코드를 구현한다.

→ 코드의 가독성이 좋고, 이해하기가 편하다는 장점

public class P2747_피보나치수_TopDown {
	static int[] D;
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        D = new int[n + 1];
        
        for (int i = 0; i <= n; i++) {
        	D[i] = -1;
        }
        D[0] = 0;
        D[1] = 1;
        fibo(n);
        System.out.println(D[n]);
   	}
    
    staitc int fibo(int n) {
    	if (D[n] != -1)
        	return D[n];
        return D[n] = fibo(n-2) + fibo(n-1);
    }
}

 

fibo 함수와 같이 먼저 가장 큰 문제인 n번째 피보나치 수열을 호출하면서 시작하게 되고,

그 수를 구하기 위해 n-2, n-1의 수열을 다시 호출한다. 그렇게 계속 계속 재귀적으로 호출을 하다보면 
DP 테이블에 정답이 구해져 있는 D[0], D[1] 까지 가게 되고, 그 지점 부터 답을 구해 저장해나가면서 다시 큰 문제로 돌아간다.

재연산을 방지하기 위해 if절로 D[n] != -1 → -1이 아니면 (값이 저장돼있다면) DP 테이블 값을 바로 사용해서 반환한다.

 

[2] 바텀-업 방식

: 바텀-업 방식을 작은 부분 문제부터 해결하면서 점점 큰 문제로 확장해 나가는 방식이다. 주로 반복문 형태로 구현한다.

public class P2757_피보나치수_BottomUp {
	static int[] D;
    public static void main(String args[]) {
    	Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        D = new int[n + 1];
        
        for (int i = 0; i <= n; i++) {
        	D[i] = -1;
        }
        
        D[0] = 0;
        D[1] = 1;
        
        for (int i = 2; i <= n; i++) {
        	D[i] = D[i-1] + D[i-2];
        }
        
        System.out.println(D[n]);
   	}
}

 

이 방식의 특징은, DP 테이블을 생성한 후, 2번째 피보나치 수열부터 바로 D[0], D[1]를 이용해서 구해버린다.

즉 바로 현재 만들 수 있는 DP테이블의 값을 바로 저장해나가는 방식이므로, DP 테이블을 모두 채운 후에는 원하는 수열 번호를
통해 바로 답을 구할 수 있다.

 

*두 방식 중에서는 바텀-업 방식이 좀 더 안전한 방식이다. 탑-다운 방식은 재귀 함수 형태로 구현되기 때문에 재귀의 깊이가 매우 깊어질 경우에 런타임 에러가 발생할 수 있다. (재귀 깊이 제한) 

하지만 실제 코딩 테스트에서는 깊이까지 고려해야할 만한 문제가 잘 나오지는 않는다.

편한 방식 채택해서 사용하면 됨!! 하지만 두 방식 차이는 알고 있을 것.!!!!!!!

 

 

- 예제 문제

1. 백준 1463번 : 정수를 1로 만들기 (실버 3)
2. 백준 14501번 : 퇴사 준비하기 (실버 3)
3. 백준 2193번 : 이친수 구하기 (실버 3)
4. 백준 11726번 : 2*N 타일 채우기 (실버 3)

---

[27일차]

[DP 문제 풀이]

 

1. 백준 10844번 : 계단 수 구하기 (실버 1)
2. 백준 13398번 : 연속된 정수의 합 구하기 (골드 5)
3. 백준 9252번 : 최장 공통 부분 수열 찾기 (골드 4)

---

[28일차]

[DP 문제 풀이]

 

1. 백준 1915번 : 가장 큰 정사각형 찾기 (골드 4)
2. 백준 1328번 : 빌딩 순서 구하기 (골드 1)
3. 백준 2342번 : DDR을 해보자 (골드 3)

---

[29일차]

[DP 문제 풀이]

 

1. 백준 11049번 : 행렬 곱 연산 횟수의 최솟값 구하기 (골드 3)
2. 백준 2098번 : 외판원의 순회 경로 짜기 (골드 1)
3. 백준 14003번 : 가장 길게증가하는 부분 수열 찾기 (플래티넘) 

---

[30일차]

[기하] CCW

: CCW는 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘

수학적으로는 벡터의 외적과 관련된 이해가 필요하지만 CCW의 공식과 결괏값에 관련된 해석 부분을 집중적으로 다루며

코딩 테스트에 집중하겠다.

 

세 점을 A(X1, Y1), B(X2, Y2), C(X3, Y3)라고 가정했을 때, CCW 공식은 다음과 같다.

 

 CCW = (X1Y2 + X2Y3 + X3Y1) - (X2Y1 + X3Y2 + X1Y3)

 

- CCW 공식 도출 과정?

1) 1번째 점을 뒤에 한 번 더 쓴다.

2) 오른쪽 아래 방향 화살표 곱은 더하고, 왼쪽 아래 방향 화살표 곱은 뺀다.

→ 이렇게 세 점이 주어졌을 때 CCW 공식을 사용해 세 점에 관한 다양한 관계를 도출할 수 있다. 

 

# CCW 공식은 기하에서 가장 기본이 되므로 코드 자체를 암기해 외워두는 것이 좋음.

 

- CCW 수행한 결괏값이 어떤 의미를 지니는지?

 

방향에 따른 CCW의 결과

 

이 부호와 별개로 CCW 결과의 절댓값은 세 점으로 이뤄진 두 벡터의 외적값을 나타내고,

이것은 CCW의 절댓값을 절반으로 나누면 세 점으로 이뤄진 삼각형의 넓이를 나타낸다는 뜻.

→ 즉, |CCW 결괏값| / 2 는 세 점으로 이뤄진 삼각형의 넓이로 이해하면 됨.

 

- 예제 문제

 

1. 백준 11758번 : 선분 방향 구하기 (골드 5)
2. 백준 17387번 : 선분의 교차 여부 구하기 (골드 2)
3. 백준 2162번 : 선분을 그룹으로 나누기 (플래티넘)
4. 백준 2166번 : 다각형의 넓이 구하기 (골드 5)

---

 

주간 회고록

• 이번 주에 코테를 한 번 응시해본 결과, 처참한 결과에 다시 차근차근 문제 풀면서 익혀 나가야겠다..
• DP 문제는 많이 풀어보기.