[자료구조] 자료구조란 무엇인가? - 정리 및 연습문제

1. 자료와 정보의 관계

자료(data) : 현실 세계에서 관찰이나 측정을 통해 수집된 값(value)이나 사실(fact)

정보(information) :
- 어떤 상황에 대해 적절한 의사결정(decision)을 할 수 있게 하는 지식(knowledge)으로서 자료의 유효한 해설(interpretation)이나 자료 상호간의 관계(relationship)을 표현하는 내용
- 자료의 2차 처리 결과물

자료와 정보의 관계는 수식 I = P(D)로 표현할 수 있다. (I : Information, P : Process, D : Data)

 

2. 추상화의 개념

추상화 : 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것

  자료의 추상화는 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 자료의 구조에 대해서 공통의 특징만을 뽑아 정의한 것이다. 자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해서는 자료의 추상화가 필요하다.

 

3. 자료구조의 개념

자료구조(Data Structure) : 추상화를 통해 자료의 논리적 관계를 구조화한 것

 

3-1. 추상 자료형(ADT)

추상 자료형(ADT) :
- 자료의 복잡한 논리적 성격을 정의하는 형식
- 자료 집합과 연산 집합의 정의/명세

 

3-2. 자료구조의 형태

C언어를 기반으로 정의된 기본 자료구조의 종류와 관계 (출처: 한국방송통신대학교)

 

미리 정의된 자료구조 :
- 프로그래밍 언어에서 제공되는 자료구조

기본 자료구조 :
- 생활 속에서 숫자나 문자 등의 형태로 존재하는 자료를 추상화한 자료구조

파생 자료구조 :
- 프로그래밍 언어에서 제공되면 유용한 자료구조라고 판단하여 파생된 자료구조

사용자 정의 자료구조 :
- 개발자가 정의하여 사용하는 자료구조
- 특정 목적에 맞춰 정의된다.

  미리 정의된 자료구조를 이용하여 프로그램 코드에서 선언하면 컴파일러 등의 도구가 구체적인 저장 용량과 방법을 결정한다. 사용자 정의 자료구조는 개발자가 정의, 추상화하여 프로그래밍 언어로 구현한다.

 

4. 자료구조와 알고리즘

알고리즘 : 
- 컴퓨터가 일을 하는 데 필요한 명령어들의 유한집합
- 추상화된 형태
- 알고리즘 ─ 구체화 → 프로그램

- 자료구조는 알고리즘의 기초가 되며 알고리즘의 성능에 영향을 줄 수 있다.

- 자료구조가 입력값이 추상화된 상태라면 알고리즘은 수행할 명령이 추상화이다.

- 개발자는 입력값을 추상화된 형태(자료구조)로 구조화하고 명령어를 추상화된 형태(알고리즘)로 체계화한 뒤 프로그래밍 언어로 자료구조와 알고리즘을 구체화한다.

 

4-1. 알고리즘의 조건

① 출력	알고리즘 수행 후 적어도 한 가지 결과를 생성해야 한다.
② 유효성	알고리즘은 실행 가능해야 하며 동일한 결과를 생성해야 한다.
③ 입력	알고리즘의 입력은 형태가 정의될 수 있는 유한한 입력이어야 한다.
④ 명확성	알고리즘의 명령은 명확해야 한다.
⑤ 유한성	알고리즘은 언젠가 종료되어야 한다.

 

5. 알고리즘 성능의 분석과 측정

알고리즘 성능 분석 : 알고리즘을 실행하는데 필요한 시간과 공간을 추정
알고리즘 성능 측정 : 실제로 프로그램을 실행하는데 걸리는 시간을 측정

 

5-1. 알고리즘 실행 시간의 예측

