BOJ 25644. [Silver 5] 최대 상승

[hojongs]

Problem link

https://www.acmicpc.net/problem/25644

Problem abstraction

문제의 핵심을 요약한다. 체계적인 문제 접근을 위해, 문제를 추상화한다

적합한 자료구조를 생각한다

Design(Plan) algorithm

# 1

---
# 2

---
# 3

Algorithm idea

추상화한 문제 이해를 기반으로 알고리즘의 대략적인 구현 계획을 서술한다

Pseudo-code

idea를 수도 코드로 작성해본다

Validate algorithm

알고리즘의 유효 여부를 구현 전에 검증한다

예제 입력을 수도 코드로 계산해보고, 놓친 알고리즘 오류가 있는지 확인한다

Impl

import sys

readl = sys.stdin.readline


def f():
    readl()
    nums = [int(i) for i in readl().rstrip().split()]
    max_num = nums[-1]
    max_earning = 0
    for num in reversed(nums):
        if num > max_num:
            max_num = num
        else:
            max_earning = max(max_earning, max_num - num)
    print(max_earning)

f()

Self-feedback

Greedy approach 그림으로 설명
https://velog.io/@kohyeonseo1006/C-BOJ-25644-%EC%B5%9C%EB%8C%80-%EC%83%81%EC%8A%B9

DP solution
https://devteo77.tistory.com/11
https://msj725.tistory.com/119
https://gerbon.tistory.com/33

• DP 알고리즘을 구현 못 함
• 문제를 잘 읽자
• Greedy 알고리즘도 살질적으로 구현 못 함

구조적 접근: 문제를 추상화하여 구조적으로 접근했는가?

사고력: 알고리즘을 완전히 이해했는가? (충분한 사고력을 가졌는가?)

구현력: 알고리즘을 신속, 정확하게 구현했는가?

[hojongs]

새로운 문제를 풀지 말고, 풀었던 문제를 복습(review)하자