6일차 강의 (16 ~ 17강)

16강 (DP)

1. 테이블 정의하기

2. 점화식 찾기

3. 초기값 정의하기

초기값이 어디인지를 잘 생각해서 적용해주어야 함

구현이 짧은 편

 

D[i][j] (2차원으로 선언 하는 이유? , 지금까지 몇 개의 계단을 밟았는지에 대한 정보가 있어야 하므로)

직접적인 값 or 추상화(D[K][1])

 

관점을 달리 하면 또 다른 방식으로  DP식이 도출될 수 있음

 

2차원 배열을 잘 활용해서 여러 조건을 관리하기

 

DP에서의 경로추적

→ 값 테이블 이외에 경로 복원용 테이블을 하나 만들어서 관리

복원용 테이블의 INDEX를 타고가서 1에 도달할 때 까지 출력 후 종료

 

17강 (그리디)

지금 가장 최적인 답을 근시안적으로 택하는 알고리즘

= 관찰을 통해 탐색 범위를 줄이는 알고리즘

 

이상적인 풀이 흐름

1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.

2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다.

3. 구현해서 문제를 통과한다.

 

거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확실한다

→ 짜서 제출해보고 틀리면 빠르게 손절

 

100% 확신은 없지만 맞는 것 같은 그리디 풀이를 찾았다.

→ 일단은 넘어가고 다른 문제를 풀게 없거나 종료가 20~40분 남은 시점에 코딩 시작

 

잘 모르겠을 때는 최후의 방법으로 일단 정렬을 시켜놓고 이리저리 끼워맞춰보기

 

그리디로 될 것 같지만 반례가 존재해서 안되는 문제들 주의하기