dbstjdgus0   2년 전

수들 중에서 제일 작은 값 두개를 리스트에서 제거 후 더한 값을 리스트에 추가 후

해당 값들의 합을 출력했습니다!

시간초과 문제는 어떻게 해결하는게 좋을까요...

조언 부탁드리겠습니다!

jeonggu223   2년 전

로직을 짜시고 난 뒤에 시간복잡도를 한 번 보시는 연습을 해보세요.

min함수같은 경우에는 배열을 다 흝으면서 그 중 작은 것을 찾는 것이기 때문에 O(n)

data.index(value) = data배열에서 value의 값을 찾는데 O(n)

data.pop(index) = data배열에서 해당 index를 pop한 뒤, 해당 빈자리를 채우기 위해 shift연산이 일어납니다. 최대 O(n)

for문이 N번만큼 돌고 for문 안에서 O(N)만큼 시간복잡도가 생기니 총 시간복잡도는 O(N^2)가 되겠죠?

N이 최대 10만이니 10만 * 10만 = 100억의 시간복잡도를 가집니다.

대충 1억번의 연산이 1초에 일어난다고 하니 100억이면 터무니 없을겁니다.

시간복잡도 개념과 사용하시는 메소드의 시간복잡도가 어떻게 되는지 공부하시는게 좋을 것 같네요.

dbstjdgus0   2년 전

감사합니다!! 독학중이라 많이 어렵네요 ㅠㅠ

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