1. del과 pop의 차이점은 무엇일까?
del의 경우 제거된 요소가 반환되지 않는다.
또한, del은 슬라이싱으로 여러 값을 삭제할 수 있다.
pop은 제거된 요소가 반환된다.
값을 제거하는 방법 중에서 remove라는 것도 있다.
remove는 index로 접근하지 않고 첫 번째로 일치하는 값을 제거하는 방법이다.
만약 해당하는 값 또는 인덱스가 없을 경우
remove는 ValueError, del과 pop은 IndexError가 발생한다.
n개의 요소들중에서 i 번째 요소를 삭제할 때 시간 복잡도는 아래와 같다.
- del O(n - i)
- pop O(n - i)
- remove O(n)
2. list의 index() 메서드의 복잡도
index()함수의 인자값에 해당하는지 비교하면서 선형적으로 순회하기 때문에 O(n)의 복잡도를 가진다.
파이썬의 리스트에서 사용되는 연산들의 연산 시간에 대해서 아래와 같이 알아두자.
| 연산 | 설명 | |
| len(a) | 전체 요소의 개수를 리턴한다. | |
| a[i] | 인덱스 의 요소를 가져온다. | |
| a[i:j] | 부터 까지 슬라이스의 길이만큼 개의 요소를 가져온다. 이 경우 객체 개에 대한 조회가 필요하므로 이다. | |
| elem in a | elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 만큼 시간이 소요된다. | |
| a.count(elem) | elem 요소의 개수를 리턴한다. | |
| a.index(elem) | elem 요소의 인덱스를 리턴한다. | |
| a.append(elem) | 리스트 마지막에 elem 요소를 추가한다. | |
| a.pop() | 리스트 마지막 요소를 추출한다. 스택의 연산이다. | |
| a.pop(0) | 리스트 첫번째 요소를 추출한다. 큐의 연산이다. 이 경우 전체 복사가 필요하므로 이다. | |
| del a[i] | i에 따라 다르다. 최악의 경우 이다. | |
| a.sort() | 정렬한다. 팀소트(Timsort)를 사용하며, 최선의 경우 에도 실행될 수 있다. | |
| min(a), max(a) | 최솟값/최댓값을 계산하기 위해서는 전체를 선형탐색해야 한다. | |
| a.reverse() | 뒤집는다. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 된다. |
3. 이진 탐색과 순차 탐색의 장단점
순차 탐색은 보통 정렬되지 않고 무작위로 주어진 데이터 내에서 특정 원소를 찾을 때 자주 사용된다. 예를 들어 배열 내에 특정 원소 존재 여부를 체크한다거나 특정 원소 개수를 세는, Python으로 치면 count('value')와 같은 메소드가 있다. 순차 탐색은 정렬 여부에 상관없이 사용되므로 데이터 개수가 N개 일때 최악의 경우에 시간 복잡도 O(N)이 된다.
이진 탐색은 배열 데이터가 정렬 되어있을 경우에만 사용이 가능하다. 이진 탐색은 3가지의 변수를 사용해서 구현되는데, 배열의 시작점, 배열의 끝점, 배열의 중간점을 사용한다. 결국 찾으려는 데이터와 중간점에 있는 위치의 데이터와 반복적으로 비교한다. 그리고 중간점 위치를 계속 옮겨다니면서 특정 데이터를 찾아낸다.
시간 복잡도가 (logN)이 되게 된다. 연산 횟수를 매번 줄어들게 하는 효과가 있기 때문에 입력 데이터가 매우 많거나 탐색 범위가 매우 넓을 때, 구체적으로는 데이터 개수가 1,000만 단위 이상 또는 탐색 범위가 1,000억 이상일 때 자주 사용된다.
divide and conquer를 통해서 이진 탐색시 시간 복잡도가 많이 줄어드는 장점이 확실하게 있다. 하지만, 반드시 크기 순서대로 정렬이 되어 있어야 한다는 점이 큰 단점이 될 수 있다. 만약 한 번만 탐색하고 말거라면, 굳이 크기 순으로 늘어놓으라 시간을 소비해야할까? 이럴 경우 순차 탐색을 통한 방법이 효율적일 수 있다.
회고
크게 배열과 연결 리스트에 대해서 학습하였다. 학과 시절 그리고 스스로도 공부했던 내용이지만 다시 상기시킬 수 있는 시간이었다.
조합과 순열에 관해서 직접 구현해보는 시간을 가지는 것이 좋을 것 같다. 여태까지 다양한 환경에서 공부한 것들에 대해서 흔적을 남겼었지만 TIL에 적합한 글을 쓰진 않았던 것 같다. 단순히 필기용도로 작성했던 것 같다. 배운 내용을 하나도 빠짐 없이 작성하려고 노력했던 것 같다. 진정한 TIL에 가까워 지도록 노력해보자!!!
'CS > 자료구조' 카테고리의 다른 글
| 프로그래머스 인공지능 데브코스 3기 1주차 Day3(1) (0) | 2021.12.10 |
|---|---|
| 프로그래머스 인공지능 데브코스 3기 1주차 Day2(2) (0) | 2021.12.09 |
| 프로그래머스 인공지능 데브코스 3기 1주차 Day2(1) (0) | 2021.12.09 |