방송대 방통대 컴퓨터과학개론 3강 - 자료구조 (1) - 요약 노트 시험족보 예상문제 - 올에이클래스

컴퓨터과학개론 3강 - 자료구조 (1)

자료의 논리적 관계를 추상화하여 효율적으로 저장하고 처리하는 자료구조의 개념을 학습한다. 배열과 희소행렬, 선형 리스트와 연결 리스트, 스택과 큐의 구조·연산·메모리 표현을 비교하며 각 자료구조가 적합한 상황을 이해한다.

1. 자료구조와 추상화

정리되지 않은 도구함보다 종류와 용도에 따라 정돈된 도구함에서 필요한 물건을 더 빠르게 찾을 수 있다. 데이터도 마찬가지이다. 자료가 어떤 관계를 갖는지 파악하고 일정한 구조로 조직하면 저장, 검색, 삽입, 삭제와 같은 처리를 효율적으로 수행할 수 있다.

추상화(abstraction)는 서로 다른 구체적인 대상에서 공통적인 개념을 찾아 하나의 일반적인 형태로 정의하는 것이다. 버스의 세부 모양이 달라도 ‘승객을 운송하는 교통수단’이라는 공통 개념으로 바라보거나, 복잡한 노선도에서 실제 지형보다 역과 연결 관계를 중심으로 표현하는 것이 추상화의 예이다.

자료 추상화는 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 데이터의 구조에 주목하여 공통 특징을 뽑아내는 것이다. 현실의 자료가 가진 모든 세부 사항을 그대로 담는 대신, 문제 해결에 필요한 데이터와 그 논리적 관계를 선택한다.

자료구조(data structure)는 자료 추상화를 통해 데이터 사이의 논리적 관계를 구조화한 것이다.

자료구조가 적절하지 않으면 소프트웨어가 비효율적으로 개발되거나 실행될 수 있고, 프로그램의 확장성과 유지보수성에도 문제가 생길 수 있다. 처리할 자료가 복잡해질수록 자료구조 선택의 중요성은 더욱 커진다.

2. 자료구조의 종류와 관계

자료구조는 프로그래밍 언어에서 제공하는 미리 정의된 자료구조와 개발자가 필요에 따라 설계하는 사용자 정의 자료구조로 나눌 수 있다.

대분류	세부 분류	예
미리 정의된 자료구조	기본 자료구조	정수, 실수, 문자
	파생된 자료구조	배열, 구조체, 포인터
사용자 정의 자료구조	응용에 맞게 개발자가 정의	리스트, 스택, 큐, 트리, 그래프

미리 정의된 자료구조는 프로그래밍 언어가 제공하거나 설계·컴파일러 구현 단계에서 개발자에게 제공되는 형태이다. 사용자 정의 자료구조는 소프트웨어 개발자가 문제와 연산의 요구에 맞게 기본·파생 자료구조를 조합하여 만든다.

자료구조는 단순히 데이터를 담는 모양만 뜻하지 않는다. 데이터 사이의 관계, 접근 방법, 허용되는 연산까지 함께 이해해야 한다.

3. 배열의 개념과 1차원 배열

배열(array)은 동일한 자료형을 가진 여러 데이터를 하나의 변수 이름 아래에 일렬로 저장하는 자료 집합체이다. 각각의 데이터를 원소(element)라 하고, 원하는 원소의 위치를 지정하는 번호를 인덱스(index) 또는 첨자라 한다.

여러 학생의 점수를 score0, score1처럼 별도 변수에 저장하면 변수 수가 늘어날수록 관리하기 어렵다. 배열을 사용하면 score[0], score[1]처럼 하나의 이름과 인덱스로 같은 종류의 자료를 체계적으로 다룰 수 있다.

1차원 배열은 가장 단순한 배열로 한 개의 인덱스를 사용해 원소에 직접 접근한다. 원소들은 컴퓨터 메모리의 연속적인 기억장소에 순서대로 저장된다.

배열 A의 시작 주소를 α, 원소 하나의 크기를 k라고 하면 A[i]의 주소는 α + i×k이다.

요소	의미
α	배열 첫 원소 A[0]의 시작 주소
i	접근하려는 원소의 인덱스
k	배열 원소 하나가 차지하는 바이트 수
α+i×k	A[i]가 저장된 실제 메모리 주소

주소를 계산해 바로 접근할 수 있으므로 배열의 특정 원소 조회는 간단하다. 다만 배열의 크기와 연속된 저장공간이 필요하다는 제약이 있다.

4. 다차원 배열과 저장 순서

