dev-waterparsley

01. 배열의 정의

✅ 배열

• 메모리 공간(메인 메모리, DDR)에 저장되는 원소의 물리적인 위치를 순차적으로 결정
  • 배열의 순서 == 메모리 공간에 저장되는 원소값의 물리적 순서
• 원소들은 모두 같은 자료형과 같은 크기의 기억 공간을 가짐
• 인덱스와 원소값(<index, value>)의 쌍으로 구성된 집합

• 인덱스(index)
  • 컴퓨터의 내부구조나 메모리 주소와 무관하게 개발자에게 개념적으로 정의됨(추상화된 값) → 불변
  • 보통 배열의 인덱스는 0부터 시작
  • 인덱스를 이용해서 원소값에 접근하기 때문에 직접 접근 가능
• 메모리 주소값은 실제 메모리의 물리적인 위치값(주소값)
  • 실제로 연속된 메모리에 저장됨
  • 주소값은 가변적임(시간이 지나거나 프로그램을 실행할 때마다 변경됨)

02. 배열의 추상 자료형

▪️ 추상자료형: 객체 및 관련된 연산의 정의
예를 들어 C언어의 printf() 처럼 C 컴파일러 개발자가 만들어 놓은 것을 다른 개발자들은 가져다 쓰기만 하면 되는...

▪️ 자료형: 메모리 저당 할당을 위한 선언
int, float, ...
'내가 프로그래밍에서 이 변수에 대해서 이러한 메모리 영역을 할당받고 싶어'라고 선언하는 것

🔸ADT Array 객체

• < i∈Index, e∈Element > 쌍들의 집합
  • Index: 순서를 나타내는 원소의 유한집합
  • Element: 타입이 같은 원소의 집합

🔸연산

• a: 0개 이상의 원소를 갖는 배열
• item: 배열에 저장되는 우너소
• n: 배열의 최대 크기를 정의하는 정수값

03. 배열의 연산의 구현

※ 컴파일러 개발자의 역

▪️ 배열 생성

//① Array create(n) ::= 배열의 크기가 n인 빈 배열을 생성하고 배열을 반환;
void create(int *a, int n){	//n=5
	int i;
    for(i=0, i<n, i++){
    	a[i] = 0;
    }
}

▪️ 배열 생성 결과

▪️ 배열값 검색(retrieve 연산)

/*
	② Element retrieve(a, i) ::= if(i∈Index) then{ 
                                                    배열의 i번째에 해당하는 원소값 'e'를 반환; 
                                                 }else{  
                                                    에러 메세지 반환; 
                                                 }
*/
#define array_size5
int retrieve(int *a, int i){ //i=2
	if(i>=0 && i<array_size){
    	return a[i];
    }else{
    	printf(Error\n);
        retrun(-1);
    }
}

▪️ 배열값 검색 결과

▪️ 배열값 저장(store 연산)

/*
	③ Array store(a, i, e) ::= if(i∈Index) then{ 
    				배열 a의 i번째 위치에 원소값 'e'를 저장하고 배열 a 반환; 
        	}else{ 
                    인덱스 i가 배열 a의 크기를 벗어나면 에러메세지 반환; 
            }
*/
#define array_size 5
void store(int *a, int i, int e){ //i=3, e=35
	if(i>=0 && i<array_size){
    	a[i] = e;
    }else{
    	printf("Error\n")
    }
}

▪️ a[3]의 값이 35로 변경되어 저장된 모습

04. 1차원 배열 및 배열의 확장

✅ 1차원 배열

• 한 줄짜리 배열을 의미하며 하나의 인덱스로 구분됨
• A[]의 시작주소값을 a라고 가정하면, A[i] 저장 주소는 [a+i*k]가 됨(k: 메모리할당단위)
• 운영체제가 이러한 규칙을 기반으로 데이터에 접근

✅ 행렬의 배열 표현

• 행렬을 컴퓨터에서 표현하기에는 2차원 배열(1차원 배열을 여러 개 쌓아 놓은 것)이 적합함

🔸행 우선 배열

🔸행 우선 할당

• 가로의 1차원 배열 단위로 메모리 영역을 우선 할당함

🔸열 우선 배열

🔸열 우선 할당

• 세로의 1차원 배열 담위로 메모리 영역을 우선 할당함

