ok-lab

Contents 코딩 테스트를 하다보면 시간 복잡도를 고려하지 않아서 발생하는 시간 초과 문제에 직면할 때가 있다. 코딩 테스트에서는 리스트(List) 구조를 많이 사용하는데, 리스트에 사용할 수 있는 함수 혹은 주요 연산들의 시간 복잡도가 어느 정도인지 알아보자. List 연산 시간 복잡도 설명 $\text{len(a)}$ O(1) 전체 요소의 개수를 리턴한다. $\text{a[i]}$ O(1) index $i$의 요소를 가져온다. $\text{a[i:j]}$ O(k) index $i$부터 $j-1$까지의 길이만큼 $k$개 요소를 가져온다. 객체 $k$개에 대한 조회가 필요하기 때문에 O($k$) $\text{element in a}$ O(n) 요소가 존재하는지 확인하는 경우 순차 탐색을 해야하기 때문..

파이썬의 리스트의 경우 다른 객체에 할당받은 후 그 객체를 변경해도 변경되지 않지만, 넘파이 array의 경우 view(원본)을 나타내기 때문에 원본이 변경되지 않게 하거나 copy를 해주어야한다. li = [x for x in range(10)] arr_li = li[:] arr_li[0] = 100 print(li) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] print(arr_li) # [100, 1, 2, 3, 4, 5, 6, 7, 8, 9] 리스트의 경우 위와 같이 객체 0번을 받아서 변경을해도 변경이 되지 않는 것을 확인할 수 있다. 복사본의 경우 변경되어 있는 것이 보인다. arr = np.arange(10) arr_view = arr[:] arr_view[0] = 100 pr..