방송대 자료구조 교재 요약 제1 장 - 강태원·정광식 공저

개인 공부를 위해 진행한 요약입니다.

자료구조에 대해 알고 싶은 분은

방송대에서 자료구조 강의를 사거나(단돈 15,000원) 교재(eBook이면 단돈 11,000원, 구판은 실물 도서인데 9,400원(내용 차이 거의 없음))를 구입하는 것을 권장합니다.

둘 다 퀄리티가 나쁘지 않습니다.

정말 좋다고 말하지 않는 건, 시중 자료구조 책을 많이 보지 않아 비교대조군이 부족하기 때문.

머리말)

프로그램은 자료구조를 조합해서 만든다. 그래서 프로그램을 효율적으로 만들고 싶다면 자료구조를 알아야 한다.

대학 학부과정에서 반드시 알아야 하는 자료구조는 다음과 같다.

1. 자료구조의 의미와 개념, 자료구조의 가장 중심 개념인 추상화

2. 프로그래밍 언어에서 기본적으로 제공하거나 정의하여 사용하는 자료구조와 그것들을 여러 개 붙여서 사용하는 배열

3. 프로그래머가 스스로 정의하여 사용하는 자료구조인 스택, 큐, 리스트와 그것의 응용

4~5. 비선형 자료구조(e.g. 트리)

6. 그래프, 그래프를 순회하는 방법

---

제1 장 자료구조란 무엇인가)

 

1. 자료와 정보

컴퓨터로 데이터가 들어올 때, 입력 자료값의 추상화를 위해 자료구조를 선택하고

프로그램의 추상화를 위해 알고리즘이 결정됨.

쉽게 말해 자료구조를 통해 데이터가 다루어지고 이를 알고리즘이 가지고 프로그램에서 다룬다.

...

가장 먼저 알아야 할 건 자료와 정보의 차이다.

자료는 정말 의미 없이 산재한 데이터다.

정보는 그런 데이터를 가공해서 의미를 가지게 한 것이다.

그래서 I=P(D)라고 교수님이 설명하는 것.

...

2. 추상화

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

'커피 마시러 갈래?'라고 할 때 커피는 카페오레가 될 수도 있고 아메리카노가 될 수도 있고 캐러멜 마키아토가 될 수도 있다.

아직 그 '커피'가 무엇인지는 지칭되지 않았다.

하지만 사람들은 그 '커피'가 무엇인지 정확하게 지칭하지 않아도 추상적 사고를 할 수 있기에 '커피'라는 단어 하나만 사용해도 수 많은 커피들이 가지고 있는 공통 요소를 바탕으로 커피를 떠올릴 수 있다.

(참고: 지금 저는 교재를 보면서 교재 내용과 제 생각을 함께 쓰고 있습니다. 틀린 내용은 웬만하면 발생하지 않을 거라 생각하나 여기에 적힌 모든 내용들이 책에 나온다는 보장이 없으니 그 부분을 유의하고 보시길 바랍니다.) 

...

3. 자료구조

자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해서는 자료의 추상화가 필요하다.

자료의 추상화를 통해 자료의 논리적 관계를 '구조화'한 것이 자료구조다.

자료구조가 컴퓨터에 대한 자료(입력값)의 추상화된 상태라면, 알고리즘은 컴퓨터가 수행해야 할 명령의 추상화다.

같은 자료구조에 여러 개의 알고리즘이 적용될 수 있고, 같은 알고리즘에 여러 개의 자료구조가 정의될 수 있다.

...

구현을 원하는 게 있으면 추상적 사고를 활용해 자료구조를 사용해서 알고리즘을 만든다.

프로그래밍 언어로 위 자료구조와 알고리즘을 컴퓨터에서 구동하면 컴파일러가 이를 구체화해서 이진코드와 전기신호를 이용해서 작업을 수행한다.

...

추상 자료형(ADT)는 자료구조와 알고리즘의 중간쯤에 있다.

자료구조는 '미리 정의된 자료구조'와 '사용자 정의 자료구조'로 구분된다.

프로그래밍 언어가 만들어질 때 미리 정의된 자료구조는 정수, 실수, 문자 등과 같은 기본 자료구조,

기본 자료구조로부터 파생된 배열, 구조체, 포인터 등과 같은 파생된 자료구조가 있다.

개발자가 정의하여 사용하는 사용자 정의 자료구조는 소프트웨어 개발 중에 개발자에 의해 만들어지는데

리스트, 스택, 큐, 트리, 그래프 등이 있다.

...

이 책은 C 프로그래밍 언어를 기반으로 정의된 자료구조를 다룬다.

(나는 자바 자료구조를 어느 정도 봤으니 둘 중 다른 내용이 있으면 메모를 남겨 보겠다.)

...

4. 자료구조와 알고리즘의 관계 및 알고리즘의 특성

알고리즘은 추상화시킨 동작들의 연속이다.

알고리즘 단계에서는 행동의 구체적인 내용은 결정되지 않는다.

알고리즘은 설계 단계에서 만들어지며, 구체적인 내용은 프로그램 작성 단계에서 이루어진다.

...

알고리즘의 조건

알고리즘에는 조건이 있다. 아래 내용들을 모두 충족해야 알고리즘이라고 할 수 있다. <- 앞으로 중요한 내용은 Bold 처리 합니다.

출력, 유효성, 입력, 명확성, 유한성.

출력: 알고리즘 수행했으면 결과가 나와야 한다.

유효성: 알고리즘 내의 각 연산은 명확해야 하고 반드시 실행할 수 있어야 한다.

입력: 입력은 유한해야 하고 반드시 입력 형태가 정의될 수 있어야 한다.

명확성: 각 명령들은 명확하고, 애매모호하지 않아야 한다.

유한성: 종료가 명확하게 정의되어 있어야 한다(무한루프 돌면 안 된다.).

...

5. 알고리즘의 성능

알고리즘의 성능을 분석한다는 말은, 알고리즘을 실행하는 데 필요한 시간과 공간을 추정하여 알고리즘의 성능을 분석하는 것.

여기서 말하는 시간은, 알고리즘의 수행 시간, 공간은, 알고리즘을 수행하는 데 필요한 메모리 공간.

...

어떤 알고리즘이 실행 횟수(알고리즘의 실행 시간)에 대해서 O(n) 함수를 가지고 있다는 것은 실행 횟수가 그러한 경향을 가지고 있다는 것을 의미한다.

100% n만큼 실행한다는 것이 아니다. 대략, 경향, 이런 의미다.

그러니 같은 O(n)을 가진다고 해서 실행 시간이 같은 게 아니다. 실행 시간이 증가하는 경향이 유사하다는 것이다.

...

끝!