인프런 커뮤니티 질문&답변
작성한 질문수
2133번 문제풀이 관련 질문
해결된 질문
작성
·
37
1
안녕하세요 선생님. 이전 두 질문에 대한 답변이 많은 도움이 되었습니다. 감사합니다.
2133번 문제의 DP 1번 풀이에서 O(N^2) 풀이를 소개해주셨는데 아래와 같이 dp 테이블을 갱신할 때 sum_dp 테이블을 같이 갱신을 해주면 시간복잡도가 O(N)으로 줄일 수 있지 않나 싶어 질문드립니다.
N = int(input())
if N % 2 != 0:
print(0)
else:
n = N//2
dp = [1] * (n+1)
sum_dp = [1] * (n+1)
for i in range(1,n+1):
dp[i] = sum_dp[i-1] * 2 + dp[i-1]
sum_dp[i] = sum_dp[i-1] + dp[i]
print(dp[-1])
그리고 이건 다른 종류의 질문인데 혹시 그래프 부분이 실제로 코테에 많이 등장하나요? 제가 조금 급하게 준비하고 있는 상태라 이론을 필수 알고리즘2까지만 들어도 될지 아니면 그래프까지 다 들어야될지 고민중입니다. 조언 주시면 감사하겠습니다!
답변 1
1
알리 Ally
지식공유자
안녕하세요, 최재원님!
[BOJ 2133 풀이1 최적화에 대한 질문]
말씀하신 것처럼 누적합을 활용하면 풀이 1의 시간 복잡도를 O(N)으로 줄일 수 있습니다.
누적합을 활용하여 풀이1을 작성해보면 아래와 같이 나타낼 수 있겠네요.
# solve
dp = [0] * 31
dp[0] = 1
psum = [0] * 31
psum[0] = 1
for n in range(2, 31, 2):
dp[n] = dp[n - 2] * 3
if n - 4 >= 0:
dp[n] += 2 * psum[n - 4]
psum[n] = psum[n - 2] + dp[n]
# input
N = int(input())
print(dp[N])
[효율적인 코딩테스트 단기 공부법에 대한 질문]
코딩테스트에 나오는 빈도수로 따지면, 필수 알고리즘1 > 그래프 알고리즘 > 필수 알고리즘2 로 나타낼 수 있겠네요. 따라서 필수 알고리즘1을 다 들으셨다면, 그래프 알고리즘을 먼저 들으시는 것을 추천드립니다!
또 궁금하신 점 있으시면 질문해주세요. :)