[자료구조 & 알고리즘] #1. 선형 배열(Linear Arrays)

허상범·2021년 11월 10일
0

CS 101

목록 보기
2/2

2강: 선형 배열(Linear Array)

선형 배열 (Linear Arrays)

선형 배열은 데이터들이 선 (line) 처럼 일렬로 늘어선 형태를 말합니다. 보통 프로그래밍에서 배열 (array) 이라고 하면 같은 종류의 데이터가 줄지어 늘어서 있는 것을 뜻하는데요, Python 에서는 서로 다른 종류의 데이터 또한 줄세울 수 있는 리스트 (list) 라는 데이터형이 있습니다.

이 강의에서는 같은 종류의 데이터가 줄지어 늘어서 있는 배열을 이용하려 합니다. 앞으로 배열 (array) 이라는 말과 리스트 (list) 라는 말이 자주 등장할 겁니다만, 우선은 같은 것이라고 생각해도 좋지만, 개념적인 구조, 즉 데이터를 늘어놓은 모양새를 말할 때는 배열 (array), Python 의 데이터형을 가리킬 때에는 리스트 (list) 라는 용어를 사용하겠습니다.

7강부터 이어질 "연결 리스트 (linked list)"와는 구별되어야 합니다.

Python 리스트에 활용할 수 있는 연산들

리스트 길이과 관계 없이 빠르게 실행 결과를 보게되는 연산들

  • 원소 덧붙이기 .append()

  • 원소 하나를 꺼내기 .pop()
    위 연산들은 리스트의 길이와 무관하게 빠르게 실행할 수 있는 연산들입니다. 리스트의 길이가 아무리 길어도 맨 끝에 요소 하나를 추가하는 것이나 맨 끝 요소 하나를 빼는건 빠르게 할 수 있는 일이죠. 반면, 리스트가 커지면 그에 따라 실행시간이 길어지는 연산들도 있습니다.

  • Big O Notation에 의하면 위와 같은 연산을 O(1)O(1)로 표시하고, 상수 시간에 할 수 있는 연산이라고 함.

리스트의 길이에 비례해서 실행 시간이 걸리는 연산들

  • 특정 위치의 원소 삽입하기 .insert()
  • 특정 위치의 원소 삭제하기 .del()

이런 연산들은 리스트의 길이가 길면 길수록 처리가 오래 걸리게 됩니다. 구체적으로 말하면 리스트의 길이예 실행 시간이 비례합니다. 리스트 길이가 100 배가 되면, 위 연산들을 실행하는 데 걸리는 시간도 100 배 커집니다.

아래와 같은 리스트 하나가 총 0~4의 인덱스를 갖는 숫자들로 하영금 오름차순의 순서로 정의되어 있다고 합시다.

L = [20, 37, 58, 72, 91]

위 리스트 가운데 65라는 숫자형 데이터 하나를 오름차순을 그대로 유지한 상태로 리스트에 추가하려면 어떻게 해야할까요? 58과 72 사이에 넣어야 할 것입니다. 즉, 아래와 같이 표현되어야 합니다.

L.insert(3, 65)

그렇다면 위 연산의 실행 구조를 살펴보도록 하겠습니다.

1) 기존의 3번 인덱스에 위치한 숫자(72)의 바로 앞 공간을 찾아내고,
2) 전체 리스트의 길이를 1만큼 증가시켜 준 후 (리스트의 총 길이가 5에서 6으로 바뀜)
3) 3번 인덱스 바로 앞 공간을 기준으로 숫자들을 1칸씩 뒤로 밀어주면, 3번 인덱스를 제외한 0,1,2,4,5 인덱스에는 모든 숫자가 할당됨
4) 그리고 비어있는 3번 인덱스의 공간에 내가 밀어넣으려는 숫자인 65를 밀어넣게 됨.

위 연산에 의해 리스트의 길이가 1 증가하긴 했지만, 단순히 리스트의 맨 끝에 원소를 추가하거나 뽑아내는 연산인 append, pop보다 상대적으로 복잡한 연산에 해당합니다.

  • 이러한 연산은 리스트의 길이가 길수록 연산 시간이 비례하여 증가하는 연산, 즉 리스트의 길이에 비례하는 연산
  • Big O Notation에 의하면 위와 같은 연산을 O(n)O(n)로 표시하고, 선형 시간에 할 수 있는 연산이라고 함.

Q. del 연산과 pop 연산의 차이점은?

del 연산은 리스트에 담겨있는 전체 원소의 인덱스(위치)를 참조(탐색)하여 동작하는 연산이지만, pop은 단순히 특정 위치 하나만을 참조해서 특정 원소를 삭제하는 점에서 구조적으로 차이가 있습니다. (구체적인 목적이 있지 않는한 pop 연산이 훨씬 효율적으로 보인다..?)

추가 다른 연산

  • 원소의 위치 탐색하기: .index()
L = ['Bob', 'Cat', 'Spam', 'Programmers']
L.index['Spam']
>>>> 2

연습문제

1. 정렬된 리스트에 주어진 원소 삽입하기

2. 주어진 리스트에서 특정 원소를 모두 찾아내라.

profile
Engineering & Science, Since 2021 | Finance, Backend, Data

0개의 댓글