자료구조 개념, 시간복잡도, 배열

이제 C 문법에서 자료구조로 넘어갑니다.

2장 4절까지는 C에서 데이터를 저장하는 도구를 배웠습니다.

변수 = 값 하나 저장
배열 = 같은 자료형 여러 개 저장
포인터 = 주소 저장
구조체 = 서로 다른 자료형 묶기

3장 1절부터는 질문이 바뀝니다.

데이터를 어떻게 저장해야 빠르게 찾고, 넣고, 지울 수 있을까요?

이것이 바로 자료구조입니다.

이번 절 내용은 자료구조 출제범위 중 자료구조와 알고리즘, 추상 자료형, 성능 분석, 공간 복잡도, 시간 복잡도, 배열, 순서리스트, 다차원 배열의 행우선과 열우선, 행렬 표현, 희소 행렬, 전치 행렬에 해당합니다. 또 배열은 C프로그래밍의 1차원 배열, 문자열, 다차원 배열, 포인터와 배열 개념과 직접 연결됩니다.

이번 절의 큰 그림

이번 절의 학습 흐름은 다음과 같습니다.

자료구조란 무엇인가
→ 알고리즘이란 무엇인가
→ 좋은 알고리즘을 어떻게 판단하는가
→ 시간복잡도와 공간복잡도
→ 배열의 구조
→ 순서리스트
→ 다차원 배열
→ 행렬과 희소 행렬

자료구조는 단순히 “자료를 저장하는 방법”이 아닙니다.

정확히는: 자료구조는 데이터를 효율적으로 저장하고, 탐색하고, 삽입하고, 삭제하기 위한 구조입니다.

예를 들어 100명의 학생 점수를 저장한다고 가정하겠습니다.

방법은 여러 가지입니다.

배열에 저장
연결리스트에 저장
트리에 저장
해시테이블에 저장

각 방법은 장단점이 다릅니다.

이번 절에서는 이 중에서 자료구조의 기본 개념과 배열을 잡습니다.

자료구조와 알고리즘 기본

자료란?

자료는 컴퓨터가 처리하는 값입니다.

학생 이름
학번
점수
회원 ID
비밀번호
게시글
댓글
사진
파일

C언어로 보면 이런 것들입니다.

int score = 90;
char name[20] = "Kim";
float height = 175.5;

자료 하나만 있으면 단순합니다. 문제는 자료가 많아질 때입니다.

학생 1명 → 변수 몇 개면 충분
학생 100명 → 배열이나 구조체 배열 필요
학생 100만 명 → 검색, 정렬, 저장 방식이 중요

자료가 많아지면 어떻게 정리하느냐가 성능을 좌우합니다.

자료구조란?

자료구조는 자료를 저장하는 방식입니다.

정의: 자료구조는 자료를 효율적으로 표현하고 저장하고 처리하기 위한 논리적·물리적 구조입니다.

자료구조 = 데이터를 정리하는 방법

예를 들어 책을 정리한다고 가정하겠습니다.

책을 그냥 바닥에 쌓아둡니다.

책장을 만들고 분야별로 정리합니다.

도서관처럼 번호를 붙이고 검색 시스템을 만듭니다.

책은 같지만 정리 방식이 다릅니다. 정리 방식이 다르면 찾는 속도도 달라집니다.

컴퓨터의 자료도 마찬가지입니다.

데이터는 같아도 자료구조가 다르면 성능이 달라집니다.

자료구조의 종류

자료구조는 크게 두 가지로 나눌 수 있습니다.

선형 자료구조
비선형 자료구조

선형 자료구조

데이터가 한 줄로 이어진 구조입니다.

A → B → C → D

대표 예는 다음과 같습니다.

자료구조 범위에도 배열, 스택, 큐, 연결 리스트가 주요 항목으로 포함되어 있습니다.

비선형 자료구조

데이터가 한 줄이 아니라 가지처럼 퍼지거나 복잡하게 연결된 구조입니다.

