BOJ 9465. [Silver1] 스티커

[hojongs]

Problem link

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

Problem abstraction

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

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

최적화 문제
왼쪽부터 순차적으로 접근하면 i번째 열에 대해 3가지 경우가 있음

• 위 스티커 선택
• 아래 스티커 선택
• 선택하지 않음

그리고 완전 탐색 시 중간 연산에서 중복 계산이 발생함 e.g. UP=0, DOWN=1, NONE=2라고 하자 0열 0 -> 1열 1 -> 2열 0 -> ... 0열 0 -> 1열 2 -> 2열 0 -> 이후 중복

중복 계산을 피하기 위해 DP 알고리즘 사용

i번째 열에서 3개의 경우에 대해 최대값을 저장함

cache[i][UP | DOWN | NONE] = max_value of i번째 행에서 3가지 중 특정 경우에 대해 이후 행들의 최대값

DP

DP는 두 종류가 있다

• memoization(Top-down): 전체 문제에서 시작하여, 서브 문제를 만날 때마다 연산 결과를 저장한다.
• tabulazation(Bottom-up): 모든 서브 문제를 탐색하며 모든 연산 결과들을 미리 저장해놓는다. 그 후에 전체 문제를 풀이한다.

Design(Plan) algorithm

# 1

---
# 2

---
# 3

Algorithm idea

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

DP memoization

recursion (DFS)

iteration으로는 memoization을 구현하기 어려워보임

Pseudo-code

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

Validate algorithm

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

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

(아래부터)

recursion depth limit

Python(Pypy) default recursion depth limit은 1,000이다 (ref)

알고리즘 및 문제 제한의 recursion max depth는 약 100,000이므로 런타임 에러 발생

메모리 초과 (256 MB)

As-is: 길이 3의 list 객체 100,000개 -> memory fragmentation 의심
To-be: 길이 100,000의 list 객체 3개로 수정 -> 여전히 메모리 초과

As-is: 디버깅용 id 파라미터가 있었음
To-be: 파라미터를 제거함 -> 메모리 초과 해결됨

4B 객체를 100,000회 recursion 호출하면 400KB 정도임.

Python v3.11.3 에서 sys.getsizeof(1) 을 호출해보면 int 객체의 size가 실제로는 28B임을 알 수 있음. 2.8MB 정도.
PyPy 환경에서는 다를 수 있음

틀렸습니다

cache에 저장할 값의 정의를 잘못 생각함. (알고리즘 설계 시 명확히 정의해야 함)

현재까지의 점수를 cache에 더하고 있었음. cache에 저장할 값은 아래와 같이 정의되야 함.

cache[i][UP | DOWN | NONE] = max_value of i번째 행에서 3가지 중 특정 경우에 대해 이후 행들의 최대값

메모리 초과 (2)

또다시 메모리 초과 발생. 재귀 호출로 풀 수 없는 문제일지도 (stack frame이 메모리를 얼마나 차지하는지 모름)

https://www.acmicpc.net/board/view/49246

iteration, tabulation 알고리즘으로 변경

Impl

import sys

readl = sys.stdin.readline

UP, DOWN, NONE = 0, 1, 2


def f():
    cache = [[0] * 100_000 for _ in range(3)]
    row_len = int(readl())
    rows = [[int(i) for i in readl().split()] for _ in range(2)]

    cache[UP][0] = rows[UP][0]
    cache[DOWN][0] = rows[DOWN][0]
    for i in range(1, row_len):
        cache[UP][i] = max(cache[DOWN][i - 1], cache[NONE][i - 1]) + rows[UP][i]
        cache[DOWN][i] = max(cache[UP][i - 1], cache[NONE][i - 1]) + rows[DOWN][i]
        cache[NONE][i] = max(
            cache[UP][i - 1],
            cache[DOWN][i - 1],
            cache[NONE][i - 1],
        )

    print(
        max(
            cache[UP][row_len - 1],
            cache[DOWN][row_len - 1],
            cache[NONE][row_len - 1],
        )
    )


t = int(readl())
for _ in range(t):
    f()

Self-feedback

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

하나가 아니라 여러 가지 알고리즘 아이디어들을 생각해보자

알고리즘 풀 때 그림도 그려보자 (DP)

cache(mem)에 저장할 값의 명확한 정의까지 포함하여, 수도 코드를 작성해본 후 구현하자

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

이것도 좀 부족했던 듯

Silver1인데 몇 시간동안 풀었음. 어려운 문제였음

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