기본 콘텐츠로 건너뛰기

방송대 자료구조 1강 : 추상화와 자료구조·알고리즘의 관계

0-썸네일-요약노트-자료구조-1강

방송대 자료구조 1강: 추상화와 자료구조·알고리즘의 관계

같은 장비 대여 기록도 아무렇게나 쌓아 두면 연체자를 찾기 어렵고, 목적에 맞게 정리하면 필요한 답을 빠르게 얻을 수 있습니다. 이 글은 자료가 정보로 바뀌는 출발점부터 추상화, 자료구조와 알고리즘의 역할, 올바른 알고리즘의 조건과 시간·공간 성능 판단까지 하나의 문제 해결 흐름으로 연결합니다.

기록은 있는데 답을 얻지 못한다면 무엇부터 바꿔야 할까

학습을 위해 학과 장비 대여 기록을 생각해 보자. 각 기록에 장비 번호, 종류, 대여자, 대여일, 반납 예정일, 반납 여부가 적혀 있어도 종이가 뒤섞여 있다면 “오늘까지 반납하지 않은 노트북은 몇 대인가?”라는 질문에 바로 답하기 어렵다. 값은 이미 있지만, 질문에 맞는 관계와 처리 순서가 준비되지 않았기 때문이다.

문제를 해결하려면 네 층을 구분해야 한다. 먼저 관찰·측정한 자료가 있고, 자료를 목적에 맞게 처리해 얻은 정보가 있다. 개발자는 현실 대상의 공통 의미를 추상화하여 자료구조와 알고리즘을 설계하고, 컴퓨터가 실행할 수 있도록 프로그램으로 구체화한다.

판단 핵심: 값이 부족한 문제인지, 값의 관계가 정리되지 않은 문제인지, 처리 절차가 없는 문제인지 먼저 나눈다. 자료구조는 입력 자료의 추상화된 상태를, 알고리즘은 그 상태에 적용할 명령의 추상화를 담당한다.

자료가 정보가 되려면 처리 목적이 먼저 정해져야 한다

자료는 현실 세계에서 관찰이나 측정으로 수집한 값 또는 사실이다. 장비 번호 204, 반납 예정일 8월 17일, 반납 여부 ‘아니요’는 각각 자료다. 그러나 이 값들이 어떤 판단에 쓰일지는 자료 자체만으로 정해지지 않는다.

정보는 특정 상황에서 의사결정에 쓰도록 자료를 해석하거나 관계를 표현한 처리 결과다. 8월 18일을 기준으로 반납 예정일이 지났고 아직 반납되지 않은 기록을 골라 “노트북 3대가 연체 상태”라고 정리하면 정보가 된다. 강의의 관계식 I=P(D)는 자료 D에 처리 P를 적용해 정보 I를 얻는다는 뜻이다.

구분장비 대여 예판단 기준
자료장비 번호, 예정일, 반납 여부의 개별 값관찰·측정·기록한 값이나 사실인가?
처리기준일보다 예정일이 빠르고 미반납인 기록을 선택질문에 맞게 분류·계산·관계 해석을 하는가?
정보현재 연체 장비의 목록과 수량상황 판단이나 의사결정에 쓸 수 있는 결과인가?

같은 자료라도 처리 목적이 달라지면 정보도 달라진다. 대여 가능 장비를 묻는다면 반납된 기록과 재고를 확인해야 하고, 장비별 이용률을 묻는다면 대여 횟수를 집계해야 한다. 따라서 “정리된 표는 모두 정보”가 아니라, 어떤 질문을 위해 어떤 처리를 거쳤는가가 구분 기준이다.

추상화는 불필요한 저장 세부를 버리고 공통 의미를 남긴다

추상화는 물리적·전기적 동작과 무관하게 대상의 공통 의미와 구조를 골라 생각하는 과정이다. 지하철 노선도를 볼 때 실제 선로의 굴곡, 역사 건물의 크기, 정확한 지리적 거리를 모두 그리지 않아도 역의 순서와 환승 관계를 알 수 있다. 버스의 외형이 서로 달라도 ‘승객을 운송하는 차량’이라는 공통 개념으로 말할 수 있는 것도 추상화의 효과다.