대표 예는 다음과 같습니다.

트리와 그래프도 자료구조 출제범위의 핵심 항목입니다. 이산수학에서도 그래프와 트리를 다룹니다.

논리적 구조와 물리적 구조

자료구조를 볼 때는 두 관점이 있습니다.

논리적 구조
물리적 구조

논리적 구조

논리적 구조는 사람이 생각하는 데이터의 관계입니다.

학생들이 번호 순서대로 있습니다.
부모와 자식 관계가 있습니다.
친구 관계가 연결되어 있습니다.

물리적 구조

물리적 구조는 실제 메모리에 어떻게 저장되는가입니다.

연속된 메모리 공간에 저장
포인터로 떨어진 공간을 연결

배열은 메모리에 연속적으로 저장됩니다.

arr[0] arr[1] arr[2] arr[3]

연결리스트는 메모리 여기저기에 있는 노드를 포인터로 연결합니다.

노드1 → 노드2 → 노드3

논리적 구조 = 사람이 보는 관계
물리적 구조 = 컴퓨터 메모리에 저장되는 방식

알고리즘이란?

자료구조가 “데이터를 담는 그릇”이라면, 알고리즘은 “문제를 푸는 절차”입니다.

정의: 알고리즘은 어떤 문제를 해결하기 위한 명확한 단계적 절차입니다.

예를 들어 라면 끓이는 방법도 알고리즘처럼 볼 수 있습니다.

1. 물을 끓입니다.
2. 면을 넣습니다.
3. 스프를 넣습니다.
4. 4분 기다립니다.
5. 먹습니다.

1. 학생 점수 배열을 처음부터 끝까지 봅니다.
2. 가장 큰 점수를 저장합니다.
3. 더 큰 점수를 만나면 갱신합니다.
4. 끝까지 본 뒤 가장 큰 점수를 출력합니다.

자료구조 범위에도 알고리즘의 정의와 조건, 성능 분석이 포함되어 있습니다. 이산수학 범위에도 알고리즘 표현과 알고리즘 분석이 들어 있습니다.

알고리즘의 조건

좋은 알고리즘은 보통 다음 조건을 만족해야 합니다.

중요한 것은 유한성입니다.

알고리즘은 반드시 끝나야 합니다.

끝나지 않는 반복문은 알고리즘으로 적절하지 않습니다.

while (1) {
    printf("Hello");
}

이것은 종료 조건이 없으면 계속 반복됩니다. 문제를 해결하는 알고리즘이라기보다 무한 반복입니다.

추상 자료형, ADT

이제 중요한 개념이 나옵니다.

추상 자료형은 영어로 ADT, Abstract Data Type이라고 합니다.

정의: 추상 자료형은 자료의 집합과 그 자료에 대한 연산을 명세한 것입니다.

말이 어렵습니다.

무엇을 저장할 수 있고,
어떤 동작을 할 수 있는지만 정한 설계도

예를 들어 스택이라는 자료구조를 생각해 보겠습니다.

push = 넣기
pop = 꺼내기
peek = 맨 위 보기
isEmpty = 비었는지 확인

이런 연산이 있다는 것을 정하는 것이 ADT다.

하지만 실제로 배열로 만들지, 연결리스트로 만들지는 아직 정하지 않습니다.

ADT = 기능 명세
구현 = 실제 코드

자료구조 예시문제에서도 “자료의 복잡한 논리적 성격을 정의하는 형식으로 자료의 집합과 연산 집합에 대한 명세”를 묻고, 정답은 추상 자료형입니다.

ADT와 구현의 차이

스택을 예로 들자.

ADT 관점

스택은 push, pop 연산을 가집니다.
마지막에 들어간 데이터가 먼저 나옵니다.

이것이 추상 자료형입니다.

구현 관점

배열로 만들 수도 있습니다.

int stack[100];
int top = -1;

연결리스트로 만들 수도 있습니다.

