2133번 문제풀이 관련 질문

Question

안녕하세요 선생님. 이전 두 질문에 대한 답변이 많은 도움이 되었습니다. 감사합니다. 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까지만 들어도 될지 아니면 그래프까지 다 들어야될지 고민중입니다. 조언 주시면 감사하겠습니다!

알리 Ally · Answer

안녕하세요, 최재원님!   [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 을 다 들으셨다면, 그래프 알고리즘 을 먼저 들으시는 것을 추천드립니다!   또 궁금하신 점 있으시면 질문해주세요. :)