장비 대여 문제에서도 컴퓨터 내부의 비트 표현과 저장 주소를 먼저 고민하지 않는다. ‘대여 기록은 장비 번호와 반납 상태를 가지며, 등록·검색·반납 처리를 할 수 있다’라는 공통 의미를 정한다. 이 수준에서는 장비 번호가 메모리의 어느 주소에 놓이는지보다 어떤 값과 연산이 필요한지가 중요하다.

구체화는 반대 방향이다. 추상적으로 설계한 대여 기록을 실제 메모리의 칸과 연결로 표현하고, 명령을 프로그래밍 언어의 문장으로 옮겨 컴퓨터가 실행하게 한다. 추상화가 세부를 무시하는 일이더라도 중요한 요구까지 지우는 것은 아니다. 질문에 필요한 속성과 연산은 남기고, 현재 판단에 불필요한 구현 세부만 감춘다.

오개념 교정: “추상화할수록 설명이 모호해진다”는 생각은 정확하지 않다. 좋은 추상화는 필요한 의미와 관계를 더 선명하게 만든다. 장비 색상이 연체 판정에 필요 없다면 제외할 수 있지만, 반납 예정일까지 제외하면 문제를 해결할 수 없는 잘못된 추상화가 된다.

자료구조와 알고리즘은 저장 대상과 처리 절차를 나누어 맡는다

자료구조는 알고리즘에서 사용할 자료의 논리적 관계를 추상화해 구조화한 것이다. 알고리즘은 컴퓨터가 특정 일을 수행하도록 추상화한 명령의 유한한 집합이다. 장비 기록을 어떤 관계로 보관할지가 자료구조라면, 연체 장비를 어떤 순서로 검사하고 결과를 만들지가 알고리즘이다.

질문자료구조가 답하는 부분알고리즘이 답하는 부분
무엇을 다루는가?값과 값 사이의 논리적 관계그 값에 수행할 명령의 순서
무엇을 추상화하는가?입력 자료의 상태와 조직컴퓨터가 수행해야 할 일
설계가 나쁘면?필요한 값을 찾고 바꾸기 어려움끝나지 않거나 잘못된 결과를 냄
어떻게 실행되는가?메모리의 구체적인 표현으로 옮김프로그래밍 언어의 명령으로 옮김

둘은 독립적으로 평가할 수 없다. 연체 장비를 한 번씩 검사하는 절차가 명확해도 기록에서 반납 여부를 찾기 어렵게 저장했다면 실행이 비효율적이다. 반대로 잘 정리한 기록이 있어도 검사 종료 조건이 없다면 올바른 결과를 보장할 수 없다. 프로그래밍 언어는 추상화된 자료구조와 알고리즘을 컴퓨터가 다룰 수 있는 형태로 함께 구체화한다.

추상 자료형은 값의 집합과 허용할 연산을 한 계약으로 묶는다

추상 자료형은 자료구조와 알고리즘 사이에서 자료의 복잡한 논리적 성격을 정의하는 형식이다. 자료값의 집합과 그 값에 허용할 연산의 집합을 명세하되, 내부 저장 위치와 구현 코드는 숨긴다.

직접 구성한 ‘장비 대여 목록’ 추상 자료형을 예로 들면 값은 장비 기록들의 집합이고, 연산은 다음처럼 정의할 수 있다.

  • 등록(record): 새 대여 기록을 목록에 추가한다.
  • 조회(id): 장비 번호와 일치하는 기록을 돌려준다.
  • 반납(id): 해당 기록의 반납 상태를 바꾼다.
  • 연체목록(date): 기준일까지 반납되지 않은 기록을 돌려준다.

이 명세는 ‘조회가 가능해야 한다’는 사용 의미를 알려 주지만, 배열의 몇 번째 칸을 볼지 또는 링크를 따라갈지는 정하지 않는다. 그래서 같은 추상 자료형도 서로 다른 구체적인 자료구조로 구현할 수 있다.

구분 기준: 연산의 의미와 외부에서 보이는 결과를 말하면 추상 자료형 수준이고, 메모리 배치와 연결 방식을 말하면 구현 자료구조 수준이다.