2차원 배열은 동일한 크기의 1차원 배열을 모아 바둑판 형태로 만든 배열이다. 원소는 행과 열을 나타내는 두 개의 첨자 A[i][j]로 구분한다. i는 행(row), j는 열(column)에 해당한다.

3차원 배열은 세 개의 첨자를 사용하는 배열이며 동일한 크기의 2차원 배열 여러 개가 겹쳐진 형태로 이해할 수 있다. 그러나 실제 컴퓨터 메모리는 일렬로 이어진 공간이므로 다차원 배열도 일정한 순서에 따라 선형으로 저장해야 한다.

저장 방식	방법	2×3 배열의 순서
행 우선 순서	첫 행의 원소를 차례대로 저장한 뒤 다음 행으로 이동	[0,0] → [0,1] → [0,2] → [1,0] → [1,1] → [1,2]
열 우선 순서	첫 열의 원소를 차례대로 저장한 뒤 다음 열로 이동	[0,0] → [1,0] → [0,1] → [1,1] → [0,2] → [1,2]

어떤 저장 순서를 사용하는지는 언어와 시스템의 규칙에 따라 정해진다. 같은 논리적 2차원 배열도 저장 순서에 따라 인접한 메모리 원소가 달라지므로 주소 계산과 처리 성능을 이해할 때 이를 구분해야 한다.

5. 희소행렬의 효율적 표현

희소행렬(sparse matrix)은 0이 아닌 원소보다 0인 원소가 상대적으로 훨씬 많은 행렬이다. 일반적인 2차원 배열로 표현하면 대부분의 저장공간이 값 0을 저장하는 데 사용되어 메모리가 낭비되고 처리 효율도 낮아질 수 있다.

효율적인 방법은 0인 원소를 저장하지 않고, 0이 아닌 원소만 따로 모아 각 원소를 (행 번호, 열 번호, 원소값) 형태로 기록하는 것이다.

행	열	값
0	1	20
0	4	9
0	7	11
2	0	78
3	4	67

실제 강의 예제처럼 큰 행렬에서 0이 아닌 값이 소수라면 이 표현은 저장량을 크게 줄인다. 반대로 0이 아닌 원소가 많다면 행·열 번호를 함께 저장하는 비용 때문에 일반 배열보다 유리하지 않을 수 있다.

희소행렬 표현의 핵심은 ‘0을 저장하지 않는다’는 것이며, 0이 아닌 값의 위치와 값을 함께 보존해야 원래 행렬을 복원할 수 있다.

6. 선형 리스트와 배열 구현

선형 리스트(linear list)는 순서 리스트(ordered list)라고도 하며, 한 개 이상의 원소가 순서를 가지고 구성된 자료구조이다. 일반적으로 A=(a₁, a₂, …, aᵢ, …, aₙ)으로 나타내며 aᵢ는 i번째 원소, n은 리스트의 크기이다.

요일 리스트 (월, 화, 수, 목, 금, 토, 일), 원소의 순서가 중요한 전쟁 기록 목록 등이 선형 리스트의 예이다. 선형 리스트는 순차 구조이므로 1차원 배열로 간단하게 표현할 수 있다.

배열 구현은 원소가 메모리에 연속적으로 배치되어 인덱스로 빠르게 접근할 수 있다는 장점이 있다. 그러나 중간에 원소를 삽입하거나 삭제하면 순서를 유지하기 위해 많은 원소를 이동해야 한다.

연산	배열 구현에서 필요한 처리
중간 삽입	삽입 위치와 그 뒤의 원소들을 한 칸씩 뒤로 이동한 후 새 원소 저장
중간 삭제	원소를 삭제한 뒤 그 뒤의 모든 원소를 한 칸씩 앞으로 이동
인덱스 접근	주소 계산으로 원하는 위치에 직접 접근

배열은 조회에는 편리하지만 리스트 크기가 자주 변하거나 중간 삽입·삭제가 빈번한 경우 원소 이동 비용이 커질 수 있다.

7. 연결 리스트의 구조

연결 리스트(linked list)는 노드 사이의 포인터 연결로 선형 리스트를 구현한다. 각 노드는 원소값을 저장하는 데이터 필드와 다른 노드의 주소를 저장하는 링크 필드로 구성된다.

첫 노드의 위치는 head가 가리키며, 링크를 따라가면 논리적인 다음 원소에 접근할 수 있다. 노드들은 실제 메모리에서 서로 떨어져 있어도 포인터 연결로 리스트의 순서를 유지한다.