🔸C언어에서의 2차원 배열(행 우선 순서 저장)

• C언어에서 A[5][3]을 선언하면 다음과 같은 배열 생성
• 사용하는 언어가 어떠한 배열 저장 규칙을 갖고 있는지를 알면 좀 더 향상된 프로그램 실행 속도를 찾아낼 수 있다!

05. 희소행렬의 개념

✅ 희소행렬

• 원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많음
• 메모리 낭비를 막고 효율성을 높이기 위해서 0인 원소는 저장하지 않고 0이 아닌 값만을 따로 모아서 저장하는 방법이 필요 => 희소행렬(추상화를 한 번 더한 것)

1. 기본 개념

• 자료구조(data structure): 추상화를 통해 자료의 논리적 관계를 구조화한 것
• 추상화: 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것 예) 수식, 프로그램 언어 등
• 자료(데이터)의 추상화: 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 데이터의 구조에 대해서 공통의 특징만을 뽑아 정의한 것

• 자료의 추상화와 구조화가 적절히 이루어지지 못하면 소프트웨어는
  • 비효율적으로 개발되거나
  • 비요율적으로 수행되거나
  • 소프트웨어의 확장성에 문제가 생기거나
  • 소프트웨어의 유지보수에 문제가 생길 수 있음

🔸자료구조의 종류와 관계

• 미리 정의된 자료구조
  • 프로그래밍 언어에서 제공
  • 프로그래밍 설계나 컴파일러 구현 단계에서 정의되어 개발자에게 제공되는 자료구조
• 사용자 정의 자료구조
  • 개발자가 정의하여 사용함
  • 소프트웨어 개발 중에 개발자에 의해 만들어지는 자료구조(리스트, 스택, 큐, 트리, 그래프 등)

2. 배열

• 배열(array): 동일한 자료형을 갖는 여러 개의 데이터를 동일한 변수 이름의 방에 일렬로 저장하는 자료 집합체(원소+인덱스)
• 원소(요소): 자료 집합체에서 각 원소의 항목값 = 데이터
• 인덱스(첨자): 자료 집합체에서 각 원소가 저장된 방을 접근하기 위한 방 번호에 해당하는 것 = 번호

🔸1차원 배열

• 가장 간단한 형태의 배열
• 한 개의 인덱스(첨자)를 사용해서 원소에 직접 접근
• 배열의 원소들은 컴퓨터 메모리의 연속적인 기억장소에 할당되어 순차적으로 저장됨
• 배열 A의 크기를 k라고 가정하고 시작 주소를 a라고 가정하면, A[i]의 저장 주소= a+i*k

🔸다차원 배열

2차원 배열

다차원 배열: 두개 이상의 첨자들을 가지는 배열을 총칭함

• 동일한 크기의 1차원 배열을 모아 놓아, 바둑판 형태로 만든 배열
• 하나의 원소는 두개의 첨자 i와 j의 쌍으로 구분됨 → A[i][j]
  • 행(row): 첨자 i에 해당하는 것
  • 열(column): 첨자 j에 해당하는 것

🔸2차원 배열 저장 순서

• 열 우선 순서 저장
  • 첫 열에 있는 각 행의 원소를 차례대로 컴퓨터 메모리에 저장하고 다음 열로 이동하여 각 행에 있는 원소를 차례대로 컴퓨터 메모리에 저장하는 방법

• 행 우선 순서 저장
  • 첫 행에 있는 각 열의 원소를 차례대로 컴퓨터 메모리에 저장하고 다음 행으로 이동하여 각 열에 있는 원소부터 차례대로 컴퓨터 메모리에 저장하는 방법

🔸희소행렬(spare matrix)

• 원소 값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬
• 0값을 저장하기 위해 컴퓨터 메모리의 낭비를 막고, 처리의 효율성을 높이기 위해 사용
• 희소 행렬의 0인 원소는 따로 저장하지 않고, 0이 아닌 값만 따로 모아서 저장하는 방법
• 0이 아닌 원소를 (행 번호, 열 번호, 원소 값)의 형태로 나타내면 2차원 배열로 표현 가능함

3. 리스트

✅ 선형 리스트(linear list)