자료구조의 분류는 누가 정의했는지와 어떻게 파생됐는지로 읽는다

강의의 분류에서는 자료구조를 미리 정의된 자료구조와 사용자 정의 자료구조로 나눈다. 미리 정의된 자료구조는 다시 기본 자료구조와 파생된 자료구조로 구분된다.

큰 분류세부 분류강의의 예읽는 기준
미리 정의된 자료구조기본 자료구조정수, 실수, 문자언어가 기본 값의 형태로 제공
미리 정의된 자료구조파생된 자료구조배열, 구조체, 포인터기본 요소를 바탕으로 더 복합적인 형태를 구성
사용자 정의 자료구조문제 목적에 맞춘 구조리스트, 스택, 큐, 트리, 그래프필요한 관계와 연산을 중심으로 정의

이 분류는 자료가 선형으로 놓이는지, 계층을 이루는지를 직접 묻는 분류와는 기준이 다르다. 예를 들어 트리가 사용자 정의 자료구조라는 사실은 트리의 계층 관계를 설명하는 말이 아니라, 강의의 분류 체계에서 어디에 속하는지 알려 주는 말이다.

알고리즘은 결과만 맞아 보인다고 성립하지 않는다

알고리즘은 명령을 나열한 메모가 아니다. 입력에서 결과를 얻기까지 각 단계가 실제로 수행 가능하고, 뜻이 분명하며, 반드시 끝나야 한다. 강의에서 제시한 다섯 조건을 장비 연체 목록 절차에 적용하면 다음과 같다.

조건확인 질문연체 목록 절차에서의 적용
입력처리할 값과 형태가 정의되어 있는가?대여 기록 집합과 기준일을 받는다.
출력수행 뒤 적어도 한 결과가 생기는가?연체 기록 목록 또는 빈 목록을 돌려준다.
명확성각 명령이 한 가지 뜻으로 해석되는가?‘오래된 기록’ 대신 ‘예정일이 기준일보다 빠름’으로 쓴다.
유효성각 명령을 실제로 수행할 수 있는가?날짜 비교와 반납 여부 확인처럼 실행 가능한 연산을 쓴다.
유한성유한한 단계 뒤 종료하는가?마지막 기록을 검사하면 멈춘다.

“연체 장비가 보일 때까지 계속 찾는다”라는 절차는 문제가 있다. 연체 장비가 하나도 없으면 언제 멈출지 정해지지 않아 유한성을 만족하지 못한다. “각 기록을 한 번씩 검사하고, 마지막 기록 뒤에는 현재 목록을 출력한다”라고 고치면 빈 목록도 유효한 결과가 되고 종료 시점도 분명해진다.

실패 원인 진단: 답이 틀렸을 때 명령의 내용만 고치지 않는다. 입력 형식이 정의되지 않았는지, 출력이 없는 경우를 빠뜨렸는지, 표현이 모호한지, 실행 불가능한 연산인지, 종료 조건이 없는지를 차례로 점검한다.

시간 성능은 실제 초보다 입력 증가에 따른 실행 횟수를 먼저 본다

알고리즘의 실행시간 분석은 실제 실행 전에 명령의 실행 횟수를 바탕으로 예상 실행시간을 추정하는 방법이다. 점근 표기인 O(n)은 입력 크기 n이 커질 때 실행 횟수가 어떤 증가 경향을 보이는지 표현한다. 같은 O(n)이라고 실제 실행 횟수나 시간이 같다는 뜻은 아니다.

직접 구성한 두 절차의 연산 횟수가 각각 T₁(n)=3n+7, T₂(n)=8n+2라고 가정하자. 두 식은 모두 n에 비례해 증가하므로 O(n)으로 묶인다. 하지만 n=100이면 T₁=307, T₂=802로 실제 횟수는 다르다. 점근 표기는 세부 횟수를 같다고 만드는 등호가 아니라 증가 양상이 유사하다는 분류다.

실행시간 측정은 실행 가능한 프로그램을 실제 컴퓨터에서 돌리고 시스템 시계 등으로 걸린 시간을 재는 방법이다. 분석은 구현 전에도 증가 경향을 비교할 수 있지만, 측정은 구현된 프로그램과 실행 환경의 영향을 함께 받는다.

