플랫폼: 프로그래머스
강의명: 어서와! 자료구조와 알고리즘은 처음이지?
강사명: 이시윤
네이버 웹툰 화산귀환의 주인공 청명이 자주 하는 대사가 있다.
"육합을 제대로 익히지 못하면 다른 검술을 익혀 봤자 소용이 없어."
파이썬 기본 자료형 중 하나인 리스트는
가장 처음 접하는 자료구조이자 많이 사용하는 자료구조임에 틀림없다.
스택이라는 자료구조로 응용되기도 하며,
비선형 자료구조 구현을 위한 재료로도 사용되는 기본 중 기본이다.
1. 상수 시간
"""
리스트 끝에 원소를 추가하거나 제거하기
- 상수 시간: O(1)
"""
AWS_SERVICES = ["EC2", "Beanstalk", "Fargate", "Lightsail"]
# 1. 마지막에 원소 추가
AWS_SERVICES.append("ElastiCache")
print(AWS_SERVICES)
# 2. 마지막 원소 반환
AWS_SERVICES.pop()
print(AWS_SERVICES)
리스트의 마지막 항목에 원소를 추가하거나 빼는 행위는 리스트 길이와 무관하다
2. 선형 시간
"""
리스트의 마지막이 아닌 곳에 원소를 추가하거나 제거하기
- 선형 시간: O(N)
"""
# 원소 추가
num_list = [20, 10, 33, 175, 177, 190]
num_list.insert(3, 1111)
print(num_list)
# 원소 제거
del num_list[2]
print(num_list)
# 원소 탐색하기
try:
res = num_list.index(2000000)
print(res)
except ValueError as e:
print(e)
그러나 마지막 인덱스가 아닌 곳의 원소 추가/제거는 전혀 다른 이야기다.
총 99개의 원소로 이뤄진 리스트가 있다고 하자.
첫 번째 위치에 새로운 값을 넣고 싶다.
기존 99개의 요소를 한 칸씩 우측으로 이동시켜야 한다.+99번의 이동
그리고 비어있는 첫 번째 자리에 새로운 요소를 삽입한다. +1번의 삽입
즉, 100번의 작업이 동반된다.
리스트의 모든 항목을 순회하며 찾고자 하는 원소가 있는지 확인하는 것 역시
리스트의 길이만큼의 시간이 소요된다. O(N)
