NUA의 개발공부로그

동적계획법(DP)

• 상향식 접근
• 최하위 해답을 구하고, 해당 결과값을 이용해 상위 문제 해결
• Memoization 기법 사용 (이전 계산값 저장하는 기법)
• 문제를 쪼갤 때, 부분 문제 중복(재활용)  (ex> 피보나치 수열)

분할 정복 (divide & conquer) 

• 하향식 접근
• 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답 구함
• 재귀함수로 구현
• 문제를 쪼갤 때, 부분 문제 중복 X (ex> 병합 정렬, 퀵 정렬)
• Memoization 기법 사용 X

- 컴파일 에러(CE) : 문법 오류

- 시간 초과(TLE) : 최적화 필요

- 메모리 초과(MLE) : 최적화 필요

- 런타임 에러(RE) 

- 0으로 나누는 경우

- Container (ex>배열)에서 index 오류 (접근)

- 무한 루프 (TLE 일 수도 있음)

- 틀렸습니다 (WA)

1. 제한 및 대소 관계 (이상, 이하, 초과, 미만, min, max)

2. 예외처리 (ex>단, 없는 경우는 -1를 출력한다)

3. 입력과 출력 (공백, 양식, 순서, 정렬 유무)

4. 시간 제한과 메모리 제한

5. 알고리즘이 맞는가?

6. 생각한 로직대로 구현했나?

7. 불필요한 반복문이 있는가?

8. 중복을 처리했는가?