방법무엇을 보는가?필요한 것해석할 때 주의점
실행시간 분석예상 명령 횟수와 증가 경향알고리즘과 입력 크기같은 O 표기가 같은 실제 시간을 뜻하지 않음
실행시간 측정실제 프로그램의 경과 시간실행 파일과 측정 환경컴퓨터와 실행 조건이 결과에 영향을 줌

공간 성능은 고정 공간과 입력에 따라 변하는 공간을 나눈다

공간 복잡도는 프로그램이 완료될 때까지 필요한 총 메모리 공간을 뜻한다. 강의에서는 이를 Sp=Sc+Se로 나타낸다. Sc는 프로그램 크기처럼 실행 중 일정하게 필요한 고정 공간이고, Se는 실행 과정에서 동적으로 할당되는 자료구조와 변수에 필요한 가변 공간이다.

학습용 예로 고정 공간이 4,096바이트이고 장비 기록 하나마다 16바이트의 가변 공간이 필요하다고 가정하자. 기록이 n개면 Sp(n)=4096+16n이다. n=200일 때 가변 공간은 16×200=3,200바이트이고 총공간은 4,096+3,200=7,296바이트다.

고정 공간이 더 크다고 해서 입력 증가에 항상 더 민감한 것은 아니다. 입력 수가 늘 때 달라지는 부분은 가변 공간이므로, 총량과 증가 원인을 함께 봐야 한다. 시간과 공간은 서로 다른 성능 축이기 때문에 실행이 빠르다는 사실만으로 메모리도 적게 쓴다고 결론 내릴 수 없다.

새 문제는 목적·표현·절차·검증·비용의 순서로 해체한다

  1. 목적을 묻는다. 어떤 의사결정을 위해 어떤 정보를 얻어야 하는지 정한다.
  2. 필요한 자료를 고른다. 관찰값 중 질문에 필요한 속성과 관계만 남겨 추상화한다.
  3. 값과 연산을 명세한다. 추상 자료형 수준에서 허용할 값과 연산을 분명히 한다.
  4. 자료구조와 알고리즘을 함께 설계한다. 저장 관계와 처리 순서가 서로 맞는지 확인한다.
  5. 다섯 조건을 검사한다. 입력·출력·명확성·유효성·유한성 중 빠진 조건을 찾는다.
  6. 시간과 공간을 분리해 평가한다. 증가 경향을 분석하고, 필요하면 구현 뒤 실제 시간도 측정한다.

이 순서를 따르면 “어떤 자료구조가 가장 좋은가?”라는 질문도 목적 없이 답하지 않게 된다. 필요한 연산과 입력 규모가 달라지면 적합한 표현과 비용 판단도 달라지므로, 구조의 이름보다 해결할 질문을 먼저 확정해야 한다.

핵심 개념 정리

  • 자료와 정보: 관찰·측정한 값에 목적 있는 처리를 적용해야 의사결정에 쓸 정보가 된다.
  • 추상화와 구체화: 추상화는 필요한 공통 의미를 남기고 구현 세부를 감추며, 구체화는 설계를 메모리 표현과 프로그램 명령으로 옮긴다.
  • 자료구조와 알고리즘: 자료구조는 값의 논리적 관계를, 알고리즘은 값에 수행할 유한한 명령 순서를 표현한다.
  • 추상 자료형: 자료값의 집합과 허용 연산의 집합을 구현과 분리해 명세한다.
  • 알고리즘의 조건: 입력과 출력이 정의되고, 명령이 명확하고 실행 가능하며, 유한한 단계 뒤 종료해야 한다.
  • 성능: 시간은 실행 횟수의 증가 경향과 실제 측정을 구분하고, 공간은 고정 공간과 가변 공간을 합해 판단한다.

자료구조 문제를 만나면 구조 이름부터 고르지 말고 먼저 원하는 정보를 적습니다. 그 정보에 필요한 자료만 추상화하고, 값과 연산을 명세한 뒤 저장 관계와 처리 절차를 짝지으세요. 마지막으로 알고리즘의 다섯 조건을 통과하는지 확인하고, 입력이 커질 때 시간과 가변 공간이 어떻게 늘어나는지 따로 계산하면 설계의 정확성과 효율을 함께 판단할 수 있습니다.

