시간을 아끼는법

백준 문제를 풀면서 시간복잡도에대해 이해하게된것같다

단순한 출력을  O(1)

반복문부터는 O(N)

반복문을 두개겹쳐서 쓰면 O(N**2)

 

근데 왜 시간복잡도라고 하는거지 더나은 네이밍이 있었을것같다 

 

예를들어

a=[5, 23, 6, 8, 741]
for i in a:
	print(a)

를하게되면 a 요소 개수만큼 반복되니까 시간복잡도는 O(N)이다 

 

중요한것은 되도록이면 반복문을 겹쳐쓰지않는것이다 시간이 기하급수적으로 오래걸리게됨

N이작을때면 모르지만 N이커졌을때 문제가 생긴다 여기서는 N이최대 백만까지 나온다

 

몰랐는데 도저히 안풀려서 찾아보니 index()의 시간복잡도도 O(N)이라고한다

 

사실 문제는 금방풀었다 계속 시간초과가 나서 그렇지 처음엔

for문을 세개썻다 하나는 인덱스도 썻으니

시간복잡도는 한O(2N+N**2)정도 되었으려나?

 

결국 for문을 하나까지 줄였는데 그래도 시간초과가 나니까 좀 멘탈이나갔다

 

for문없이 푸는건 불가능하다고 생각했기때문

 

for문 아래에 있는 index()의 시간복잡도 역시 for문과 같은 O(N)이었던걸 몰랐었던것이다

 

set  쓰는법 리스트속 중첩요소를 없애는데 쓰임(for문대체)

요론식으로씀 list(set(list))

 

오늘또 배운건 print와 같이쓰는 end이녀석이다 한줄로 뽑아내라길래 리스트만든다음에 

join으로 합쳤는데 이거쓰면 정답제출용 리스트를 따로 만들지않아도되서 아주 유용한걸 배웠다

 

인덱스를 쓰지않고 풀어내는걸보고 대단하다고 생각했다