이기 웨 1000ms나 차이나는거야

코딩 채널

알림 알림 중 알림 취소

구독자 4411명 알림수신 85명 @은월영

프로그래밍 및 코딩 채널

질문 이기 웨 1000ms나 차이나는거야

감자가좋아

추천 0 비추천 0 댓글 6 조회수 176 작성일 2023-03-14 05:12:35

⚠️ 이 게시물은 작성자가 삭제할 수 없도록 설정되어 있습니다.

https://arca.live/b/programmer/71777630

LCS(최장 공통부분 수열) 문제임.

이게 1000ms

이게 시간초과( 제한시간 2000ms )

파이썬 list는 참조값의 나열 아니였어? 접근 시간 O(1)로 알고 있었는데 저거 단 두번 들어갓다고 시간이 터져부리냐.

댓글 [6] 글쓰기

KamaPytorq

2023-03-14 06:25:21 답글

https://stackoverflow.com/questions/11400163/python-list-indexing-efficiency
음수 인덱싱은 CPython 내부에서 그 길이를 구하고, 거기에 더하는 식으로 구현 되어있다고 하는것 같음
그래서 len(LCS[-1][-1]) 요 부분에서 O(A * B * 문자열길이) 만큼 시간이 걸릴듯?
어떻게 최적화가 들어간다면 달라질지도 모르겠지만 아마 저래서 시간초과 뜨는 걸지도

Stack Overflow

Python List Indexing Efficiency

Quick question about the built in python list object. Say you have a list with the numbers 0 - 99. You are writing a program that takes the last item in the list and uses it for some other purpos...

음수 인덱싱은 CPython 내부에서 그 길이를 구하고, 거기에 더하는 식으로 구현 되어있다고 하는것 같음
그래서 len(LCS[-1][-1]) 요 부분에서 O(A * B * 문자열길이) 만큼 시간이 걸릴듯?
어떻게 최적화가 들어간다면 달라질지도 모르겠지만 아마 저래서 시간초과 뜨는 걸지도

펼쳐보기▼

감자가좋아

2023-03-14 06:26:45 답글

파이썬 컴파일러는 생각보다 멍청하구나.
중복된건 알아서 동일 논리 꺼내오는걸로 알고있었는데. 아닌가보네

펼쳐보기▼

KamaPytorq

2023-03-14 06:32:56 답글

미리 컴파일을 거치는 것도 아니니 그럴 순 있을듯...
그래도 여러번 실행하면 최적화하지 않?을까

펼쳐보기▼

진격의엄ㅋ

2023-03-14 06:27:40 답글

그게 그런식이라곤 꿈에도 생각못했는데...

펼쳐보기▼

KamaPytorq

2023-03-14 06:34:01 답글

사실 컴퓨터 메모리 구조 생각해보면 저렇게 구현하는거 말고는 좀 힘들듯

펼쳐보기▼

감자가좋아

2023-03-14 06:48:14 답글

*수정됨

파이썬 list구조 특성상 O(len(A)*len(B))는 아닌것 같고,  print 내부에서 -1말고 인덱스로 접근해봐도 똑같은데 print외부에서 똑같이 했을 때 문제가 없는 걸 보면 print함수의 문제인듯.
컴파일러가 print내의 요소들을 각개 다른걸로 본건지, 아님 print함수 자체의 문제인지는 몰?루

res1 = len(LCS[-1][-1])
res2 = LCS[-1][-1]
print(res1, res2, sep='\n')
얘는 1000ms

print(les(LCS[-1][-1], LCS[-1][-1], sep='\n')
얘는 2000++ms

기묘하다 파이썬!

펼쳐보기▼

댓글 작성