[Python] 2차원 리스트에서의 객체 생성

YUKI KIM·2022년 1월 9일

알고리즘

알고리즘 공부하면서

목록 보기

3/4

오늘 낮에 백준에서 1로 만들기 2 문제를 풀었다. 그런데 이 문제를 풀면서 느낀 것과 알게 된 것들을 정리하고 싶어 포스팅 남긴다. 혹여나 제가 틀린 개념은 마구마구 지적해주세요!

내가 풀어낸 코드

우선 이 문제는 dp 문제이다. X에서 1이 되려면 몇번 가야되는지 dp로 구하고, 그 경로를 역추적하는 문제이다.

1. 1차원 dp 역추적

import sys
input = sys.stdin.readline


def solution(X):
    dp = [0, 1, 1]   # dp[i]: (i + 1)이 1이 되려면 몇번?

    for i in range(3, X):
        dp.append(float('inf'))
        if (i + 1) % 3 == 0:
            dp[i] = min(dp[i // 3] + 1, dp[i])
        if (i + 1) % 2 == 0:
            dp[i] = min(dp[i // 2] + 1, dp[i])
        dp[i] = min(dp[i - 1] + 1, dp[i])

    OneToNum = dp[X - 1] - 1
    print(OneToNum + 1)

    while X != 0:
        if X % 3 == 0 and dp[(X // 3) - 1] == OneToNum:
            print(X, end=" ")
            X = X // 3
        elif X % 2 == 0 and dp[(X // 2) - 1] == OneToNum:
            print(X, end=" ")
            X = X // 2
        else:
            print(X, end=" ")
            X = X - 1
        OneToNum -= 1


if __name__ == '__main__':
    X = int(input())
    solution(X)

처음에 내가 푼 풀이는 위와 같다. OneToNum은 "X가 1이 되려면 몇번 가는지"이다. dp 배열을 먼저 구한 다음에 X부터 1까지 내림차순으로 OneToNum을 1씩 감소시키며 판별하는 방식이다.

이 코드는 통과는 되지만 해당 문제는 N의 범위가 큰 문제이므로 위와 같이 반복문을 2번 돌리는 방식은 비효율적이라 생각하고 풀이를 수정하였다.

2. dp에 경로 저장하기

import sys
input = sys.stdin.readline


def solution(X):
    dp = [[0, []] for _ in range(X + 1)]  # [i][0]에는 몇번, [i][1]에는 경로
    dp[1][0] = 0 
    dp[1][1] = [1]

    for i in range(2, X + 1):
        dp[i][0] = dp[i - 1][0] + 1
        dp[i][1] = dp[i - 1][1] + [i]
        if i % 3 == 0 and dp[i // 3][0] + 1 < dp[i][0]:
            dp[i][0] = dp[i // 3][0] + 1
            dp[i][1] = dp[i // 3][1] + [i]
        if i % 2 == 0 and dp[i // 2][0] + 1 < dp[i][0]:
            dp[i][0] = dp[i // 2][0] + 1
            dp[i][1] = dp[i // 2][1] + [i]

    print(dp[X][0])
    print(*reversed(dp[X][1]))


if __name__ == '__main__':
    X = int(input())
    solution(X)

코드가 훨씬 간결해졌다. (x//3) 혹은 (x//2)로 가는 것이 (x-1)로 가는 것보다 더 빠른 방식이며, (x//3) 혹은 (x//2)로 못가면 무조건 (x-1)로 가야 하기 때문에 dp에 우선 (x-1)의 경우를 저장해주고 (x//3)과 (x//2) 둘 중 작은 것을 더한다.

그리고 1 풀이와 비교해보면 dp가 2차원 리스트인데, dp[i][1]에는 경로를 저장해준다. 그렇다면, 이 방식이 1보다 최적화된 방식이라 할 수 있는가?

두 풀이 비교하기

그렇다면, 이 방식이 1보다 최적화된 방식이라 할 수 있는가?

앞 절에서 이런 질문을 했다. 나의 답은 "아니요!" 이다. 실제로 백준에서의 소요된 시간을 보면 1번 풀이보다 2번 풀이의 시간이 2배 더 많이 소요된다.

사실 for문을 1번 돌리든, 2번 돌리든, 결국에 시간 복잡도는 O(N)이 소요된다. 이 두 풀이의 시간을 결정하는 것은 dp 배열의 생성에 있다.

파이썬의 2차원 리스트

dp1 = [0 for _ in range(X + 1)]         # 1번 풀이 dp
dp2 = [[0, []] for _ in range(X + 1)]   # 2번 풀이 dp

편의상 1번 풀이 dp를 dp1, 2번 풀이 dp를 dp2라고 하겠다. dp1은 내부적으로 객체 생성을 단 한 번만 하지만 dp2는 객체 생성을 (X+1)번 하게 된다. 따라서 파이썬 내부에서 객체 생성에 필요한 시간이 소요되기 때문에 객체 생성을 덜 하는 1번 풀이가 시간 측면에서 더 빠르다.