코딩 테스트 합격자 되기 5장 배열

코테합 스터디를 진행하고 있습니다.

파이썬의 개념은 어느정도 아는 상태이기 때문에, 책을 읽으면서 몰랐던 부분, 까먹었던 부분만 정리하고자 합니다.

 

배열 연산의 시간 복잡도

원소에 접근할 때: 인덱스를 가지고 바로 접근 가능하므로 O(1)

맨 뒤에 원소를 삽입할 때: append() 메서드를 이용해서 바로 삽입 가능하므로 O(1)

맨 앞/중간에 원소를 삽입할 때: 원래 있던 원소들을 한 칸 씩 뒤로 미루는 작업을 해야하므로 O(N)

 

배열을 선택할 때 고려할 점

위에서 언급했듯, 배열은 삽입/삭제 과정에서 많은 비용이 소모된다. 따라서 메모리 공간을 충분히 확보해야 한다는 단점이 있으므로, 코딩테스트를 풀 때 시간, 메모리 제한 등을 잘 확인해야 한다.

1. 할당할 수 있는 메모리 크기 확인: 보통 1차원 배열은 1000만, 2차원 배열은 3000*3000 크기를 최대로 생각한다.

2. 빈번한 삽입: 위에서 언급했듯, 한 번 삽입하는데 시간복잡도가 O(N)으로 매우 높다. 빈번한 삽입은 최대한 지양해야 한다.

 

메서드

메서드를 사용한다고 해서 그게 어딘가에 저장되는 게 아니라, 단순히 그 행위가 진행되는 것일 뿐이다.

따라서 메서드를 특정 변수에 저장해야 한다.

a = [1, 2, 3]
a.remove(1)
b = a.remove(1)

remove는 조건을 만족하는 원소들 중 맨 앞에 있는 원소만 제거된다는 점을 기억하자.

이 외에도 index, count 함수들이 있었다.

 

참고로 sort() 메서드의 시간복잡도는 O(NlogN)이다.

list(set())의 시간복잡도는 O(N)이다.

 

마무리

파이썬에는 유용한 함수들이 많다. 예를 들어 직접 버블정렬하기보다는 sort함수가 훨씬 더 효율적이다.

따라서 유용한 함수들을 까먹지 말고 적재적소에 활용하는 능력이 요구된다.

앞으로 스터디를 진행하면서 놓치고 배우지 못했던 함수나, 까먹었던 함수를 다시 복습하는 계기가 되었으면 한다.