[Programming Language] 3. 자료형 (2)

직전글

2023.07.11 - [Language] - [Programming Language] 3. 자료형 (1)

● 배열

동질적인(동일한 타입을 가진) 데이터 원소들의 집합체

개개의 원소는 집단체(Aggregate)에서 첫 번째 원소와의 상대적인 위치(오프셋)에 의해서 식별됨. (개개의 배열 원소들에 대한 참조는 첨자(Subscript)나 색인(Index) 식을 이용하여 명세됨.)

※ 오프셋(Offset) vs. 색인(Index)

오프셋은 메모리상에서 처음 위치와 떨어진 거리, 색인은 배열 상의 순서를 의미함.

 

- 언어별 주의할 점

ㄴ C, Java, C++, Ada, C# 등

배열의 모든 원소들이 동일한 타입이어야 함.

포인터나 참조들은 단일 타입을 가리키거나 참조하도록 제한됨.

따라서, 가리켜지거나 참조되고 있는 객체나 데이터 값들도 단일 타입에 속함.

 

ㄴ Python, JavaScript, Ruby 등

변수들은 객체나 데이터 값들에 대한 타입과 상관없는 참조임.

배열은 여전히 단일 타입 원소들로 구성되지만, 그 원소들은 다른 타입의 객체 또는 데이터 값들을 참조 가능함.

배열의 원소들이 동일한 타입에 속하기 때문에, 원소들은 여전히 동질적이라고 할 수 있음.

 

- 배열과 색인

배열의 특정 원소들은 두 레벨의 구문 메커니즘에 의해 참조됨.

첫 레벨은 집단체 이름이고, 다음 레벨은 첨자 또는 색인임.

 

ㄴ 유한 사상(Finite Mapping)

선택 연산은 배열 이름과 첨자값들의 집합으로부터 집단체의 한 원소로의 사상으로 생각됨.

배열은 유한 사상이라고도 불림.

기호로 표시하면 다음과 같음.

[ 배열_이름(첨자_값_리스트) → 원소 ]

 

ㄴ첨자의 범위 오류

여러 프로그램에서 발생하는 공통적인 현상

범위 검사를 요구하는 것은 신뢰성에 중요한 요소임.

Java, C# 등은 검사를 명세하지만, 많은 프로그래밍 언어들(C 등)은 명세하지 않음.

 

- 첨자 바인딩과 배열 유형

배열 변수에 대한 첨자 타입의 바인딩은 보통 정적(대부분 Int)이지만, 그 첨자 값의 범위는 때때로 동적으로 바인딩됨.

어떤 언어들에서 첨자 범위의 하한(Lower Bound)이 묵시적으로 존재함.

(ex. C, Java - 0으로 고정 / Fortran 95+ - 하한 디폴트가 1)

다른 언어들에서는 첨자 범위가 프로그래머에 의해 명세되어야 함.

 

ㄴ 다섯 가지 유형의 배열

첨자 값 범위에 대한 바인딩, 기억공간에 대한 바인딩, 기억공간의 할당 위치에 기반해 분류함.

1. 정적 배열(Static Array)

첨자 범위가 정적으로 바인딩되고, 기억공간 할당이 실행 시간 전에(== 정적으로) 이루어짐.

장점 : 실행 시간의 효율성 → 동적 할당이나 회수 필요 x

단점 : 배열에 대한 기억공간이 프로그램 실행 시간 전체에 항상 존재해야 함.

예시 : C언어 static 배열

 

2. 고정 스택-동적 배열(Fixed Stack-dynamic Array)

첨자 범위가 정적으로 바인딩되고, 기억공간의 할당이 실행 시간 중 선언문 세련화 시간(Declaration Elaboration Time)에 이루어짐.

선언문 세련화 시간은 메모리가 할당되고 바인딩되는 시간을 의미함.

장점 : 정적 배열에 비하여, 기억 공간의 효율성 존재 (활성화되는 시간이 제한적)

