rhdtka21   1년 전

12865 평범한 배낭 문제 풀다가 알게된건데요

같은 N * K 2차원 리스트라도

행으로 긴것보다 열로 긴게 시간 복잡도에서 더 유리하네요...??


N(1 ≤ N ≤ 100)

K(1 ≤ K ≤ 100,000)

조건이 있는데


d = [[0 for _ in range(K+1)] for _ in range(N)] (채점번호 : 22494256)

d = [[0 for _ in range(N)] for _ in range(K+1)] (채점번호 : 22494224)

이 둘 차이때문에 시간이 꽤나 차이가 나서 정답 유무에 영향이 있더라구요

이중 for문을 돌때 바깥 for문이 크고 안쪽 for문이 작은거랑

바깥 for문이 작고 안쪽 for문이 큰거랑 차이가 있는건가요 

아니면 파이썬 리스트 구조상 차이가 있는건가요?

리스트 구조라서 열을 길게 늘이는게 더 유리해서 그런걸까요??

왜 그런건지 궁금합니다!!!


bupjae   1년 전

d = [[0 for _ in range(K+1)] for _ in range(N)] 는 list 객체가 총 N+1 개 생성되고

d = [[0 for _ in range(N)] for _ in range(K+1)] 는 list 객체가 총 K+2 개 생성됩니다.

프로그램에서 사용할 수 있는 공간의 수는 같지만, 내부적으로 새로운 객체를 만들 때 마다 필요한 연산이 있기 때문에

객체 생성 횟수는 적은 쪽이 유리합니다.

댓글을 작성하려면 로그인해야 합니다.