지난 챕터 linear list에 이어 이번 챕터에서는 배열에 대한 내용을 기록하려고 한다. 배열의 의미는 지난 챕터에 기록을 해두었기 때문에 이번 챕터에서는
✅ 배열의 ADT
✅ 실행 함수(add, remove 등)에 따른 big-O() 차이
위 내용에 대해 정리하고, Structures and Unions에 대해 간단하게 정리하려고 한다.
1. 배열의 ADT
저번 list의 ADT와 마찬가지로 배열도 ADT로 나타낼 수 있다. 배열의 main method로는
- get(int i) >> index i인 요소를 삭제하지 않고 값만 리턴
- set(int i, obj o) >> index i인 요소의 값을 o로 대체하고 대체 전 값 리턴
- add(int i, obj o) >> index i에 새로운 요소 o 추가
- remove(int i) >> index i값 제거 후 index i값 리턴
이 있다. Additioanl method로는 size(), isEmpty()도 있다.
ADT Array is
objects : A set of pairs <index,value> where for each value of index there is a value from the set item.
Index is a finite ordered set of one or more dimensions, for example,
{0,...,n-1} for one dimension, {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)}
for two dimensions,etc.
functions :
for all A ∈ Array, i ∈ index, x ∈ item,j,size∈integer
Array Create(j,list) ::= return an array of j dimensions where list
is a j-tuple whose ith element is the size of
the ith dimension. Items are undefined.
Item Retrieve(A,i) ::= if(i∈index) return the item associated with
index value i in array A
Array Store(A,i,x) ::= if(i in index)
return array that is identical to array A except the
new pair<i,x> has been inserted else return error
end Array이런 식으로 ADT를 쓸 수 있고, objects 부분은 역시 바꿀 수 없다. functions는 접근 방법을 알려주고있고 저기에 나온 세 개의 함수는 사용해줘야 한다.
2. 배열 실행 (Big-O)
배열에 다양한 함수를 실행시켜 값을 얻어낸다던지, 중간 요소를 삭제한다던지 등등의 작동을 시킬 수 있다. 그럴 때 실행 횟수를 big-o로 나타내볼 수 있다.
가볍게 리마인드를 하자면 big-O의 표기 규칙은 최고차항만 남겨두고 최고차항의 계수도 지워 표기한다. 예를 들어 2n+3이라면 O(n)으로 표기할 수 있다는 뜻이다.
2-1. O(1)의 예시 _ get(i), set(i), size, isEmpty
main method중 get(i)를 실행한다고 해보자. get()은 index i인 값을 return하는 함수이므로 원하는 인덱스에 가서 값을 추출하는 한 번의 과정만 거치면 된다. 그러므로 O(1)로 표기한다.
2-2. O(2)의 예시 _ add(i,o), remove(i,o)
add를 실행한다고 해보면, add는 index i에 값이 o인 값을 추가하는 것이므로 index i 이후의 요소를 뒤로 한 칸씩 밀어낸 후 빈 자리에 o를 삽입하는 것이다. Worst case는 i가 0인 경우로, index의 크기가 n이라면 밀어내는 과정을 n번 한 뒤에야 값을 추가할 수 있게 된다. n+1이라고 볼 수 있겠지만 최고차항만 남기므로 n이라고 해야한다. 따라서 O(n)으로 나타내게 된다.
2-3 add, remove가 O(1)인 경우 _ circular array(환형 배열)
환형 배열은 시작과 끝이 이어져있는게 특징이라서 add(0,x)나 remove(0,x)의 경우 맨 뒤에 붙여넣는 것과 같게 되므로 중간에 끼워넣을 때처럼 다른 값들을 이동시킬 필요가 없어진다. 따라서 O(1)이 된다.
3. 구조체와 공용체 (Structure and Union)
구조체와 공용체는 자료구조를 C로 배울 때에만 다루고 JAVA로 배울 땐 다루지 않는다고 하셨다. 그래서 각각의 의미만 간단하게 보고 넘어갔다. 사실 이 부분은 1학년 2학기에 배운 시스템프로그래밍 기초 과목에서 배웠던 부분이라 리마인드만 했다!
- arrays(배열) : 배열은 같은 타입의 요소들만 같은 배열에 담을 수 있다.
- Structures(구조체) : 구조체는 다른 타입의 요소들을 담을 수 있다. 구조체 값을 꺼낼 때에는 .으로 연결한다.
typedef struct {
char name[5];
int age;
float salary;
}person;위와 같이 선언하며, 만약 age에 2라는 값을 넣고 싶다면, person.age = 2 로 작성한다.
- Unions(구조체) : 다른 자료형들에게 한 장소를 빌려주는 느낌으로 이해하면 될 것 같다.
union int_or_float {
int i;
char f;
}이라 하면 최대 sizeof(int)만큼의 메모리가 할당된다. 한 번에 한 자료형에게만 메모리를 할당해준다.
이렇게 또.... 2023/1/30의 강의기록 끗........😊