예상문제 10선

1. 자료와 정보의 관계를 가장 정확하게 설명한 것은?

정답입니다.

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

정답 및 해설 보기

정답: ③

  • ① 오답: 처리 전의 값이나 사실이 자료이고, 처리 뒤 얻은 판단 가능한 결과가 정보이므로 순서가 반대다.
  • ② 오답: 표는 표현 형식일 뿐이며 어떤 질문과 처리 목적에 연결되는지가 정보 판단의 핵심이다.
  • ③ 정답: 강의의 I=P(D)처럼 자료에 목적 있는 처리를 적용해야 정보가 된다.
  • ④ 오답: 두 개념은 물리적 위치가 아니라 처리 전의 값과 의사결정 가능한 결과라는 역할로 구분된다.

2. 장비 번호·반납 예정일·반납 여부 기록에서 ‘현재 연체 장비 수’라는 정보를 얻는 처리로 가장 적절한 것은?

정답입니다.

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

정답 및 해설 보기

정답: ①

  • ① 정답: 연체 판정에는 기준일과 예정일의 비교, 미반납 조건이 모두 필요하며 선택 뒤 집계해야 한다.
  • ② 오답: 예정일이 지났어도 이미 반납한 기록은 현재 연체 수에서 제외해야 한다.
  • ③ 오답: 아직 반납하지 않았어도 예정일이 지나지 않았다면 현재 연체로 판정할 수 없다.
  • ④ 오답: 예정일이 오늘과 같거나 미래인 기록을 골라 날짜 비교 방향을 반대로 적용했다.

3. 추상화와 구체화의 관계를 옳게 설명한 것은?

정답입니다.

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

정답 및 해설 보기

정답: ④

  • ① 오답: 구현 세부를 뒤로 미루는 쪽이 추상화이며 실제 표현을 정하는 쪽이 구체화다.
  • ② 오답: 좋은 추상화는 문제 해결에 필요한 의미를 보존하고 불필요한 세부만 감춘다.
  • ③ 오답: 메모리 주소는 구체화 단계의 일부일 수 있지만 추상화는 논리적 의미와 관계를 다룬다.
  • ④ 정답: 개발자의 개념 설계에서 컴퓨터의 실제 표현으로 이어지는 두 방향을 정확히 구분했다.

4. 자료구조와 알고리즘의 역할을 올바르게 짝지은 것은?

정답입니다.

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

정답 및 해설 보기

정답: ②

  • ① 오답: 명령 순서는 알고리즘의 역할이며 자료구조는 물리 주소만이 아니라 논리적 관계를 다룬다.
  • ② 정답: 입력의 조직과 처리 절차라는 두 추상화의 대상을 정확히 연결했다.
  • ③ 오답: 입력과 출력은 알고리즘 조건이며 두 개념을 입력·출력 한쪽씩으로 나누지 않는다.
  • ④ 오답: 같은 연산도 자료의 조직 방식에 따라 효율이 달라지므로 둘은 함께 설계해야 한다.

5. 추상 자료형에 대한 설명으로 가장 적절한 것은?

정답입니다.

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

정답 및 해설 보기

정답: ①

  • ① 정답: 추상 자료형은 외부에서 필요한 값과 연산의 의미를 규정하고 내부 구현은 감춘다.
  • ② 오답: 추상 자료형은 값의 집합뿐 아니라 연산의 의미도 명세하며 특정 프로그래밍 언어 문장에 한정하지 않는다.
  • ③ 오답: 값과 연산은 함께 정하지만 내부 저장 방식은 외부 명세에서 감출 수 있다.
  • ④ 오답: 같은 값과 연산 명세도 서로 다른 구체 자료구조로 구현할 수 있다.

6. “연체 장비가 나타날 때까지 기록을 계속 검사한다”라는 절차의 가장 직접적인 결함은?

정답입니다.

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

정답 및 해설 보기

