[자료구조] 리스트 (배열)

리스트란?

• 같은 타입으로 이루어진 원소들이 연속된 공간에 나열되어 있는 자료구조

시간 복잡도

1. Search

• 리스트는 인덱스로 원소에 접근이 가능하다. O(1)

2. Insert

• 맨 뒤에 원소를 삽일할 경우 O(1). 단, 맨 앞에 원소를 넣을 시 원소들을 한 칸씩 뒤로 밀어야 함으로 O(N)의 시간 복잡도가 소요.
• C++, 자바의 벡터나 파이썬 리스트 같은 경우. 할당된 메모리에 값이 다 차 있는 경우에 값이 들어오면 자동으로 메모리를 늘린 다음에 원소를 넣는다. 이 때 O(N)의 시간 복잡도가 소요됨. (참고만 하자)

3. Delete

• 맨 뒤에 원소를 삭제할 경우 O(1). 단, 맨 앞에 원소를 삭제할 시 원소들을 한 칸씩 앞으로 당겨야 함으로 O(N)의 시간 복잡도가 소요.

문제

백준 3273번 (두 수의 합)

어떻게 접근할 것인가

• 이중 포문. (완전 탐색). 시간 복잡도 상 TLE O(N^2)
• 리스트를 정렬한 뒤, 리스트 양 끝에 두 개의 인덱스가 가리키는 원소의 합에 따라 인덱스 이동 (투포인터 알고리즘) O(N)