[코드잇-자료구조1 : 기본 자료구조들] 3. 배열
본 게시물은 코드잇의(codeit) 자료구조 시리즈 강의 첫번째 주제인 '기본 자료구조들'을 듣고 정리한 게시물임을 알려드립니다.
1. 배열이란 (배열은 가장 기본적인 자료구조이기에 중요하다.)
- 파이썬에서 말하는 리스트와 비슷한 개념
- 파이썬 언어는 C언어를 기반으로 만들어졌고, 파이썬 리스트는 C의 배열을 이용해서 만들어짐
- 그런데 파이썬 리스트랑 C 배열은 몇 가지 핵심적인 차이가 있음
파이썬 리스트와 C 배열
파이썬 리스트
- append 메소드를 쓰면 계속 요소 추가 가능
- 다양한 타입의 값들을 담을 수 있음
C 배열
- 처음에 배열의 크기를 정해놓고 시작함, 배열의 각 요소를 다른 값으로 수정은 가능하지만 지우거나 삭제는 불가
- 같은 타입의 값들만 담아야 함
파이썬 리스트와 C 배열이 실제로 값들을 저장하는 방법
파이썬 리스트
- 필요한 공간을 메모리에서 사용
- 데이터가 메모리에 연속적으로 저장되는 C 배열과 달리, 파이썬 리스트에서는 2,3,5,7 이 값들이 메모리 아예 다른 곳에 저장되어 있을 수도 있음. 연속적인 공간에 있을 수도 있고, 아닐 수도 있음
- 그럼 위 공간에 있는 것 : 2,3,5,7에 대한 레퍼런스가 저장되어 있는것. 즉, 이 칸들은 2,3,5,7을 담고있는게 아니고, 2,3,5,7을 가리키고 있는 것.
- 이에, 어차피 값 자체를 저장하는 게 아니기 때문에 자료들의 크기가 상관이 없음
- 아무리 큰 값이어도 위에서는 그냥 가리키는 역할만 함.
- 그래서 C배열과 달리 파이썬 리스트는 다양한 타입의 값들을 저장할 수 있는 것
C 배열
- 크기를 정해놓고 시작함
- 그래서 처음에 배열을 정의할 때 크기를 정함
→ 아래 예시에서는 정수 타입 네 개를 담을 수 있는 배열을 만든 것
- 메모리에 필요한 만큼의 공간을 미리 할당해둬야 함
- C에서는 정수 하나가 보통 4바이트이기 때문에 정수 4개를 담기 위해서 총 16바이트의 메모리를 예약함. 위의 예시에서는 연속적인 16칸을 예약함
- 0번 인덱스에 2, 1번 인덱스에 정수 3, ...
- 각 정수값 크기는 4바이트
2. 배열 인덱스를 이용한 데이터 저장/접근법
배열에 데이터를 저장하고 가지고 오는 법
- 파이썬에서는 배열을 잘 안쓰기 때문에 그냥 C배열로 설명할 것
- 문법은 대충만 봐도 됨
- 우선 사용하고 있지 않고, 연속적인 16칸의 메모리 찾고 위같이 값 할당
저장된 데이터를 받아오는 법
- 저장할 때처럼 인덱스를 사용하면 된다.
내부적으로 작동되는 방식
- 우선 배열에 어떤 인덱스의 값을 받아오기 위해서는 그 값의 주소를 알아야 한다.
- 근데 이 주소는 그냥 간단한 계산으로 구할 수 있음. 즉, 주소만 알면 O(1)으로 접근이 가능함. 다시말해 배열에서 값을 받아오는 것은 O(1)으로 할 수 있다는 것.
- 우선 numArray는 이 배열이 시작되는 지점의 주소를 가리키고 있음
- 그리고 몇 번 인덱스를 받고 싶은지에 따라서 주소를 찾음
- 램은 말 그대로 '임의 접근 메모리'이기에, 그 주소가 어디에 있든 상관없이 같은 속도로, 효율적으로 접근 가능
→ 즉, O(1)으로 접근이 가능
이는 값을 저장할때에도 마찬가지
- 특정 인덱스의 값을 저장하기 위해서는 그 인덱스의 주소를 알아야 되는데, 값을 받아올 때랑 똑같이 주소를 찾아서 그 주소의 O(1)으로 접근하고 거기에 값을 저장하면 되는 것
정리하면
- 값을 저장하든 / 받아오든
배열 인덱스 접근 : O(1)
이며, 이게 배열의 가장 큰 장점.
- 즉, 주소만 정확히 알고있으면 한 번에 접근할 수 있는 램의 특성을 똑똑하게 이용하는 자료구조
3. 배열 탐색
4. 정적 배열