단점 : 할당, 회수에 소요되는 실행 시간

예시 : C언어 함수에 (static 없이) 선언된 배열

 

3. 스택-동적 배열(Stack-dynamic Array)

첨자 범위 바인딩과 기억공간 할당 모두가 세련화 시간에 동적으로 이루어지지만, 일단 이루어지면 변수의 존속기간 동안 고정됨.

장점 : 정적과 고정 스택-동적 배열에 비해 유연함.(배열의 크기가 사용되기 전까지 미리 알려질 필요가 없음)

예시 : Ada의 배열

 

4. 고정 힙-동적 배열(Fixed Heap-dynamic Array)

첨자 범위와 기억공간의 바인딩이 기억공간이 할당된 후 고정된다는 점이 고정 스택-동적 배열과 유사함. 차이점은 첨자 범위와 기억공간의 바인딩이 실행 중에 사용자 프로그램의 요청으로 이루어지고, 기억공간이 힙으로부터 할당된다는 점임.

장점 : 유연성(사용자가 필요한 만큼만 요청할 수 있으므로 문제에 맞춤화됨)

단점 : 할당 시간(스택으로부터 할당보다 힙으로부터 할당이 더 오래 걸림)

예시 : C 동적할당, Java 비포괄적(Non-generic) 배열(== 타입이 지정된 배열)

 

5. 힙-동적 배열(Heap-dynamic Array)

첨자 범위의 바인딩과 기억공간의 할당이 동적이며, 배열의 존속기간 동안에 여러 번 변경 가능함.

장점 : 유연성(프로그램 실행 중 기억공간에 대한 필요가 변화됨에 따라 변경 가능)

단점 : 할당, 회수의 시간이 길어지고, 실행 중에 여러번 일어날 수 있음

예시 : Java 포괄적 클래스인 ArrayList 배열, Python 배열

5가지 배열 유형 정리표

※ 작명법? 암기법?

시험을 위해 만든..

명칭의 각 부분이 의미하는 바

- 배열 연산

배열 단위로 수행하는 연산

ㄴ 공통된 배열 연산

1. 배정

변수에 배열을 배정함.

2. 접합

배열과 배열을 이어 붙임.

3. 비교

두 배열이 같은지 비교함.

4. 슬라이스

배열의 일부를 잘라냄.

 

C는 배열 연산을 제공하지 않고 라이브러리 함수로 제공함.

Java는 메서드로 제공함.

Python은 동적 배열의 모든 특성을 가지지만, 리스트(List)라고 부름. 배열 원소는 객체에 대한 참조이고, 객체들은 임의의 타입이 가능함. 단지 참조 변경이기는 하지만 배열 배정을 제공하고, 접합(+), 멤버십(in), 슬라이스([:]) 연산을 제공함. 두 개의 비교 연산(is와 ==)도 제공함. (is는 참조가 같은지 검사하고, ==은 내용이 같은지 검사함)

 

- 직사각형 배열과 톱니형 배열

ㄴ 직사각형 배열(Rectangular Array)

모든 행들이 동일 개수의 원소들을 포함하고, 모든 열들이 동일 개수의 원소들을 포함하는 다차원 배열.

ㄴ 톱니형 배열(Jagged Array)

행들의 크기가 동일할 필요가 없는 다차원 배열.

톱니형 배열은 다차원 배열을 배열을 포함하는 배열로 볼 때 가능함.

C, Java는 톱니형 배열을 지원하지만 직사각형 배열은 지원하지 않음. (ex. myArray[3][5])

Fortran, Ada, C# 등은 직사각형 배열을 지원함. (ex. myArray[3,5])

 

- 슬라이스

배열의 부분 구조. 슬라이스는 새로운 데이터 타입이 아님에 유의!

배열의 부분을 한 단위로 참조하기 위한 메커니즘임.

 

ㄴ Python 예시

vector = [2, 4, 6, 8, 10, 12, 14, 16]
matrix = [[1,2,3], [4,5,6], [7,8,9]]

