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..

tuple의 형태와 기초를 다루는 형태로 코드를 작성해보았다. # tuple t1 = () t2 = (1,) t3 = (1, 2, 3) # 괄호를 생략해도 무방 t4 = 1, 2, 3 t5 = ('a', 'b', ('ab', 'cd')) t1, t2, t3, t4, t5 # list 의 값은 변경이 가능하지만 tuple의 값은 변경이 불가능하다. # 지우는 것이 불가능 t1 = 1, 2, 'a', 'b' del t1[0] # error # 변경 불가능 t1[0] = 'c' # error # indexing t1 = 1, 2, 'a', 'b' t1[0] # 1 a = ((1 ,2) , (3,4), (5,9)) a[:][1] # (3, 4) # slicing t1[:-1] # (1, 2, 'a') t1[1:..