[알고리즘 2491] 발표자료

DP

• 동적 계획법
• 복잡하 문제를 더 작은 하위 문제로 나눠서 해결하는 알고리즘이다.
• 각 하위 문제의 결과를 저장하고 재사용 → 중복 계산을 피하는 해결법임

언제쓰노

• 최적 부분 구조
  • 문제의 최적 해결책이 부분 문제의 최적 해결책으로 구성되는 경우

    예를 들어

    A → D 로 가는 최단 경로가 필요한 데

    

    • 일단 A → B → D 가 최단이라는 가정하
    • B → D의 경로도 반드시 최단 경로여야함.

• 중복되는 부분 문제
  • 동일한 계산이 반복적으로 필요한 경우
• 메모이제이션이 필요한 경우
  • 계산 결과를 저장하고 재사용가능한 경우

코드 분석

static int[] UP;
static int[] DOWN;

• 증가 및 감소하는 부분수열에 대한 기록을 위하여

if (N == 1) {
    System.out.println(1);
    return;
}

• 한개면 생각할 필요도 없음. 걍 1

for (int i = 1; i < arr.size(); i++) {
    if (arr.get(i) >= arr.get(i - 1)) {
        UP[i] = UP[i - 1] + 1;
    } else {
        UP[i] = 1;
    }
    
    if (arr.get(i - 1) >= arr.get(i)) {
        DOWN[i] = DOWN[i - 1] + 1;
    } else {
        DOWN[i] = 1;
    }
    
    maxLen = Math.max(Math.max(UP[i], DOWN[i]), maxLen);
}