본 포스팅은 프로그래머스의 어서와! 자료구조와 알고리즘은 처음이지? 강의를 듣고 정리한 것임을 참고 바랍니다.
선형 배열 (Linear Array)
- 배열(Arrays) - 같은 종류의 데이터가 줄지어 늘어서있는 것을 뜻 함, 파이썬에는 따로 존재하지 않음
- 리스트(List) - Python의 list는 다른 프로그램의 Arrays에 비해 융통성이 있는 자료구조
Python 리스트의 index는 0부터 시작, 리스트의 요소의 길이가 달라도, 다른 타입이여도 상관이 없다.
리스트 연산은 크게 5가지로 나뉜다.
(1) 원소 덧붙이기(append)
(2) 끝에서 꺼내기(pop)
리스트의 (1), (2) 연산은 리스트의 길이와 무관한 상수 시간이 걸린다. O(1)
(3) 원소 삽입하기(insert)
리스트를 하나 삽입하였음에도 불구하고 이전보다 많은 연산이 필요하다는 것을 알 수 있다.
(4) 원소 삭제하기 (del(L[2]), L.pop(2))
리스트의 (3), (4) 연산은 리스트의 길이가 길면 오래 걸린다. (리스티의 길이에 비례, 선형시간), O(n)
del(L[2])의 L.pop(2) 차이점
- del은 특정 인덱스에서 항목을 제거
- pop은 특정 인덱스에서 항목을 제거한후 반환
(5) 원소 탐색하기