구분	링크 구조	특징
단일 연결 리스트	각 노드가 후행 노드를 가리키는 링크 하나를 가짐	다음 노드 접근은 쉽지만 선행 노드로 가려면 head부터 다시 탐색
이중 연결 리스트	각 노드가 선행·후행 노드를 가리키는 링크 두 개를 가짐	앞뒤 방향의 접근이 쉽지만 링크 저장공간과 관리가 더 필요

연결 리스트는 삽입·삭제 위치 주변의 링크만 조정하면 되므로 배열처럼 뒤의 모든 원소를 이동할 필요가 없다. 반면 특정 번째 원소에 접근하려면 첫 노드부터 링크를 따라가야 하며, 데이터 외에 링크를 위한 공간이 추가로 필요하다.

배열은 물리적으로 연속된 저장공간으로 논리 순서를 표현하고, 연결 리스트는 물리적 위치와 관계없이 포인터 연결로 논리 순서를 표현한다.

8. 스택의 구조와 연산

스택(stack)은 데이터의 삽입과 삭제가 한쪽 끝인 top에서만 이루어지는 자료구조이다. 가장 나중에 삽입한 데이터가 가장 먼저 삭제되므로 후입선출(LIFO, Last-In-First-Out) 구조라고 한다.

연산	기능
push	top 위치에 새 데이터를 삽입
pop	top에 있는 가장 최근 데이터를 삭제하고 반환
top	현재 가장 위의 원소 위치를 나타냄

A, B를 차례로 push한 뒤 pop을 수행하면 가장 최근에 넣은 B가 먼저 제거된다. 그 뒤 C와 D를 넣으면 위에서부터 D, C, A의 순서가 된다.

스택 오버플로(overflow)는 삽입 연산 중 할당된 저장공간을 초과하여 더 이상 데이터를 넣을 수 없는 현상이다. 스택 언더플로(underflow)는 스택에 데이터가 없는데 삭제 연산을 시도하여 pop이 일어나지 않는 현상이다.

스택의 핵심: 한쪽 끝에서 삽입·삭제, 마지막 입력이 첫 번째 출력

9. 큐의 구조와 연산

큐(queue)는 선형 리스트의 한쪽 끝에서 데이터를 삽입하고 다른 쪽 끝에서 삭제하는 자료구조이다. 가장 먼저 삽입한 데이터가 가장 먼저 제거되므로 선입선출(FIFO, First-In-First-Out) 구조라고 한다.

삭제가 일어나는 앞쪽 위치를 front, 삽입이 일어나는 뒤쪽 위치를 rear로 관리한다. 줄을 선 순서대로 버스를 타거나 정수기의 물이 들어온 순서대로 나가는 모습으로 이해할 수 있다.

연산·상태	설명
enqueue	rear 쪽에 데이터를 삽입
dequeue	front 쪽의 가장 오래된 데이터를 삭제
오버플로	할당된 저장공간을 초과하여 더 이상 삽입할 수 없는 상태
언더플로	데이터가 없는 큐에서 삭제를 시도한 상태

단순 배열 큐에서는 dequeue가 반복될수록 앞쪽에 빈 공간이 생길 수 있다. rear가 배열 끝에 도달했다고 해서 전체 큐가 반드시 가득 찬 것은 아니다. 강의에서 보여 준 ‘만원 상태’ 문제는 앞의 빈 공간을 재사용하지 못하는 단순 선형 큐의 한계를 의미하며, 큐가 실제 원소로 모두 채워졌다는 뜻은 아니다.

스택은 삽입과 삭제가 같은 끝에서 이루어지는 LIFO 구조이고, 큐는 서로 다른 끝에서 이루어지는 FIFO 구조이다.

10. 주요 자료구조 비교

자료구조	논리적 특징	주요 장점	주의점
배열	동일 자료형의 원소를 인덱스로 관리	직접 접근과 주소 계산이 간단함	크기와 연속 공간의 제약, 중간 삽입·삭제 비용
희소행렬 표현	0이 아닌 원소의 위치와 값만 저장	0이 많은 행렬의 공간 절약	0이 아닌 값이 많으면 효율 감소
배열 리스트	연속 메모리에 순서대로 저장	특정 위치 접근이 빠름	삽입·삭제 시 원소 이동
연결 리스트	노드를 링크로 연결	원소 이동 없이 링크 조정으로 삽입·삭제	순차 접근과 링크 공간 필요
스택	LIFO	최근 항목부터 처리하는 작업에 적합	top에서만 삽입·삭제
큐	FIFO	도착 순서대로 처리하는 작업에 적합	단순 배열 구현에서 앞쪽 빈 공간 문제

