[자료구조] 배열과 리스트 with Python

알고리즘 첫 글에서는 배열이라고 하는 자료구조에 대해 알아보자.
파이썬을 배우며 리스트, 딕셔너리 등을 배웠는데 이런 것들도 배열과 비슷한 구조를 띄고 있다.

배열

• 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조
• 아래의 그림처럼 6개의 숫자를 배열로 바꾸어보았다.

배열이 왜 필요할까?

1. 프로그램 내에서 여러 개의 변수가 필요할 때, 일일이 다른 변수명을 이용하여 자료에 접근하는 것은 매우 비효율적일 수 있다.
2. 배열을 사용하면 하나의 선언을 통해서 둘 이상의 변수를 선언할 수 있다.
3. 단순히 다수의 변수 선언을 의미하는 것이 아니라, 다수의 변수로는 하기 힘든 작업을 배열을 활용해 쉽게 할 수 있다.
4. 즉, 여러 데이터를 하나의 이름으로 그룹핑해서 관리하기 위한 자료구조

그렇다면 배열을 사용하기 위해서는 어떻게 선언 해주어야 할까?

배열의 선언자

• 별도의 선언 방법이 없으면 변수에 처음 값을 할당할 때 생성
• 이름: 프로그램에서 사용할 배열의 이름

배열에 접근하기 위해서는 아래와 같이 접근하면 된다.

Arr[0] =10
Arr[idx] = 20

특징

1. 순서가 있는 값을 의미하며 들어있는 값을 요소(element)라고 한다.
2. 배열의 순서는 인덱스(index)라고 한다.
3. 배열에서의 인덱스는 유일무이한 식별자
4. 순서는 0부터 시작되며 []로 표시한다.
5. 크기가 정해져 있지만 기능이 없기 때문에 다른 자료구조의 좋은 부품으로 사용된다.
6. 배열의 경우 길이를 바꿀 수 없고, 가변 배열과 같은 변경가능한 배열은
   • 기존의 배열은 두고, 새로운 길이로 지정된 배열을 따로 할당
   • 데이터의 복사를 진행 후 기존 배열 삭제
   • 즉, 3번의 작업+메모리 탐색이 필요해 리소스 낭비가 크다.

그렇다면 리스트와 똑같이 생긴것 같은데 차이가 뭘까?

# 리스트와 배열

• 리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재라는 장점을 취한 자료 구조이다.
• 엘리먼트들 간의 순서가 가장 큰 특징이다. 따라서 다른 말로는 시퀀스(sequence)라고도 부르며 순서가 있는 데이터의 모임을 의미한다..
• 리스트에서의 인덱스는 몇 번째 데이터인가 정도의 의미
• 즉 head부터 순서대로 접근하기 때문에 접근속도는 느리지만 포인터로 연결되어있어 데이터를 삽입 삭제하는 연산 속도가 빠르다.
• 빈 엘리먼트는 허용하지 않으며, 데이터 갯수가 확실하게 정해져 있고, 자주 사용된다면 array가 더 효율적

파이썬에서는 기본적으로 리스트를 제공하며, 배열은 제공하지 않는다. (리스트의 특징과 배열의 특징을 모두 가진다) 즉, 리스트가 배열이다.
파이썬의 리스트는 크기가 가변적이고, 어떤 원소 타입이던 저장할 수 있다는 장점이 있지만 C의 array보다 메모리를 더 많이 필요로 한다는 단점이 있다!

예제 하나를 풀어보고 마치자.

Gravity

• 상자들이 쌓여있는 방이 있다. 방이 오른쪽으로 90도 회전하여 상자들이 중력의 영향을 받아 낙하한다고 할 때, 낙차가 가장 큰 상자를 구하여 그 낙차를 리턴하는 프로그램을 작성하시오.
  • 중력은 회전이 완료된 후 적용된다.
  • 상자들은 모두 한쪽 벽면에 붙여진 상태로 쌓여 2차원의 형태를 이루며 벽에서 떨어져서 쌓인 상자는 없다.
  • 방의 가로길이는 항상 100이며, 세로 길이도 항상 100이다.
  • 즉, 상자는 최소 0, 최대 100 높이로 쌓을 수 있다.
  • 예) 총 26개의 상자가 회전 후 , 오른쪽 방 그림의 상태가 된다. A상자의 낙차가 7로 가장 크므로 7을 리턴하면 된다.
  • 회전 결과, B상자의 낙차는 6, C상자의 낙차는 1이다.

1) 입력받는 수 중 가장 먼저 나오는 제일 큰 값이 리턴된다면 우리가 원하는 낙차 크기를 구할 수 있다!
2) 또는 입력받는 상자의 최대 낙차를 구한 후 아래 박스가 있다면 1씩 빼준다.
이번 시간엔 배열에 대해 알아보았다. 다음 시간엔 정렬이라는 것에 대해 배워보자!!