struct Node {
    int data;
    struct Node *next;
};

즉 같은 ADT라도 구현 방법은 여러 가지입니다.

ADT = 무엇을 할 수 있는가
구현 = 어떻게 만들 것인가

이 차이를 알아야 자료구조가 쉬워집니다.

성능 분석

성능 분석이 필요한 이유

같은 문제도 여러 방법으로 풀 수 있습니다.

예를 들어 배열에서 어떤 숫자 x를 찾는다고 가정하겠습니다.

앞에서부터 하나씩 찾습니다.

정렬된 배열에서 가운데를 기준으로 반씩 줄여 찾습니다.

둘 다 답을 찾을 수 있습니다.

그런데 데이터가 10개일 때는 별 차이 없습니다. 하지만 데이터가 100만 개면 차이가 엄청 커집니다.

그래서 알고리즘의 성능을 분석해야 합니다.

성능은 보통 두 가지로 봅니다.

자료구조 출제범위에도 공간 복잡도, 시간 복잡도, 연산 시간 표기법, 실용적인 복잡도가 포함되어 있습니다.

시간 복잡도란?

시간 복잡도는 입력 크기가 커질 때 실행 시간이 얼마나 늘어나는지를 나타냅니다.

여기서 입력 크기를 보통 n이라고 합니다.

학생 수 n명
배열 크기 n개
문자열 길이 n

시간 복잡도는 실제 초 단위 시간이 아닙니다.

컴퓨터 A에서는 1초
컴퓨터 B에서는 0.5초

이렇게 컴퓨터 성능에 따라 달라질 수 있기 때문입니다.

그래서 보통 연산 횟수가 n에 따라 어떻게 증가하는지를 봅니다.

Big-O 표기법

시간 복잡도는 보통 Big-O 표기법으로 씁니다.

O(1)
O(log n)
O(n)
O(n log n)
O(n²)
O(2ⁿ)

O(1) = 오 원
O(n) = 오 엔
O(n²) = 오 엔 제곱

Big-O는 대략적인 증가 속도를 나타냅니다.

중요한 순서는 다음과 같습니다.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

왼쪽이 빠르고, 오른쪽으로 갈수록 느립니다.

O(1): 상수 시간

O(1)은 입력 크기와 상관없이 시간이 거의 일정한 경우입니다.

int arr[100] = {0};

printf("%d", arr[3]);

배열에서 arr[3]에 접근하는 것은 바로 가능합니다.

배열 크기가 10개든 100만 개든, 인덱스만 알면 바로 갑니다.

배열 인덱스 접근 = O(1)

이것이 배열의 큰 장점입니다.

O(n): 선형 시간

O(n)은 입력 크기에 비례해서 시간이 늘어나는 경우입니다.

int i;
int sum = 0;

for (i = 0; i < n; i++) {
    sum += arr[i];
}

배열 원소 n개를 전부 한 번씩 봅니다.

n이 10이면 10번, n이 100이면 100번, n이 100만이면 100만 번 정도 반복됩니다.

전체 원소 한 번씩 보기 = O(n)

O(n²): 제곱 시간

중첩 반복문이 대표적입니다.

int i, j;

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        printf("*");
    }
}

바깥 반복문이 n번, 안쪽 반복문도 n번 반복됩니다.

n × n = n²

O(n²)

정렬 중에서 버블 정렬, 선택 정렬, 삽입 정렬의 평균적인 비교 횟수는 보통 O(n²)로 설명합니다. 정렬은 자료구조의 탐색과 정렬 범위에서 다시 다룹니다.

O(log n): 로그 시간

O(log n)은 문제 크기가 매번 절반 정도로 줄어드는 경우에 나옵니다.

대표 예는 이진 탐색입니다.

가운데를 봅니다.
찾는 값이 작으면 왼쪽 절반만 봅니다.
크면 오른쪽 절반만 봅니다.
다시 가운데를 봅니다.