어떤 자료구조가 항상 가장 좋은 것은 아니다. 필요한 접근 방식, 삽입·삭제 빈도, 데이터 크기 변화, 메모리 사용량을 고려하여 문제에 맞는 구조를 선택해야 한다.

핵심 개념 정리

• 자료구조는 자료 사이의 논리적 관계를 추상화하고 구조화한 것이다.
• 자료구조는 미리 정의된 구조와 개발자가 만드는 사용자 정의 구조로 나눌 수 있다.
• 배열은 동일 자료형 원소를 연속 메모리에 저장하고 인덱스로 접근한다.
• 1차원 배열 A의 i번째 원소 주소는 시작 주소 α와 원소 크기 k를 이용해 α+i×k로 계산한다.
• 다차원 배열은 실제 메모리에서 행 우선 또는 열 우선 순서로 선형 저장된다.
• 희소행렬은 0이 아닌 원소를 (행, 열, 값)으로 저장하여 공간을 절약한다.
• 배열 리스트는 접근이 빠르지만 중간 삽입·삭제 시 원소 이동이 필요하다.
• 연결 리스트는 데이터 필드와 링크 필드를 가진 노드의 포인터 연결로 구성된다.
• 스택은 한쪽 끝에서 삽입·삭제하는 LIFO 구조이다.
• 큐는 rear에서 삽입하고 front에서 삭제하는 FIFO 구조이다.
• 할당 공간을 넘는 삽입은 오버플로, 빈 구조에서의 삭제는 언더플로를 일으킨다.

최종 정리: 자료구조는 데이터를 어떻게 저장할지뿐 아니라 어떤 연산을 얼마나 효율적으로 수행할지를 결정한다. 연속 공간과 인덱스를 활용하는 배열, 링크로 순서를 만드는 연결 리스트, 처리 순서를 제한하는 스택과 큐의 차이를 문제의 요구와 연결해 이해해야 한다.

예상문제 20선

1. 자료구조의 정의로 가장 알맞은 것은?

① 자료 추상화를 통해 자료의 논리적 관계를 구조화한 것② 모든 자료를 무작위로 저장한 것③ 프로그램의 출력 화면만을 뜻하는 것④ 데이터의 자료형을 모두 제거한 것

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
자료구조는 문제에 필요한 자료와 그 관계를 추상화하여 저장·처리에 적합한 구조로 만든 것이다.

2. 사용자 정의 자료구조에 해당하는 것은?

① 정수형② 스택③ 실수형④ 문자형

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
스택·큐·리스트·트리·그래프 등은 개발자가 목적에 맞게 구현하여 사용하는 자료구조이다.

3. 배열의 특징으로 옳은 것은?

① 서로 다른 모든 자료형만 저장한다.② 원소 이름을 모두 다르게 해야 한다.③ 동일 자료형의 여러 원소를 하나의 이름과 인덱스로 관리한다.④ 원소 사이에 순서가 존재하지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
배열은 같은 자료형의 원소를 연속적으로 저장하고 인덱스로 각 원소를 구분한다.

4. 시작 주소가 α이고 원소 크기가 k인 1차원 배열 A에서 A[i]의 주소는?

① α-k② i+k③ α×i+k④ α+i×k

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
첫 원소에서 i개의 원소 크기만큼 떨어져 있으므로 시작 주소에 i×k를 더한다.

5. 2차원 배열 A[i][j]에서 i와 j가 일반적으로 나타내는 것은?

① i는 행, j는 열② i는 열, j는 자료형③ i는 주소, j는 크기④ 둘 다 링크 필드

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
2차원 배열의 첫 첨자는 행, 두 번째 첨자는 열을 나타낸다.

6. 행 우선 순서 저장에 대한 설명은?

① 첫 열 전체를 저장한 뒤 다음 열로 이동한다.② 한 행의 원소를 차례로 저장한 뒤 다음 행으로 이동한다.③ 원소를 임의 순서로 저장한다.④ 대각선 원소만 저장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
행 우선은 첫 행을 왼쪽부터 저장한 다음 그다음 행을 같은 방식으로 저장한다.

7. 희소행렬의 특징은?

① 모든 원소가 0이 아니다.② 행과 열이 항상 하나씩이다.③ 0이 아닌 원소보다 0인 원소가 상대적으로 많다.④ 문자 데이터만 저장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
희소행렬은 대부분의 원소가 0인 행렬이므로 0을 제외한 효율적 표현을 사용할 수 있다.

8. 희소행렬의 0이 아닌 원소를 효율적으로 저장할 때 필요한 정보는?

