내가 하고싶은 건 다 하는 공간
코딩 테스트 합격자 되기 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함수가 훨씬 더 효율적이다.
따라서 유용한 함수들을 까먹지 말고 적재적소에 활용하는 능력이 요구된다.
앞으로 스터디를 진행하면서 놓치고 배우지 못했던 함수나, 까먹었던 함수를 다시 복습하는 계기가 되었으면 한다.
'알고리즘' 카테고리의 다른 글
코딩테스트 합격자 되기 6장 스택 (0) | 2025.06.28 |
---|---|
프로그래머스 level 1 모의고사 (Python 파이썬) (0) | 2025.06.22 |
[배열] 프로그래머스 level 1 두 개 뽑아서 더하기 (Python 파이썬) (0) | 2025.06.22 |
프로그래머스 level 2 n^2 배열 자르기 (Python 파이썬) (0) | 2025.06.17 |
프로그래머스 level 0 배열 회전시키기 (Python 파이썬) (0) | 2025.06.17 |