📌 문제 : 백준 2775번
📌 문제 탐색하기
T : 테스트 케이스 수
k : 살고 있는 층 수 (1 ≤ k ≤ 14)
n : 살고 있는 호 수 (1 ≤ n ≤ 14)
✅ 입력 조건
1.T입력
2.k입력
3.n입력
✅ 출력 조건
1.T만큼 해당 집 거주민 수 출력
아파트는 0층부터, 각 층엔 1호부터 존재하며 0층의 i호엔 i명이 산다.
즉, 0층엔 입력받은 n에 따라 거주민 수가 정해져 있다고 생각할 수 있다.
아파트 a층 b호 거주 조건은 다음과 같다.
a-1층의1호부터b호까지 사람들의 수의 합 만큼의 거주민 필요
0.5초의 시간 제한 내에 계산하기 위해 재귀함수 대신 DP를 활용한다.
k = 0인 경우, n호에 사는 사람은 n명,
n = 1인 경우, 모두 1명이 산다.
조건을 기반으로 k층의 n호에 사는 사람의 수를 점화식을 세우면 다음과 같다.
초기 값은 이다.
이를 적용해 DP 테이블을 채워 원하는 값을 찾는다.
가능한 시간복잡도
T만큼 반복 →
dp 테이블 생성 →
dp 테이블 채우기 →
최종 시간복잡도
으로 제한 시간 내에 연산이 가능하다.
알고리즘 선택
전체 범위의 거주민 수를 점화식을 통해 계산하여 dp 테이블에 저장
📌 코드 설계하기
- T 입력
- T만큼 k, n을 한 줄씩 입력
- dp 테이블 초기화
- dp 테이블 채우기
- 원하는 형식으로 출력
📌 시도 회차 수정 사항
1회차
# 3. dp 테이블 초기화
dp = [[0] * 15] * 15- 결과
- dp 테이블 초기화를 위해 위와 같이 정의했는데, 이와 같이 Python에서 리스트를 곱하게 되면 객체의 참조가 복사된다고 한다. 따라서 모든 행이 같은 리스트를 가리키는 것이다.
- 그로인해 이후 dp 테이블을 채울 때,
dp[0][0]을 변경하면 다른 리스트dp[0][1],dp[0][2], ...등 모두 똑같이 변경되어 원하는 값이 계산되지 않았다.
# 3. dp 테이블 초기화
dp = [[0] * 15 for _ in range(15)]- 이와 같이 리스트 컴프리헨션을 활용해 각 행을 독립적인 리스트로 만들어줌으로써 해결했다.
📌 정답 코드
import sys
input = sys.stdin.readline
# 1. T 입력
T = int(input())
# 2. T만큼 k, n을 한 줄씩 입력
for _ in range(T):
k = int(input())
n = int(input())
# 3. dp 테이블 초기화
dp = [[0] * 15 for _ in range(15)]
# 4. dp 테이블 채우기
# 4-1. 0층 채우기
for i in range(1, 15):
dp[0][i] = i
# 4-2. k층의 1호 채우기
for i in range(1, 15):
dp[i][1] = 1
# 4-3. 점화식에 따라 채우기
for x in range(1, 15):
for y in range(2, 15):
dp[x][y] = dp[x][y-1] + dp[x-1][y]
# 5. 원하는 형식으로 출력
print(dp[k][n])- 결과
다른 풀이
import sys
input = sys.stdin.readline
# 1. 모든 층의 모든 호 거주민 수 저장할 리스트
# 0층 거주민 수 저장
li = [[1,2,3,4,5,6,7,8,9,10,11,12,13,14]]
# 2. 모든 층의 모든 호 거주민 수 계산
for i in range(1, 15):
for j in range(14):
# 인덱스 0을 1호로 생각해 1 채우기
if j == 0:
li.append([1])
continue
# 리스트 채우기
li[i].append(li[i-1][j] + li[i][j-1])
# 3. T 입력
T = int(input())
# 4. k, n 입력
for i in range(T):
k = int(input())
n = int(input())
# 5. 원하는 형식으로 출력 (1호를 인덱스 0으로 했으므로 n-1로 접근)
print(li[k][n-1])- 결과
- 유사하지만 dp 테이블 값을 변경하는 것이 아니라 계산해
append하는 방식이다.
📌 회고
- 이전 dp 문제도 초기화 부분에서 틀렸었는데 이번에도 그런 것을 보니, dp 알고리즘을 사용할 때 나에게 가장 어려운 부분인 것 같다. 많이 연습해야겠다.
- 리스트 연산의 특성에 대해 찾아보다가
깊은 복사,얕은 복사에 대한 정리의 필요성을 느꼈다.
📌 기억할 정보
리스트 복사 시 얕은 복사(Shallow Copy)
- 문제: 얕은 복사는 새로운 리스트를 생성하지만, 리스트 내의 객체들은 원래 리스트의 객체들을 참조
original = [[0] * 5] * 3 original[0][0] = 1 print(original) # [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]
깊은 복사(Deep Copy)
- 문제 해결: 새로운 리스트와 내부 객체들까지 모두 복사하려면 깊은 복사 사용해야 함
import copy original = [[0] * 5 for _ in range(3)] copied = copy.deepcopy(original) copied[0][0] = 1 print(original) # [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
변수 할당 시 객체 참조
- 문제: 변수에 리스트 할당하면, 변수는 리스트 객체 참조
a = [1, 2, 3] b = a b[0] = 100 print(a) # [100, 2, 3]
슬라이싱을 이용한 복사
- 특징: 슬라이싱을 이용한 복사는 얕은 복사
original = [1, 2, 3, 4] copied = original[:] copied[0] = 100 print(original) # [1, 2, 3, 4]
리스트 내포를 이용한 초기화
- 특징: 리스트 내포 이용 → 독립적인 객체들 생성됨
grid = [[0] * 5 for _ in range(3)] grid[0][0] = 1 print(grid) # [[1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
copy 모듈을 이용한 복사
- 얕은 복사:
copy.copy()import copy original = [1, 2, [3, 4]] shallow_copy = copy.copy(original) shallow_copy[2][0] = 100 print(original) # [1, 2, [100, 4]] - 깊은 복사:
copy.deepcopy()import copy original = [1, 2, [3, 4]] deep_copy = copy.deepcopy(original) deep_copy[2][0] = 100 print(original) # [1, 2, [3, 4]]
파이썬의 객체 참조와 메모리 관리
- 참조 카운트: 파이썬은 참조 카운트를 사용하여 객체의 메모리 관리 → 여러 변수가 동일한 객체를 참조 가능
import sys a = [1, 2, 3] b = a print(sys.getrefcount(a)) # 출력 값은 플랫폼에 따라 다를 수 있음
id() 함수
- 특징:
id()함수 사용하여 객체의 고유 식별자 확인 가능 → 동일한 객체를 참조하는지 확인할 때 사용a = [1, 2, 3] b = a print(id(a) == id(b)) # True
깊은 복사 vs 얕은 복사
- 얕은 복사
- 객체의 최상의 레벨의 요소들만 복사, 하위 레벨 요소들은 원래 객체와 참조 공유
- 복사된 객체에서 최상의 요소 변경 시 원본 객체에 영향 ❌, 하위 레벨 변경 시 영향 ⭕️
- 원본 객체와 복사된 객체가 일부 요소를 공유 → 공유된 요소를 변경하면 서로 영향을 미치게 됨
- 깊은 복사
- 객체와 그 하위 레벨의 모든 요소들까지 완전히 복사 → 별개의 객체
- 원본 객체와 복사된 객체가 완전히 독립적 → 변경해도 서로 영향을 주지 않음
