문제
https://www.acmicpc.net/problem/2775
사용 언어
Python3
풀이 과정
재귀로 풀었고 IDE에서는 정답이 출력되는 것을 확인했으나 백준에서는 시간 초과가 떴다.
import sys
t = int(sys.stdin.readline()) # Text case의 수 , 2
j = 0
result = []
def people(a, b):# 몇 층이든 b호까지밖에 없음
total = 0
if (a == 0): # 0층의 b호에는
total = b # 총 b명이 산다
else: # 1층부터는 재귀
for i in range(0, b+1):
total += people(a-1, i) # people(a-1, 0) + people(a-1, 1) + ~ + people(a-1, b)
return total
while (j < t):
floor = int(sys.stdin.readline())
ho = int(sys.stdin.readline())
result.append(people(floor, ho))
j += 1
print(*result, sep='\n') # 결과 리스트 한 줄씩 출력
한 번 계산한 값을 저장해 (메모리를 더 사용하는 대신) 호출 횟수(시간)를 줄이고 싶어서 구글링했고 결과적으로 Memoizatoin 방식을 적용해 코드를 수정했다.
눈 깜짝할 사이에 채점하더니 뜬 맞았습니다!!
키야 이 맛에 코딩하지~
그냥 다른 사람의 풀이를 검색해보고 싶은 마음을 꾹 참았는데 혼자 풀어보길 잘한 것 같다.
앞으로 재귀 함수를 사용할 때에는 처음부터 Memoization 방식을 꼭 적용해야겠다.
찾아보니 Memoization은 dynamic programming(동적 계획법) 문제를 풀 때 흔히 쓰이는 방법인데 동적 계획법 문제를 풀기 위한 더 깔끔하고 효율적인 방법은 Bottom-up이라고 한다. 또 공부해야지...
제출 답안
import sys
t = int(sys.stdin.readline()) # Text case의 수
j = 0
memo = {} #(0, 1):1, (0, 2):2, ... }
result = []
def people(a, b):# 몇 층이든 b호까지밖에 없음
total = 0
global memo
if (a == 0): # 0층의 b호
memo[(a, b)] = b # 저장
return b
elif (a, b) in memo: # 0층이 아닌데 memo에 있으면
return memo[(a, b)]
# memo에 없는 값이면 계산하기
for i in range(0, b+1):
total += people(a-1, i) # people(a-1, 0) + people(a-1, 1) + ~ + people(a-1, b)
memo[(a, b)] = total # 저장
return total
while (j < t): # t번 입력받고 결괏값 리스트에 저장
floor = int(sys.stdin.readline())
ho = int(sys.stdin.readline())
result.append(people(floor, ho))
j += 1
#print(memo)
print(*result, sep='\n') # 결과 리스트 한 줄씩 출력
공부한 내용
전역 변수와 지역 변수
전역 변수를 함수 안에서 지역 변수와 함께 사용하고 싶을 경우
global 변수명
으로 호출하고 새로운 값을 할당해 사용할 수 있다. 이 때 global 변수명 = 새로운 값으로 한 줄에 작성하는 것은 안 된다.
출처: http://www.tcpschool.com/python2018/python_function_scope
딕셔너리
리스트와 비슷하지만, 딕셔너리는 항목의 순서를 따르지 않으며 offset으로 항목을 선택할 수 없다. 대신 key로 해당 값을 접근할 수 있다.
key는 대부분 문자열로 사용되지만, 다른 불변하는 타입(bool, int, float, tuple, string, ...)이 될 수도 있다.
딕셔너리는 변경 가능하므로 키-값 요소를 추가, 삭제, 수정 할 수 있다.
딕셔너리에 특정 키가 존재하는지 확인할 때 in을 사용하고 True나 False로 반환된다.
dictVariable = {'a':1, 'b':2, 'c':3, 'd':4}
print(dictVariable) # {'a': 1, 'b': 2, 'c': 3, 'd': 4}
check = 'c' in dictVariable
print(check) # True
출처: https://wikidocs.net/16 | https://www.byfuls.com/programming/read?id=30
재귀 함수의 호출 횟수를 줄여보자
재귀함수는 알고리즘을 간단히 축약할 수 있다는 장점이 있지만, 스택 오버 플로어 문제와 런타임이 비교적 오래 걸린다는 단점이 있다. 따라서 알고리즘 시간을 줄일 수 있는 Memoization과 Tubulation을 학습했다. 이 두 개는 메모리를 더 사용하는 대신, 계산 시간을 줄인다. 예시 코드는 출처를 참고한다.
- Memoization : 주어진 입력값에 대한 결과를 저장함으로써 같은 입력값에 대해 함수가 한 번만 실행되는 것을 보장.
보통 배열이나 딕셔너리에 저장해놓고, 필요할 때 참조하여 이용. 오버헤드는 발생하지 않으며 런타임 시간은 줄고, 메모리 사용은 증가한다는 특징이 있음
- Tabulation : Memoiation과 동일하게 함수 중복을 줄여주는 방식이며 런타임이 줄고, 메모리 사용이 증가. 다른 점은 미리 결괏값을 계산해 다 배열에 저장해두기 때문에 오버헤드가 발생할 수 있음
* 오버헤드는 제어프로그램이 시스템 지원을 위해 대기하는 시간
출처: https://blog.naver.com/PostView.naver?blogId=haran3056&logNo=222298085248&categoryNo=1&parentCategoryNo=0
Unpacking Operator *
마지막에 for문을 사용하지 않고 리스트를 한 줄씩 출력하고 싶어 찾아보니 역시 파이썬은 방법이 있었다. 정확히는 Packing과 Unpacking의 개념을 알아야 해서 간단하게 공부했고, 내가 원했던 방식은 다음과 같이 적용하면 된다.
list = [1,2,3,4,5]
print(*list, sep='\n')
'''
1
2
3
4
5
'''
위와 같이 함수에서 Unpacking을 할 때는, 매개변수에서 *을 붙이는게 아니라 인자 앞에 *을 붙여서 사용한다.
참고로 리스트를 Unpacking하여 그대로 출력하기 때문에 기본적으로 개행이 없이 한 줄로 출력된다. 저번에 공부한 파이썬 print 함수의 강제 개행(end='\n')이 적용되지 않는 것이다.
따라서 개행을 원한다면 sep='\n'을 덧붙여주도록 한다.
출처: https://wikidocs.net/22801
'코딩 테스트 스터디 > 백준' 카테고리의 다른 글
[브론즈 III] 3009번. 네 번째 점 (0) | 2022.02.04 |
---|---|
[브론즈 II] 14561번. 회문 (0) | 2022.02.03 |
[브론즈 II] 2577번. 숫자의 개수 (0) | 2022.01.31 |
[실버 IV] 9012번. 괄호 (0) | 2022.01.26 |
[브론즈 II] 10809번. 알파벳 찾기 (0) | 2022.01.26 |