자료구조) 배열

애늙은이·2022년 12월 28일

목록 보기

1/2

순차 기억장소에 할당된 유한 개수의 동일자료형 데이터 모음

만약 우리가 선생님이고, 5명의 학생들의 시험 성적을 처리한다고 가정해봅시다.
이것을 코드로 짠다면, 5개의 변수를 선언하여 그곳에 성적들을 입력하겠죠.

하지만 학생 수가 100명, 1000명이 된다면, 그만큼 변수도 생겨날 겁니다. 굉장히 비효율적인 일이죠.

우리는 배열을 사용하여, 이 데이터들을 묶어낼 수 있습니다.
순차적으로 성적데이터를 나열하므로써, 처리하기 쉽게 만드는 거죠.

그렇기에 배열은 순차 기억장소에 할당됩니다.
즉, 메모리 상에서 순차적으로 원소들이 이어져있죠.

(Image from javatpoint)

배열에는 배열명, 배열 크기, 그리고 배열의 자료형이 있습니다.

int arr[N]; // int -> 자료형, arr -> 배열 이름, N -> 배열 크기

일반적인 배열을 선언할 때에는 N의 크기가 명시되어 있어야 하며, 자료형만큼 배열이 시작 주소 (Base address) 부터 N * (자료형 크기) 만큼의 메모리를 할당받습니다.

아까 학생들 얘기로 돌아와서, 만약 개별 학생들의 성적이 보고 싶을 때는 어떻게 해야할까요? 배열 이름만으로는 특정 학생을 구분하기 어려울 텐데요.

이를 위해 배열에는 인덱스라는 개념이 있습니다.
각각의 원소들을 구분하기 위해 방 번호를 붙인 것이죠.

인덱스는 일반적으론 0번부터 시작해서 N-1번으로 끝이 납니다.

다차원 배열은 2차원 이상의 배열들을 이야기 하지만,대부분의 다차원 배열은 2차원, 내지는 3차원으로 이루어져 있습니다.

다차원 배열은 메모리 상에서는 선형으로 되어있지만, 선언 시에는 행과 열을 따로 적습니다.

int arr[3][5]; // 행 : 3, 열: 5

💡 다차원 배열의 메모리 할당

다차원 배열에서 메모리는 저차원 우선 순서로 할당됩니다.
그러므로 고차원의 크기로 저차원을 구분합니다.
예를 들어 2차원 배열이라면, 행을 기준으로 할당이 되며,
열의 개수로 선형 메모리 내 행을 구분하는 것이죠.

시간 복잡도란 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼만큼 걸리는지를 나타냅니다.

시간 복잡도는 효율적인 알고리즘을 판단하는 척도가 됩니다.
시간 복잡도가 적을 수록 빠른 알고리즘을 구성할 수 있으니까요.

주로 Big-O 표기법을 통해 표현됩니다.

🤔 Big-O 표기법?

Big-O 표기법은 알고리즘이 최악의 경우일 때의 시간을 표기합니다.
또한 상수항, 계수 등의 영향이 적은 것들을 제거하고 최고차항만 표기하죠.
예를 들어 3n^3 + 2n + 3의 시간이 걸린다고 하면, O(n^3)의 형태로 표기합니다.

배열의 시간복잡도

글쓰는 개발자입니다.

자료구조