데이터 구조
데이터 구조 정의
- 데이터 값의 모임으로 각 원소들이 논리적으로 정의된 규칙에 의해 나열된 구조이다.
데이터 구조 목적
- 자료에 대한 처리를 효율적으로 할 수 있도록 자료를 구분하여 표현하는 것이다.
필요성
- 예를 들어, 새로 유입된 고객의 정보를 DB에 저장한다고 가정해보자.
- 가장 먼저 생각할 수 있는 방법은 DB 전체를 순회하면서 고객을 찾은 뒤 업데이트를 하는 방법이 있을 것이다.
- 하지만 이 방법은 매 업데이트마다 전체 DB를 순회하기에 데이터의 양에 따라 기하 급수적으로 시간이 증가할 것이다.
- 또 다른 방법으로는 해시 테이블을 사용하는 것이다. 해시 테이블은 Key, Value로 데이터를 저장하는 자료 구조 중 하나로 O(1)의 시간 복잡도를 가지기에 빠르게 데이터를 검색할 수 있다.
- 하지만 이것 만으로는 완벽하지 않기에 연결 리스트를 사용한다.
- 연결 리스트는 각 데이터를 노드로 표현하는 것으로 그 노드 안에 다음 노드의 위치 정보를 같이 저장한다.
- 이렇게 함으로써, 배열처럼 전체 데이터를 이동 시키지 않고, 특정 노드(데이터)의 다음 위치 정보를 수정하는 식으로 삽입하거나 삭제할 수 있다는 장점이 있다. → 즉 데이터 추가/삽입에 용이함. 하지만 데이터 탐색에는 적합하지 않음
- 데이터 탐색도 빠르게 하기 위해 추가적으로 이진 탐색 알고리즘을 통해 찾는 탐색하는 것도 효율적으로 해줄 수 있다.
배열
배열의 정의
- 같은 타입의 변수들로 이루어진 유한 집합
-
배열을 구성하는 각각의 값을 배열 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 한다.
배열의 장단점
- 장점
- 구현이 쉽다.
- 인덱스를 이용하여 빠른 접근이 가능(검색 성능이 좋다).
- 데이터의 크기가 확정적일 때 배열을 사용하는 것이 메모리나 처리 속도 면에서 효율적이다.
- 메모리 공간이 연속적이기에 시스템 레벨에서 처리와 관리하기 편하다.
- 단점
- 삽입 삭제가 어렵고 오래 걸린다.
- 중간의 요소를 삽입하거나 삭제하면 다음의 모든 요소를 이동 시켜야 한다.
- 그러므로 자료의 수에 비례하여 성능이 떨어지게 된다.
- 배열의 크기를 바꿀 수 없다.
- 크게 잡을 경우 메모리가 낭비되고, 작게 잡을 경우 그 이상의 자료를 저장하지 못한다.
- 배열은 초기 사이즈만큼의 메모리를 할당받아 사용하기에 데이터의 존재 유무와 관계없이 그 만큼의 메모리를 사용한다.
- 삽입 삭제가 어렵고 오래 걸린다.
배열의 구성
- 배열명($V$): 배열 전체를 일컫는 기호
- 배열 크기($N$): 원소를 저장하는 셀들의 개수
- 배열 첨자($i$): 셀의 순위(상대적 위치, 시작은 0(Lower bound), 끝은 $N-1$(Upper bound)) == 인덱스
- 배열 원소($V[i]$): 배열 $V$의 $i$에 저장된 원소
- 배열 표시($V[LB..UP]$)
배열의 메모리 할당
- 일차원 배열의 메모리 할당
- 컴파일 시, 배열의 셀들은 base라 불리는 배열의 첫째 셀 위치부터 시작하여 차례로 할당한다.
- 각 셀은 베이스로부터 오프셋만큼 떨어져 있다.
- offset은 시작점이나 기준점으로부터 특정 요소까지의 위치 또는 거리를 나타내는 값이다.
- 예를 들어 $V[3:10]$이 있을 때, $V[7]$의 오프셋은 4(index - base==7 - 3)이다.
다차원 배열
다차원 배열 정의
- 2차원 이상의 배열을 의미하며, 배열 요소로 또 다른 배열을 가지는 배열을 의미한다.
- n차원 배열은 배열 요소로 n-1차원 배열을 가지는 배열
다차원 배열 구성
- 배열 크기 : 각 차원의 곱(모든 요소의 개수)
- 배열 첨자( $i_{1}, i_{2},…, i_{n}$:) 각 차원에서의 방의 순위(즉, 상대적 위치)
- 시작: 0,0,…0, 또는 $LB_{0}, LB_{1}, …., LB_{n}$
- 끝: $N_{1}-1, N_{1}-1, … ,N_{n}-1$ 또는 $UB_{0}, UB_{1}, … , UB_{n}$
- 배열 원소($V[i_{1}, i_2, … i_n]$): 배열 첨자들에 저장된 원소
- 배열 표시
- LB=0이면, $V[N_0 \times N_1 \times … \times N_N]$
- 일반적으로 $V[LB_1…UP_1, LB_2…UB_2, …, LB_n…UB_n]$
다차원 배열의 메모리 할당
- 2차원 메모리 할당 크기
- 우선 기본적으로 배열은 행 우선 순서(또는 저차원 우선 순서)로 저장한다.
-
2차원 배열에서의 offset구하기
- $k_1 - LB_1$ : 몇 번째 행인지 확인(상위 차원의 거리 계산)
- $UB_2 - LB_2 + 1:$ 한 행에 몇 개의 열이 있는지 확인
- $k_2 - LB_2$: 해당 행의 몇 번째 열에 위치했는지 확인
-
3차원 배열의 표현(offset 계산)
응용 문제
- 1차원 배열과 다차원 배열의 메모리 할당 방식의 차이
- 1차원 배열
- 연속적인 메모리 위치에 할당
- 배열의 각 요소에 단일 인덱스로 접근 가능(인덱스 = 시작주소로 부터의 offset)
- 배열의 시작 주소에서 offset을 더함으로 각 요소의 메모리 주소 계산 가능
- 메모리 관리가 비교적 단순
- 다차원 배열
- 행렬과 유사한 형태로 메모리에 할당
- 행 또는 열 우선 순서로 메모리에 할당 될 수 있음
- 다 수의 인덱스를 사용하여 메모리에 접근
- 1차원 배열
- 배열의 위치 바꿈
// 수도 코드
Alg main
Input:
integer n, m
array ls of size n
array switch_index of size m
Output:
array ls after switching
tmp ← ls[switch_index[0]]
for i ← 1 to m - 1
tmp2 ← ls[switch_index[i]]
ls[switch_index[i]] ← tmp
tmp ← tmp2
// c 코드
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#pragma warning(disable:4996)
int main() {
int n;
int ls[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &ls[i]);
}
int m;
scanf("%d", &m);
int* nums = (int*)malloc(sizeof(int) * m);
for (int i = 0; i < m; i++) {
scanf("%d", &nums[i]);
}
int tmp = ls[nums[0]];
for (int i = 1; i < m; i++) {
int tmp2 = ls[nums[i]];
ls[nums[i]] = tmp;
tmp = tmp2;
}
for (int i = 0; i < n; i++) {
printf(" %d", ls[i]);
}
return 0;
}
- 대각선 방향으로 배열 채우기
// 수도 코드
Alg main
Input integer n, m // 행렬의 행의 크기와 열의 크기
Output array ls // 대각선 방향으로 채운 배열
val <- 1
ls <- array[n][m]
// 대각 원소 포함 윗부분 채우기
for i <- 0 to m-1
now_row <- 0
now_col <- i
while(now_col >= 0 && now_row < n)
ls[now_row][now_col] <- val
val <- val + 1
now_row <- now_row + 1
now_col <- now_col + 1
// 나머지 아래 부분 채우기
for i <- 1 to n - 1
now_row <- i
now_col <- m - 1
while(now_row < n && now_col >= 0)
ls[now_row][now_col] <- val
val <- val + 1
now_row <- now_row + 1
now_col <- now_col - 1
// c 코드
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#pragma warning(disable:4996)
int main() {
int n, m;
int ls[100][100];
scanf("%d %d", &n, &m);
int cnt = 1;
for (int i = 0; i < m; i++) {
int i1 = i;
int j = 0;
while (i1 >= 0 && j < n) {
ls[j][i1] = cnt;
cnt++;
i1--;
j++;
}
}
for (int i = 1; i < n; i++) {
int i1 = i;
int j = m - 1;
while (i1 < n && j >= 0) {
ls[i1][j] = cnt;
cnt++;
i1++;
j--;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
printf(" %d", ls[i][j]);
}
printf("\n");
}
return 0;
}
PREVIOUS[자료구조] 스택(Stack)과 큐(Queue)