정답: ③

  • ① 오답: 기록이 0개나 1개여도 빈 결과 또는 검사 결과를 정의할 수 있으며 두 개 이상일 필요는 없다.
  • ② 오답: 장비 번호의 자료형보다 현재 절차가 끝나는 조건이 없는 점이 직접적인 문제다.
  • ③ 정답: 찾을 대상이 없는 입력에서는 반복이 멈추지 않으므로 마지막 기록 뒤 종료하도록 고쳐야 한다.
  • ④ 오답: 구체적인 메모리 주소는 알고리즘의 유한성 판단에 필요한 조건이 아니다.

7. 강의의 자료구조 분류에서 사용자 정의 자료구조에 해당하는 것만 묶은 것은?

정답입니다.

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

정답 및 해설 보기

정답: ④

  • ① 오답: 정수·실수·문자는 미리 정의된 기본 자료구조의 예다.
  • ② 오답: 배열·구조체·포인터는 미리 정의된 자료구조 중 파생된 자료구조로 분류된다.
  • ③ 오답: 문자는 기본, 배열은 파생, 리스트는 사용자 정의 자료구조여서 세 분류가 섞였다.
  • ④ 정답: 리스트·스택·큐는 강의 분류표에서 모두 사용자 정의 자료구조에 속한다.

8. 두 절차의 연산 횟수가 T₁(n)=3n+7, T₂(n)=8n+2일 때 옳은 해석은?

정답입니다.

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

정답 및 해설 보기

정답: ①

  • ① 정답: 두 식은 선형 증가로 같은 점근 분류에 속하지만 실제 연산 횟수는 계수와 상수항 때문에 다르다.
  • ② 오답: 같은 O 표기는 증가 경향이 같다는 뜻이지 각 입력에서 횟수가 같다는 뜻이 아니다.
  • ③ 오답: 입력에 비례하는 n항이 있으므로 상수항만 보고 상수 시간으로 분류할 수 없다.
  • ④ 오답: 점근 분류에서는 상수항의 영향이 작아지지만 실제 횟수 307과 802를 계산할 때는 포함해야 한다.

9. 공간 사용량이 Sₚ(n)=4096+16n바이트일 때 기록 200개의 총공간은?

정답입니다.

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

정답 및 해설 보기

정답: ②

  • ① 오답: 16×200으로 구한 가변 공간만 나타내며 고정 공간 4,096바이트가 빠졌다.
  • ② 정답: 고정 공간과 가변 공간을 더해 4,096+16×200=4,096+3,200=7,296바이트다.
  • ③ 오답: 고정 공간 4,096에도 기록 수 200을 곱해 고정과 가변의 역할을 혼동한 결과다.
  • ④ 오답: 기록이 하나일 때의 4,096+16만 계산해 입력 개수 200을 반영하지 않았다.

10. 새 자료 처리 문제를 설계할 때 가장 타당한 순서는?

정답입니다.

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

정답 및 해설 보기

정답: ④

  • ① 오답: 목적과 필요한 연산을 정하기 전에 구조와 구현을 확정하면 문제에 맞는 추상화를 설계하기 어렵다.
  • ② 오답: 실행시간 측정은 실행 가능한 프로그램이 있어야 하므로 추상화와 구현보다 앞설 수 없다.
  • ③ 오답: 입출력과 처리 목적을 뒤늦게 정하면 앞서 설계한 구조와 절차가 해결할 문제에 맞는지 보장할 수 없다.
  • ④ 정답: 목적에서 출발해 논리적 설계와 정확성 검사를 거친 뒤 비용을 평가하는 일관된 흐름이다.

참고 자료와 작성 기준

이 글은 한국방송통신대학교 자료구조 1강 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 개념 관계, 장비 대여 사례와 계산 문제는 초급 학습자가 판단 과정을 재현할 수 있도록 별도로 구성하고 검토했습니다.

  • 작성·편집: 올에이클래스 학습연구팀
  • 주요 근거: 한국방송통신대학교 자료구조 1강 「자료구조란 무엇인가」 강의록 전체 37쪽
  • 외부 보충 자료: 사용하지 않음
  • 편집 원칙: 올에이클래스 편집 정책
  • 최종 내용 검토: 2026-08-18

댓글