데이터가 100만 개여도 절반씩 줄이면 금방 줄어듭니다.

1,000,000
→ 500,000
→ 250,000
→ 125,000
→ ...

그래서 O(n)보다 훨씬 빠릅니다.

이진 탐색은 자료구조의 탐색 범위에서 다시 다룹니다.

자주 나오는 시간 복잡도 표

처음에는 이 정도만 외워도 충분합니다.

시험에서는 보통 코드를 주고 반복문 구조를 보고 시간 복잡도를 묻습니다.

시간 복잡도 계산 예제 1

for (i = 0; i < n; i++) {
    printf("%d", i);
}

반복문이 n번 반복됩니다.

O(n)

시간 복잡도 계산 예제 2

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        printf("%d", i + j);
    }
}

바깥 n번, 안쪽 n번.

n × n = n²

O(n²)

시간 복잡도 계산 예제 3

printf("%d", arr[5]);

배열의 특정 위치에 바로 접근합니다.

O(1)

시간 복잡도 계산 예제 4

for (i = 1; i < n; i *= 2) {
    printf("%d", i);
}

i가 이렇게 변합니다.

1, 2, 4, 8, 16, 32, ...

매번 2배가 됩니다.

n에 도달할 때까지 몇 번 걸릴까?

2를 몇 번 곱해야 n이 되는가

이것이 로그입니다.

O(log n)

공간 복잡도란?

공간 복잡도는 알고리즘이 메모리를 얼마나 사용하는지 나타냅니다.

int sum = 0;

변수 하나만 추가로 쓴다면 공간은 거의 일정합니다.

O(1)

int temp[n];

추가 공간이 n개 필요합니다.

O(n)

시간이 빠른 알고리즘이 항상 좋은 것은 아닙니다. 메모리를 너무 많이 쓰면 문제가 될 수 있습니다.

시간과 공간의 균형

알고리즘에서는 종종 시간과 공간이 trade-off 관계입니다.

시간을 줄이려고 메모리를 더 씁니다.
메모리를 아끼려고 시간이 더 걸립니다.

예를 들어 어떤 값을 빠르게 찾기 위해 해시테이블을 만들면 검색은 빨라질 수 있습니다.

하지만 해시테이블을 저장할 추가 메모리가 필요합니다.

자료구조를 잘 고른다는 것은 결국 이 균형을 잘 잡는 것입니다.

배열과 순서리스트

배열 다시 보기

이제 이번 절의 핵심 자료구조인 배열로 들어갑니다.

배열은 같은 자료형의 데이터를 연속된 메모리 공간에 저장하는 구조입니다.

int arr[5] = {10, 20, 30, 40, 50};

메모리에서는 대략 이렇게 저장됩니다.

arr[0] arr[1] arr[2] arr[3] arr[4]
 10     20     30     40     50

배열의 특징은 다음과 같습니다.

배열의 장점

배열의 가장 큰 장점은 임의 접근입니다.

임의 접근은 원하는 위치에 바로 접근할 수 있다는 뜻입니다.

arr[3]

이렇게 쓰면 네 번째 원소에 바로 갑니다.

배열 크기가 5든 500만이든 인덱스 계산으로 위치를 바로 찾을 수 있습니다.

배열 접근 시간 = O(1)

이것이 배열의 가장 큰 장점입니다.

배열의 단점

배열은 중간 삽입과 삭제가 불편합니다.

예를 들어 배열이 이렇게 있다고 가정하겠습니다.

[10, 20, 30, 40, 50]

여기서 20과 30 사이에 25를 넣고 싶습니다.

[10, 20, 25, 30, 40, 50]

그러려면 30, 40, 50을 한 칸씩 뒤로 밀어야 합니다.

30 이동
40 이동
50 이동

데이터가 많으면 많이 밀어야 합니다.

그래서 배열 중간 삽입은 보통 O(n)입니다.

삭제도 마찬가지입니다.

[10, 20, 30, 40, 50]

