배열
선형 배열을 알기 위해선 우선 배열에 대해 알아야 합니다. 배열이란 같은 종류의 데이터가 줄지어 들어간 것을 말합니다. 배열은 순서에 따라 원소들을 늘어놓은 것을 말합니다. 그렇기 때문에, 파이썬에서는 순서가 있는 데이터 타입인, 리스트를 배열로 사용합니다.
선형 배열
배열의 의미를 알면 선형 배열은 굉장히 쉽습니다. 선형 배열이란, 선 즉 일렬로 늘어져있는 배열을 의미합니다. 위에서 배열은 순서가 있는 데이터 타입이라고 했습니다. 그렇다면 선형 배열은 마치 맛집에서 줄서서 기다리듯이 일렬로 늘어져, 순서가 있는 데이터를 의미합니다.
선형 배열 이용하기
선형 배열을 사용하면, 많은 것들을 할 수 있습니다.
1. 원소 덧붙이기
우선 다음과 같은 선형 배열이 있습니다.
여기서, 프로그래머스 뒤에 'new'라고 하는 새로운 데이터를 삽입하고자 합니다. 그렇다면, 다음과 같이 이루어집니다.
코드로 나타내면 다음과 같습니다.
L = ['Bob', "Cat", "Spam", "Programmers"]
print(L)
#1. 원소 덧붙이기
L.append("new")
print(L)2. 원소 꺼내기
바로 위에서 붙인 맨 뒤의 요소 'new'를 바로 삭제하는것도 가능합니다. 삽입과 반대 프로세스로 이루어지면, 맨 뒤 요소 삭제입니다. 코드 상으로는 다음과 같습니다.
L.pop()
print(L)
3. O(1), 상수시간
이 두 가지 방식에는 공통점이 있습니다. 바로 리스트의 길이가 길던 짧던 그것과 상관없이 이루어진다는 점입니다. 이러한 알고리즘의 시간복잡도를 우리는 O(1) 즉 상수시간 알고리즘이라고 합니다. 단어 그대로 길이와는 전혀 연관 없이 상수의 시간만으로 이루어진다는 특징이 있습니다.
그러나, 이와 반대로 리스트 길이가 길어지면 실행시간이 길어질 수 밖에 없는 알고리즘들이 있습니다.
4. 배열 중간에 원소 삽입하기
바로, 배열 중간에 원소를 삽입하거나, 중간에 위치한 원소를 삭제하는 것입니다. 이해하기 쉽게 그림으로 알아보도록 하겠습니다.
위 사진처럼, 크기 순으로 정렬되어 있는 리스트에서 58과 72 사이에 65를 넣기 위해선 다음과 같은 과정이 필요합니다. 우선 72와 91을 각각 한 칸씩 내려줍니다. 그 후, 원래 72기 있던 자리에 65를 삽입해줍니다. 그림으로 보면 다음과 같습니다.
이 과정을 반대로 하면 리스트 중간 값을 삭제할 수 있습니다. 이를 파이썬 코드로 나타내면 다음과 같습니다.
#1. 배열 중간에 원소 삽입
L = [20,37,58,72,91]
L.insert(3,65) #index 3에 65 삽입함
print(L)
#2. 원소 삭제
del(L[2])
print(L)
L.pop(2)
print(L)
그렇다면 이 알고리즘들은 왜 리스트 길이에 비례하여 시간이 걸릴까요? 리스트 중간에 값을 삭제하거나 혹은 값을 삽입한다면, 기존 값들도 다른 자리로 모두 옮겨 주어야 하기 때문입니다. 리스트가 커지면, 더 많은 값들을 옮겨야 하기 떄문에 자연히 오래걸릴 수 밖에 없습니다..
이 방식을 빅오표기법으로 나타내면 O(n) 이라고 할 수 있습니다. 리스트 길이에 비례하여 선형의 시간이 걸리기 때문입니다.
선형 배열이 코테에 직접적으로 나오는 일은 거의 없지만, 알고리즘의 기본이기 때문에 잘 알아두는 것이 좋습니다. 모두 열심히 공부해서 원하는 기업에 합격할 때까지 파이팅합시다!
해당 포스팅은 프로그래머스의 어서와!자료구조와 알고리즘은 처음이지? 를 듣고 작성하였습니다.
어서와! 자료구조와 알고리즘은 처음이지?
× 이 강의는 Python 기반으로 진행하므로 최소한 문법에는 익숙한 상태로 수강해야 합니다. 듣고는 싶은데, Python을 잘 모르나요? 이 무료 강의 부터 듣고 수강하세요. × C++ 기반의 자료구조와 알
school.programmers.co.kr
'코딩테스트 준비 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 재귀 알고리즘 (2) | 2024.03.18 |
|---|