① 값만② 행 번호만③ 열 번호만④ 행 번호·열 번호·원소값

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
원래 행렬의 위치와 값을 복원하려면 세 정보가 모두 필요하다.

9. 선형 리스트의 설명으로 옳은 것은?

① 한 개 이상의 원소가 순서를 가지고 구성된다.② 모든 원소 사이에 순서가 없다.③ 반드시 2차원 배열만 사용한다.④ 원소를 한 개만 저장할 수 있다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
선형 리스트는 첫째, 둘째와 같이 원소 사이에 선형적인 순서가 정의된 자료구조이다.

10. 배열로 구현한 선형 리스트의 중간에 원소를 삽입할 때 필요한 작업은?

① 모든 원소 삭제② 삽입 위치 이후 원소를 한 칸씩 뒤로 이동③ head 포인터만 변경④ top을 감소

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
배열의 연속된 순서를 유지하며 빈자리를 만들기 위해 뒤쪽 원소들을 이동해야 한다.

11. 연결 리스트의 노드를 구성하는 두 필드는?

① 행 필드와 열 필드② front와 rear③ 데이터 필드와 링크 필드④ 부호와 지수

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
노드는 원소값을 저장하는 데이터 필드와 다음 또는 이전 노드 주소를 담는 링크 필드로 구성된다.

12. 단일 연결 리스트의 특징은?

① 각 노드가 선행·후행 링크를 모두 가진다.② 원소들이 반드시 연속 주소에 있다.③ 어느 노드에서나 이전 노드로 즉시 갈 수 있다.④ 각 노드의 링크가 후행 노드를 가리킨다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
단일 연결 리스트는 다음 노드를 가리키는 링크 하나로 한 방향 연결을 만든다.

13. 이중 연결 리스트가 단일 연결 리스트보다 제공하는 기능은?

① 선행 노드와 후행 노드 양쪽으로 접근② 링크 필드 제거③ 모든 노드를 같은 주소에 저장④ 인덱스만으로 직접 접근

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
이중 연결 리스트의 노드는 이전과 다음 노드를 가리키는 링크를 모두 가져 양방향 이동이 쉽다.

14. 스택의 자료 처리 방식은?

① 선입선출② 후입선출③ 임의 접근만④ 열 우선 처리

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
스택은 가장 나중에 들어온 원소가 top에서 가장 먼저 나가는 LIFO 구조이다.

15. 스택에서 데이터를 삽입하는 연산은?

① dequeue② pop③ push④ fetch

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
push는 스택의 top에 새 원소를 넣는 연산이고 pop은 top 원소를 제거한다.

16. 빈 스택에서 pop을 시도할 때 발생하는 것은?

① 정규화② 오버플로③ 행 우선 저장④ 언더플로

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
삭제할 데이터가 없는 상태에서 삭제 연산을 시도하면 언더플로가 발생한다.

17. 큐의 자료 처리 방식은?

① 선입선출② 후입선출③ 큰 값 우선④ 마지막 주소 우선

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
큐는 먼저 들어온 데이터가 front에서 먼저 나가는 FIFO 구조이다.

18. 큐에서 삽입과 삭제가 일어나는 위치는?

① 둘 다 front② rear에서 삽입하고 front에서 삭제③ front에서 삽입하고 top에서 삭제④ 둘 다 임의 위치

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
큐는 뒤쪽 rear로 새 원소가 들어오고 앞쪽 front의 오래된 원소가 나간다.

19. 단순 배열 큐에서 rear가 배열 끝에 도달했을 때의 설명으로 옳은 것은?

① 큐가 항상 실제 원소로 완전히 찼다.② front는 반드시 첫 칸이다.③ 앞쪽에 삭제로 생긴 빈 공간이 남아 있을 수 있다.④ 모든 원소가 자동으로 앞으로 이동한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
선형 큐는 앞쪽 빈 공간을 재사용하지 못할 수 있으므로 rear가 끝이어도 전체 공간이 가득 찬 것은 아니다.

20. 배열과 연결 리스트의 비교로 옳은 것은?

① 연결 리스트의 노드는 반드시 연속 메모리에 저장된다.② 배열은 중간 삽입 시 원소 이동이 전혀 없다.③ 연결 리스트는 링크 저장공간이 필요 없다.④ 배열은 직접 접근에 유리하고 연결 리스트는 링크 조정으로 삽입·삭제하기 좋다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
배열은 인덱스 주소 계산이 가능하고, 연결 리스트는 주변 링크를 바꾸어 원소 이동 없이 삽입·삭제할 수 있다.