[10, 30, 40, 50]

30, 40, 50을 한 칸씩 앞으로 당겨야 합니다.

그래서 배열 중간 삭제도 보통 O(n)입니다.

배열 연산의 시간 복잡도

찾는 위치를 알 때는 빠릅니다.
중간에 넣고 지울 때는 느릴 수 있습니다.

순서리스트란?

자료구조에서 리스트는 원소들이 순서를 가지고 나열된 구조입니다.

[10, 20, 30, 40]

순서리스트는 보통 배열을 이용해 리스트를 구현한 것입니다.

순서리스트 = 배열 기반 리스트

특징은 다음과 같습니다.

자료구조 범위에도 배열 단원 안에 순서리스트가 포함되어 있습니다.

순서리스트 삽입

배열 기반 순서리스트가 있다고 가정하겠습니다.

[10, 20, 30, 40, _]

현재 원소는 4개이고, 빈칸이 하나 있습니다.

20과 30 사이에 25를 넣고 싶습니다.

인덱스: 0   1   2   3   4
값:    10  20  30  40  _

25를 인덱스 2에 넣으려면, 뒤 원소를 뒤로 밀어야 합니다.

40을 인덱스 4로 이동

30을 인덱스 3으로 이동

인덱스 2에 25 저장

[10, 20, 25, 30, 40]

삽입 위치 뒤의 원소들을 뒤로 이동시킵니다.

순서리스트 삭제

이번에는 삭제입니다.

[10, 20, 30, 40, 50]

인덱스 1의 20을 삭제하고 싶습니다.

삭제 후에는 뒤 원소들을 앞으로 당깁니다.

30 → 인덱스 1
40 → 인덱스 2
50 → 인덱스 3

[10, 30, 40, 50]

삭제 위치 뒤의 원소들을 앞으로 이동시킵니다.

그래서 중간 삭제는 O(n)입니다.

배열과 연결리스트 미리 비교

연결리스트는 3장 3절에서 자세히 배우지만, 배열과 비교를 미리 해두자.

배열은 “번호로 바로 찾기”가 강합니다. 연결리스트는 “중간에 끼워 넣기, 빼기”가 강합니다.

다차원 배열과 행렬

다차원 배열

2장 4절에서 2차원 배열을 잠깐 배웠습니다.