• 순서 리스트(ordered list)라고도 함
• 1개 이상의 원소들이 순서를 가지고 구성됨
• A = (a₁, a₂, ..., aᵢ, ..., aₙ)와 같이 표시
  • aᵢ는 i번째 원소를 나타냄
  • aₙ의 n은 리스트의 크기가 됨
• 예1) 요일 리스트: (월, 화, 수, 목, 금, 토, 일)
• 예2) 전쟁 리스트: ((황산벌 전투, 660), (임진왜란, 1592), (세계 1차 대전, 1914), (세계 2차 대전, 1939))

🔸선형 리스트의 구현1(배열을 통한 구현)

• 선형 리스트와 1차원 배열은 순차적인 구조를 가지고 있으므로 1차원 배열로 간단하게 표현할 수 있음
• 원소 삽입
  • 삽입될 위치 이후의 원소들의 순서를 그대로 유지하면서 원소를 삽입해야 함
  • 그래서 삽입할 위치에 있는 원소와 그  다음에 위치한 원소들을 모두 한 칸 씩 뒤로 이동시킴
• 원소 삭제
  • 삭제할 원소를 찾아 삭제한 후, 그 뒤에 있는 모든 원소들을 한 칸 씩 앞으로 이동시킴

🔸선형 리스트의 구현2(연결 리스트(linked list))

• 노드 간의 포인터 연결을 통해서 구현됨
• 각 노드는 적어도 두 종류의 필드(원소 값을 저장하는 데이터 필드/노드 연결을 위한 링크 필드)를 가짐
• 선형 리스트의 논리적 순서만을 지원함
• 포인터만 변경 시키면 되기 때문에 쉽게 연산 가능

🔸연결 리스트 종류

• 단일 연결 리스트(singly linked list)
  • 특정 노드의 링크 필드를 사용해서 후행 노드를 가리킴
  • 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 선행 노드에 대한 접근은 헤드노드부터 새로 시작해야 함
• 이중 연결 리스트(doubly linked list)
  • 첫번째 링크는 후행 노드를 가리키고 두번째 링크는 선행 노드를 가리킴
  • 특정 노드에서 후행 노드 뿐만 아니라 선행 노드에 대한 접근을 쉽게 제공하기 위한 것
  • 메모리 추가적으로 들겠지만 연산은 조금 더 빨라짐

4. 스택과 큐

✅ 스택(Stack)

• 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어지는 자료구조
• 가장 먼저 입력된 데이터가 가장 나중에 제거되는 선입후출(FILO, First-In-Last-Out) 특징을 가짐 (=LIFO, Last-In-First-Out)

🔸스택의 연산

• 삽입 연산: push
• 삭제 연산: pop
• 스택 오버플로(overflow)
  • 삽입 연산을 수행할 때 발생
  • 스택을 위해 할당된 저장 공간을 초과해서 더 이상 데이터를 삽입할 수 없는 현상
• 스택 언더플로(underflow)
  • 삭제 연산을 수행할 때 발생
  • 스택에 데이터가 존재하지 않으면 삭제가 일어나지 않는 현상

✅ 큐(Queue)

• 선형 리스트의 한쪽 끝에서는 데이터의 삭제만 이루어지고, 다른 한쪽 끝에서는 데이터의 삽입만 이루어지는 자료구조
• 가장 먼저 입력된 데이터가 가장 먼저 제거되는 선입선출(FIFO, First-In-First-Out) 특징을 가짐

🔸큐의 연산

• 삽입 연산: enqueue
• 삭제 연산: dequeue
• 오버플로(overflow)
  • 삽입 연산을 수행할 때 발생
  • 큐를 위해 할당된 저장 공간을 초과해서 더 이상 데이터를 삽입할 수 없는 현상
• 언더플로(underflow)
  • 삭제 연산을 수행할 때 발생
  • 큐에 데이터가 존재하지 않으면 삭제가 일어나지 않는 현상

🔸큐의 만원 상태

• 만원 상태
  • 데이터가 큐에 삽입됨에 따라 rear 변수 값이 증가하다가 n-1이 되면 더 이상 데이터가 삽입될 수 없는 상태가 됨. 하지만 이 경우가 반드시 큐에 n개의 항목이 가득 차 있다는 것을 의미하는 것은 아님

=> 큐가 가득 채워진 상태를 결정하기 위한 다른 방법이 필요함