슬라이스는 배열 이름과 “[:]”를 이용하여 표현됨.
vector[3:6]은 vector의 네 번째부터 여섯 번째 원소까지 포함한 세 개의 원소를 갖는 배열([8, 10, 12])을 참조함.
matrix[1]은 mat의 두 번째 행([4, 5, 6])을 참조함.
vector[0:7:2]는 vector의 첫 번째부터 여섯 번째 원소까지 중에서 한 번씩 건너 뛰는 원소의 배열([2, 6, 10, 14])을 참조함.

 

- 배열의 발전 단계

초기 배열에서의 주요 진보 : 동적 배열, 슬라이스

최근 주요 진보 : 연상 배열(연관 배열) (관련 내용 아래에 나올 예정)

 

- 배열 타입의 구현

배열을 구현하는 것은 기본형을 구현하는 것보다 더 많은 노력이 요구됨.

배열 원소의 접근을 허용하는 코드는 컴파일 시간에 생성되어야 함. 즉, 생성된 코드는 실행 시간에 배열에서 특정 원소들의 주소를 계산할 수 있어야 함.

ㄴ 1차원 배열

list[k]로 표현되는 일차원 배열의 접근 함수 (하한(lower_bound)은 0인 언어가 대부분임)

주소( list[k] ) = 주소( list[하한] ) + ( ( k–하한 ) × 원소크기 )
# (어떤 원소의 시작주소) = (가장 처음에 있는 원소 주소) + (어떤 원소의 색인) × 원소크기

 

ㄴ 다차원 배열

다차원 배열은 1차원 배열보다 구현이 복잡함.

하드웨어 메모리는 선형적이므로, 두 개 이상의 차원을 갖는 데이터 타입의 값들은 1차원 메모리로 사상되어야 함.

+ 다차원 배열을 1차원 배열로 사상하는 두 가지 방법

1. 행-우선 순서

첫 번째 행의 원소들을 먼저 저장한 뒤, 다음 행의 원소들을 저장하는 형태

2. 열-우선 순서

첫 번째 열의 원소들을 먼저 저장한 뒤, 다음 열의 원소들을 저장하는 형태

 

A[i, j]로 표현되는 다차원 배열의 접근 함수 (행-우선 순서에서)

let, n = (행 단위의 원소 개수), row_lb = (행 하한), col_lb = (열 하한)
주소( A[i, j] ) = 주소( A[row_lb, col_lb] ) + [ { ( i – row_lb ) × n } + ( j – col_lb ) ] × 원소크기
# (어떤 원소의 시작주소) = (가장 처음에 있는 원소 주소) + { (어떤 원소가 있는 행 직전까지의 행 수 ×
                                            행 하나에 있는 원소 수) + (어떤 원소가 있는 열 직전까지의 열 수) } × 원소크기
                                         = Start + (A + B) × Size

 

- 연상 배열(Associative Array)

원소 개수와 동일한 개수의 키(key)들로 인덱싱되는, 순서를 갖지 않는 데이터 원소들의 모임.
배열에서는 색인을 저장할 필요가 없지만, 연상 배열에서는 사용자-정의 키들이 그 구조에 저장되어야 함.
따라서, 연상 배열의 각 원소는 실제로 항목들의 쌍 (키, 값)이 됨.

연상 배열은 원소들에 대한 탐색이 요구되면 배열보다 훨씬 좋음. 원소 접근에 쓰이는 해시 연산이 매우 효율적이기 때문임. 반면, 모든 원소들에 대한 명령을 수행해야 한다면 배열이 더 효율적임.

 

ㄴ 지원 언어
Python, Ruby, Perl, Lua 등 - 직접 지원

Java, C++, C# 등 - 표준 클래스 라이브러리로 지원

 

ㄴ Python에서 연상 배열

딕셔너리(Dictionary)라고 부름. (Perl에서는 해시(Hash))

값들이 모두 객체에 대한 참조임.