int matrix[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

논리적으로는 표처럼 보입니다.

하지만 컴퓨터 메모리는 기본적으로 한 줄입니다.

즉 2차원 배열도 실제 메모리에는 1차원처럼 저장됩니다.

문제는 어떤 순서로 저장하느냐입니다.

행 우선 저장
열 우선 저장

자료구조 범위에도 다차원 배열의 행우선과 열우선이 포함되어 있습니다.

행우선 저장

행우선 저장은 한 행을 먼저 다 저장하고 다음 행으로 넘어가는 방식입니다.

1 2 3
4 5 6

1, 2, 3, 4, 5, 6

0행 전체 → 1행 전체

C언어의 2차원 배열은 보통 행우선 방식으로 저장됩니다.

int matrix[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

matrix[0][0]
matrix[0][1]
matrix[0][2]
matrix[1][0]
matrix[1][1]
matrix[1][2]

열우선 저장

열우선 저장은 한 열을 먼저 다 저장하고 다음 열로 넘어가는 방식입니다.

1 2 3
4 5 6

1, 4, 2, 5, 3, 6

0열 전체 → 1열 전체 → 2열 전체

일부 언어에서는 열우선 저장을 사용합니다.

시험에서는 C가 무조건 무엇을 쓰는가보입니다, 행우선과 열우선의 차이를 이해하는 것이 중요합니다.

행우선 주소 계산

주소 계산은 처음엔 어렵지만 원리는 단순합니다.

2차원 배열이 있다고 가정하겠습니다.

int A[3][4];

이 배열은 3행 4열입니다.

행 개수 = 3
열 개수 = 4

각 원소가 4바이트이고, 시작 주소가 1000이라고 가정하겠습니다.

A[i][j]의 위치 = 시작주소 + (i × 열 개수 + j) × 원소크기

LOC(A[i][j]) = base + (i × columns + j) × w

여기서는 다음과 같습니다.

예를 들어 A[2][1]의 주소를 구해 보겠습니다.

base = 1000
columns = 4
w = 4
i = 2
j = 1

1000 + (2 × 4 + 1) × 4
= 1000 + 9 × 4
= 1000 + 36
= 1036

A[2][1]의 주소 = 1036

왜 i × 열 개수 + j인가?

A[3][4]는 이렇게 생겼습니다.

A[2][1]은 앞에 몇 개의 원소가 있을까요?

0행에 4개
1행에 4개
2행에서 1개 앞에 있음

2 × 4 + 1 = 9개

그래서 시작 주소에서 9칸 이동합니다.

1부터 시작하는 인덱스 공식

시험에서는 인덱스가 1부터 시작한다고 가정하는 문제가 나올 수도 있습니다.

예를 들어 A[1..m][1..n] 같은 형태입니다.

LOC(A[i][j]) = base + ((i - 1) × n + (j - 1)) × w

i × n + j

(i - 1) × n + (j - 1)

이 차이를 조심해야 합니다.

열우선 주소 계산

열우선은 열을 먼저 저장합니다.

```text title="행 개수가 rows일 때" LOC(A[i][j]) = base + (j × rows + i) × w

0부터 시작한다고 보면 그렇습니다.

예를 들어 `A[3][4]`에서 `A[2][1]`을 열우선으로 저장한다고 가정하겠습니다.

```text
base = 1000
rows = 3
w = 4
i = 2
j = 1

1000 + (1 × 3 + 2) × 4
= 1000 + 5 × 4
= 1020

행우선에서는 1036이었는데, 열우선에서는 1020입니다.

즉 저장 순서가 다르면 주소도 달라집니다.

행렬

자료구조에서 배열은 행렬을 표현하는 데 많이 쓰입니다.

행렬은 숫자를 행과 열로 배열한 것입니다.

1 2 3
4 5 6

C에서는 2차원 배열로 표현할 수 있습니다.

int A[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

행렬 연산에는 다음이 있습니다.

행렬 덧셈
행렬 곱셈
전치 행렬
희소 행렬 표현

자료구조 범위에도 배열의 응용으로 행렬 표현, 행렬 연산, 희소 행렬, 전치 행렬이 포함되어 있습니다.

행렬 덧셈

두 행렬을 더하려면 크기가 같아야 합니다.

A = 1 2
    3 4

B = 5 6
    7 8

A + B = 1+5  2+6
        3+7  4+8

6  8
10 12

C 코드로는 중첩 반복문을 씁니다.

for (i = 0; i < rows; i++) {
    for (j = 0; j < cols; j++) {
        C[i][j] = A[i][j] + B[i][j];
    }
}

시간 복잡도는?

rows × cols

O(n²)

전치 행렬

전치 행렬은 행과 열을 바꾼 행렬입니다.

A = 1 2 3
    4 5 6

A는 2행 3열입니다.

Aᵀ = 1 4
     2 5
     3 6

Aᵀ는 3행 2열이 됩니다.

A[i][j] → Aᵀ[j][i]

for (i = 0; i < rows; i++) {
    for (j = 0; j < cols; j++) {
        T[j][i] = A[i][j];
    }
}

행과 열을 서로 바꿉니다.

희소 행렬

희소 행렬은 0이 대부분인 행렬입니다.

0 0 0 7
0 0 0 0
0 5 0 0
0 0 0 0

전체 원소는 4 × 4 = 16개입니다.

하지만 0이 아닌 값은 2개뿐입니다.

7, 5

이런 행렬을 일반 2차원 배열로 저장하면 낭비가 큽니다.

0도 전부 저장해야 함

그래서 희소 행렬은 0이 아닌 값만 저장하는 방식이 효율적입니다.

희소 행렬의 3원소 표현

희소 행렬은 보통 3개 정보로 저장합니다.

행 번호, 열 번호, 값

0 0 0 7
0 0 0 0
0 5 0 0
0 0 0 0

0이 아닌 원소는 다음과 같습니다.

전체 정보까지 포함하면 보통 첫 줄에 행 개수, 열 개수, 0이 아닌 원소 개수를 저장합니다.

4행 4열, 0이 아닌 원소 2개

실제 0이 아닌 원소의 위치와 값

이렇게 하면 0을 전부 저장하지 않아도 됩니다.

희소 행렬의 전치

희소 행렬의 전치도 행과 열을 바꾸면 됩니다.

원래 표현은 다음과 같습니다.

전치하면 행과 열이 바뀝니다.

단, 보통은 row 순서대로 정렬해서 저장하는 경우가 많습니다.

정렬하면 다음과 같습니다.

자료구조에서 전치 행렬은 배열 응용의 대표 문제입니다.

배열 기반 자료구조의 핵심

배열은 뒤에서 배울 스택과 큐의 기본 구현으로도 사용됩니다.

배열로 스택 만들기

stack[0]
stack[1]
stack[2]
...

top 변수가 맨 위 위치를 가리킵니다.

배열로 큐 만들기

queue[0]
queue[1]
queue[2]
...

front, rear 변수가 앞과 뒤를 관리합니다.

즉 배열은 단순히 C 문법이 아니라 자료구조의 기초 재료입니다.

배열 → 스택
배열 → 큐
배열 → 힙
배열 → 행렬
배열 → 해시테이블

자주 혼동되는 출제 포인트

혼동 포인트 1. 자료구조와 알고리즘을 구분해야 합니다

자료구조 = 데이터를 저장하는 방식
알고리즘 = 문제를 해결하는 절차

혼동 포인트 2. ADT는 구현 코드가 아닙니다

ADT = 자료와 연산의 명세
구현 = 배열이나 포인터로 실제로 만드는 것

자료구조 예시문제에서 ADT의 정의가 직접 나옵니다.

혼동 포인트 3. Big-O는 정확한 실행 시간이 아닙니다

O(n)은 n초 걸린다는 뜻이 아닙니다.
입력 크기에 따라 연산 횟수가 선형으로 증가한다는 뜻입니다.

혼동 포인트 4. 이중 반복문은 보통 O(n²)

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        ...
    }
}

O(n²)

혼동 포인트 5. 배열 인덱스 접근은 O(1)

arr[100]

특정 위치를 바로 접근하므로 O(1)입니다.

혼동 포인트 6. 배열 중간 삽입/삭제는 O(n)

중간에 넣거나 지우면 뒤 원소들을 밀거나 당겨야 합니다.

혼동 포인트 7. C 배열은 행우선 저장

2차원 배열이 표처럼 보여도 실제 메모리에는 한 줄로 저장됩니다.

행우선 = 한 행을 먼저 저장

혼동 포인트 8. 전치 행렬은 행과 열을 바꾸는 것

A[i][j] → Aᵀ[j][i]

혼동 포인트 9. 희소 행렬은 0이 아닌 원소만 저장합니다

0이 대부분인 행렬은 0을 전부 저장하면 낭비가 큽니다.

이번 절의 핵심 정리

자료구조

데이터를 효율적으로 저장하고 처리하기 위한 구조

알고리즘

문제를 해결하기 위한 명확한 절차

추상 자료형, ADT

자료의 집합과 연산의 명세

시간 복잡도

입력 크기 n에 따라 실행 시간이 얼마나 증가하는가

공간 복잡도

입력 크기 n에 따라 메모리 사용량이 얼마나 증가하는가

Big-O 순서

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

배열

같은 자료형을 연속된 메모리에 저장
인덱스로 O(1) 접근
중간 삽입/삭제는 O(n)

행우선 저장

한 행을 먼저 저장하고 다음 행으로 이동

전치 행렬

행과 열을 바꿈
A[i][j] → T[j][i]

희소 행렬

0이 대부분인 행렬
0이 아닌 원소만 저장하면 효율적

핵심 한 문장

이번 절의 핵심을 한 문장으로 정리하면 다음과 같습니다.

자료구조는 데이터를 효율적으로 저장하는 방법이고, 알고리즘은 문제를 해결하는 절차이며, 배열은 연속된 메모리에 같은 자료형을 저장해 빠른 인덱스 접근을 제공하지만 중간 삽입과 삭제에는 불리합니다.

자료구조 = 저장 방법
알고리즘 = 해결 절차
시간복잡도 = 걸리는 시간의 증가량
배열 = 빠른 접근, 느린 중간 삽입/삭제

확인 문제

문제 1

자료구조의 의미로 가장 알맞은 것은?

① 프로그램을 실행하는 운영체제 ② 데이터를 효율적으로 저장하고 처리하기 위한 구조 ③ 컴퓨터의 전기 회로 ④ 화면 디자인을 만드는 방법

문제 2

알고리즘의 의미로 가장 알맞은 것은?

① 데이터를 저장하는 메모리 주소 ② 문제를 해결하기 위한 명확한 절차 ③ C언어의 예약어 ④ 웹페이지의 태그

문제 3

자료의 집합과 그 자료에 대한 연산 집합을 명세한 것은?

① 배열 ② 포인터 ③ 추상 자료형 ④ 반복문

문제 4

배열 arr[i]처럼 인덱스를 알고 특정 원소에 접근할 때의 시간 복잡도는?

① O(1) ② O(n) ③ O(n²) ④ O(2ⁿ)

문제 5

다음 코드의 시간 복잡도는?

for (i = 0; i < n; i++) {
    printf("%d", i);
}

① O(1) ② O(log n) ③ O(n) ④ O(n²)

문제 6

다음 코드의 시간 복잡도는?

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        printf("%d", i + j);
    }
}

