[Coding Test][Python] 백준 2775번: 부녀회장이 될테야

문제

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

 

코드

rows = 15
cols = 15

# 아파트: 15x15의 2차원 배열, 0으로 초기화 
apt = [[0 for col in range(cols)] for row in range(rows)]

# Base Case - 0층, 1호 거주민 수 채우기
## 0층 
for i in range(1, 15):
    apt[0][i] = i 

## 0층~14층까지 1호에는 1명만 산다
for i in range(15):
    apt[i][1] = 1 
    
# 1~14층, 2~14호 까지 채우기
for i in range(1, 15):
    for j in range(2, 15):
        apt[i][j] = apt[i][j-1] + apt[i-1][j]

# 테스트
## 테스트 케이스 수
T = int(input()) 

## 풀이
for i in range(T):
    k = int(input()) # 층
    n = int(input()) # 호
    
    print(apt[k][n])

이 문제의 핵심은 특정 층, 특정 호수의 거주민 수를 구하기 위해 매번 아래층 사람들을 처음부터 다 더할 필요가 없다는 것이다.

표를 그려 규칙을 찾아보면 다음과 같은 점화식이 도출된다.

DP(k, n) = DP(k, n-1) + DP(k-1, n)

(현재 집 거주민 = 같은 층 옆집 거주민 + 아래층 같은 호수 거주민)

 

즉, 이전에 계산해 둔 결과를 저장해두고 필요할 때 꺼내 쓴다는 다이나믹 프로그래밍(DP)의 핵심 원리를 활용한 문제라고 할 수 있다.

(이는 서버에서 DB 조회를 줄이고 응답 속도를 높이기 위해 사용하는 Redis와 같은 캐시 시스템의 기본 철학과 동일하다.)

 

관점 1: 사전 연산

처음 코드를 작성할 때는 테스트 케이스 입력이 들어올 때마다 매번 거주민 수를 계산하도록 반복문을 설계하는 실수를 했다.

하지만 만약 T가 10만, 100만 건이라면 수십배의 트래픽이 순간적으로 발생했을 때 시스템은 무너진다.

 

따라서 요청이 올 때마다 무거운 계산을 수행해서는 안 된다고 판단했다.

아파트 거주민 수 조건처럼 '미리 정해져 있고 변하지 않는 데이터'는 트래픽(요청)을 받기 전에 미리 계산하여 메모리(배열)에 올려두고, 요청이 오면 배열의 인덱스로 접근해 O(1)의 속도로 즉시 응답(조회)하는 방식으로 아키텍처를 변경해야 한다. 

 

관점 2: Base Case 세팅

복잡한 점화식(비즈니스 로직)을 실행하기 전에 가장 선행되어야 할 작업은 0층과 모든 층의 1호라는 기본값을 배열에 정확히 세팅하는 것이었다.

결제 및 금융 서비스에서는 수많은 거래건을 수백가지 요구사항으로 계산해도 빠르게 오차없이 계산이 가능한 정산 시스템을 만드는 게 중요하다.

기초 데이터에 얕은 복사(Shallow Copy) 같은 결함이 발생하면 그 위에 쌓아 올린 좋은 로직도 결국 잘못된 결과(오차)를 뱉어내게 될 것이다. 따라서 파이썬의 list comprehension을 활용해 독립적이고 안전하게 2차원 배열의 밑그림을 그리는 것이 선행되어야 했다.