시간 복잡도(Time Complexity) : 알고리즘에서 입력값과 수행 시간의 상관관계를 나타내는 척도

  알고리즘의 실행 시간은 시간 복잡도라는 개념을 통해 예측할 수 있다. 어떤 알고리즘이 실행 횟수에 대해 O(n)의 함수를 갖고 있다는 것은 실행 횟수가 그러한 경향을 갖고 있다는 것을 의미한다. 다수의 알고리즘이 실행 횟수 함수 O(n)을 가지는 것은 유사한 입력 개수의 증가에 대해 비슷한 실행 시간의 증가를 보인다는 것을 의미한다. 같은 O(n)을 가진다고 해서 같은 실행 시간을 갖는 것이 아니라 실행 시간의 유사한 증가 경향을 보인다. 따라서 같은 일을 하는 여러 알고리즘의 실행 시간을 예측해서 특정 입력 경향에 대해 적합한 알고리즘을 선택할 수 있다.

 

5-2. 알고리즘 실행 메모리의 예측

공간 복잡도(Space Complexity) : 프로그램을 실행시켜 완료하는데 필요한 메모리 총량
고정 공간 : 프로그램이 종료될 때 까지 고정적으로 필요한 메모리 공간
가변 공간 : 프로그램 실행 과정에서 동적으로 할당되어야 하는 자료구조와 변수를 위해 필요한 메모리 공간

S_p = S_c + S_e

프로그램 P의 총 메모리 공간 = 고정 공간 + 가변 공간

 

  프로그램 P의 총 메모리 공간(space for program)은 고정 공간(space for compile)과 가변 공간(space for execution)의 합으로 구한다.

 

5-3. 알고리즘 실행 시간의 측정

  프로그램의 실제 실행 시간을 측정하는 방법으로 시스템 시계(System Clock)을 이용하여 프로그램의 첫 라인에서의 시스템 시간, 끝 라인에서의 시스템 시간을 기록하여 구할 수 있다. 실제 프로그램 및 데이터가 있어야 측정이 가능하다.

 

연습문제

1. 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것은?
① 자료구조
② 정보화
③ 추상화
④ 알고리즘

2. 다음 문장의 옳고 그름을 결정하시오. (O, X)
정보는 현실 세계에서 관찰이나 측정을 통해서 수집된 값이나 사실이다.

3. 다음 문장의 옳고 그름을 결정하시오. (O, X)
자료의 추상화란 컴퓨터에 의해 수행되기 위해 필요한 명령어들의 유한 집합이 사람의 머릿속에 추상화되어 존재하는 것이다.

4. 자료의 복잡한 논리적 성격을 정의하는 형식으로 자료 값의 집합과 연산 집합에 대한 명세의 집합을 무엇이라고 하는가?(2016년도 기말고사 기출문제)
① 추상화 집합
② 알고리즘
③ 자료형
④ 추상 자료형

5. 다음 문장을 수식으로 표현한 것으로 알맞은 것은?
정보(Information)은 자료(Data)를 처리(Process)해서 얻어진 결과(Result)이다.
① R = P(D)
② I = P(R)
③ P = R(D)
④ I = P(D)

6. 현실 세계에서 관찰이나 측정을 통해서 수집된 값이나 사실을 무엇이라 하는가?
① 자료
② 정보
③ 자료구조
④ 추상화

7. I = P(D)의 해석으로 옳은 것은?
① 정보(Information)은 자료(Data)를 처리(Process)해서 얻어진 결과(Result)이다.
② 정보(Information)은 결과(Result)를 처리(Process)해서 얻어진 자료(Data)이다.
③ 자료(Data)는 결과(Result)를 처리(Process)해서 얻어진 정보(Information)이다.
④ 자료(Data)는 정보(Information)를 처리(Process)해서 얻어진 결과(Result)이다.

8. 다음 중 미리 정의된 자료구조는 무엇인가?
① 배열
② 스택
③ 큐
④ 트리

9. 알고리즘의 조건에 포함되지 않는 것은?
① 출력
② 입력
③ 절대성
④ 유한성

10. 다음 표에서 (가), (나)의 순서대로 가장 적합한 내용은 무엇인가?
① 프로그램, 알고리즘
② 자료구조, 알고리즘
③ 슈도 코드, 프로그램
④ 알고리즘, 프로그램

	자료	연산
추상화	추상 자료형	(가)
구체화	자료형	(나)

 

정답 ▼

1 : ③
2 : X
3 : X
4 : ④
5 : ④
6 : ①
7 : ①
8 : ①
9 : ③
10 : ④