① O(1) ② O(log n) ③ O(n) ④ O(n²)

문제 7

다음 코드의 시간 복잡도는?

for (i = 1; i < n; i *= 2) {
    printf("%d", i);
}

① O(1) ② O(log n) ③ O(n) ④ O(n²)

문제 8

배열의 가장 큰 장점으로 알맞은 것은?

① 중간 삽입이 항상 O(1)입니다 ② 중간 삭제가 항상 빠릅니다 ③ 인덱스를 이용해 특정 위치에 빠르게 접근할 수 있습니다 ④ 서로 다른 자료형을 자유롭게 섞어 저장합니다

문제 9

크기가 5인 C 배열 int arr[5];에서 사용 가능한 마지막 인덱스는?

① 4 ② 5 ③ 6 ④ 1

문제 10

C의 2차원 배열 저장 방식과 가장 가까운 것은?

① 열우선 저장 ② 행우선 저장 ③ 무작위 저장 ④ 해시 저장

문제 11

전치 행렬의 의미로 알맞은 것은?

① 모든 값을 0으로 바꾸는 행렬 ② 행과 열을 서로 바꾼 행렬 ③ 대각선 값만 저장한 행렬 ④ 가장 큰 값만 남긴 행렬

문제 12

희소 행렬의 특징으로 알맞은 것은?

① 모든 원소가 1인 행렬 ② 0이 대부분인 행렬 ③ 행과 열의 개수가 반드시 같은 행렬 ④ 문자열만 저장하는 행렬

정답과 해설은 절별 확인문제 정답해설에서 확인합니다.

다음 3장 2절은 스택, 큐, 후위표기식입니다. 3장 1절이 “자료구조의 기본 개념과 배열”이었다면, 3장 2절은 배열을 이용해서 실제로 많이 쓰는 스택과 큐를 다룹니다.