[C 자료구조] Ch.0 자료구조

시작하며, 2-3년 전 자료구조를 java로 공부했던 주인장
후배들에게 자료구조를 가르쳐야하는 상황이 발생해버렸다..
문제는 C언어로 가르치라는 교수님의 명이 있었기에 교육 자료 겸
자료구조 글을 시리즈로 올려보려 한다.
누군가에게 도움이 되길 바라며

남기는 말

1. 사전 지식이 거의 없는 사람의 학습용 자료 입니다.
2. 학습을 위해 일반적인 책과 학습 순서가 다를 수 있습니다.
3. 특정 주제가 하나의 챕터에 모든 내용이 들어간 것이 아닌 여러 챕터로 나누어져 있을 수 있습니다.
이때는 추후 주석이나 링크로 보강하도록 하겠습니다.
4. 글이 수정될 경우, 최상단에 수정 일과 수정 내용을 간단히 작성 하겠습니다.
5. 본 포스팅은 "C로 배우는 쉬운 자료구조", 한빛아카데미 4판 을 참고하였습니다.

 

챕터 0에서는 자료구조란 무엇인지, 알고리즘이란 무엇인지 책에서 다룰거 같은 내용과 왜 공부해야하는지 등

앞으로 어떤 것을 배울지를 정리 하려한다.

 

---

 

0. 튜토리얼

중고등학생에게 코딩 교육 봉사를 자주 했던 주인장에게

관련 지식이 없는 어린이한테 자료구조를 설명하라한다면, 이렇게 답할 것이다.

"필통과 보관함의 차이"

대충 이런 느낌일 것이다.

필통 속 연필과 색연필 들은 분류 되어 있지 않다. 필요한 색의 색연필을 꺼내기 위해서는 필통을 뒤적여야 할 것 이다.

반면 오른쪽 사물함(약방 분류함 이긴한데...)은 종류에 맞춰 분류되어 있을 것이다.

한 칸에는 하나의 색을 가진 여러 색연필이 있을 것이다.

 

여기까지 설명 했다면 보통 어린이들은 이렇게 답한다.

"자료구조는 정리네요" 혹은 "자료구조는 분류네요" 

 

이 대답은 필통과 보관함이 지닌 공통된 의미를 포함하지 않고 있다.

필통과 보관함은 물건을 보관 할 수 있으며, 언제든 물건을 꺼낼 수 있고, 물건이 떨어지면 추가로 넣어줄 수 있다. 또한 어떤 물건을 넣을지 정할 수 있다.

 

이 설명 이후 위키백과에 나와있는 자료구조의 정의를 읽어주자.

 

자료구조는 '효율적'으로 접근 및 수정을 할 수 있도록 하는 자료의 조직, 관리, 저장을 통틀어 의미한다.
더 자세히는 데이터 값의 모임, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수 혹은 명령을 의미한다.

 

---

 

1. 자료구조란?

이 글을 어떤 책, 수업, 자료를 병행하여 읽을지 알 수 없어 이론적인 측면도 같이 첨부 합니다..

 

우선 자료구조가 다루는 내용은 '이론적 측면'과 '실제적 측면'으로 나눠진다.

 

이론적 측면 : 이산 수학(그래프 이론, 집합 이론, 조합적 분석), 확률 이론

위 내용을 통해 알고리즘 분석에선 검색, 정렬, 효율분석(공간 복잡도, 시간 복잡도)를 배우게 된다.

 

실제적 측면 : 문자열, 리스트, 트리, 그래프, 파일

위 내용을 통해 알고리즘을 구현하는데 프로그래밍, 파일 작성, 메모리 관리, 운영체제 에 대해 다루게 된다.

 

다음으로 자료구조는 4가지 구조를 지닌다. 이는 자료구조의 분류 4가지로 알려져 있다.

(해당 구조에 대한 자세한 설명은 본 챕터에서 진행 예정)

 

1. 단순 구조 : 정수, 실수, 문자, 문자열

 

2. 선형 구조 : 스택, 큐, 덱, 순차 리스트, 연결 리스트(단순, 이중, 원형 등)

 

3. 비선형 구조 : 트리(일반 트리, 이진 트리), 그래프(방향, 무방향)

 

4. 파일 구조 : 순차 파일, 직접 파일, 색인 파일

 

이 처럼 4가지 구조가 존재하는데, 저장공간, 실행 소요 시간, 연산 특성, 자료 특성 등에 맞게 가장 효율적인 자료구조를 선택하는 것이 학습의 최종 목적이다.

 

---

 

2. 자료의 추상화와 구체화

인간이 가진 기능 중 하나인 추상화(Abstraction)에 대해 이야기 해보겠다.

대부분 우리가 사람이나 사물을 기억하기 위해 사용되는 기능인 추상화는 대상의 세세한 정보를 기억하는 대신, 다른 대상과의 다른점(해당 대상만의 특징)을 바탕으로 기억한다.

 

ex) 빨간색의 구형 물체로 과일이며, 지름이 5~9cm로 비타민 C가 5% 정도 함유 되어 있으며, 영어로는 apple = 사과

ex) 빨간색 주먹만한 과일 = 사과

 

이렇듯 컴퓨터도 크고 복잡한 문제를 해결하기 위해 추상화 작업을 적용하여 문제를 단순화 시킨다.

자료 추상화에 있어 기본 개념은 자료(Data), 연산(Operation), 자료형(Data Type)이 있다.

 

자료 : 어떤 값(Value)을 의미, 프로그래밍의 처리 대상이 되는 모든 것

연산 : 어떤 일을 처리하는 과정, 연산자를 이용하여 수행

자료형 : 처리할 자료의 집합과 자료에 대해 수행할 수 있는 연산자의 집합

이렇듯 추상화 된 자료형은 추상 자료형(ADT: Abstract Data Type) 이라고 한다.

 

추상화 과정과 반대로 추상화된 자료를 실제로 사용하기 위해 구조화하여, 수행되어야 할 명령어를 체계화 하는 작업을

'구체화'라고 한다.

 

---

 

3. 알고리즘

Algorithm은 문제 해결을 위한 방법을 추상화 한 뒤, 단계적 절차를 논리적으로 기술해 놓은 명세서이다.

쉽게 말해 요리 레시피이다.

된장국을 만들기 위해 물, 된장, 두부랑 끓이는 것을 생각하는게 추상화

순서에 맞춰 재료를 정량을 넣어가며 수행하도록 하는 것이 알고리즘 이다. (극단적인 예시이다.)

 

이러한 알고리즘은 5가지의 조건을 가지고 있으며, 이 조건을 모두 만족해야 효율적인 알고리즘이라고 부를 수 있다.

 

1. 입력 : 수행에 필요한 자료가 외부에서 입력됨

2. 출력 : 수행 후, 결과가 하나 이상 출력되야 함

3. 유한성 : 모두 수행 후, 반드시 종료되어야 함

4. 명확성 : 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어가 명확히 명시되어야 함

5. 효과성 : 모든 명령어는 기본적으로 실행할 수 있어야 함

 

---

 

4. 알고리즘의 성능 분석

앞서 알고리즘을 소개했다. 문제는 만들어진 알고리즘이 효율적인지 확인할 방법을 아직 배우지 못했다.

문제를 효율적으로 풀기 위해 필요한 것이 효율적인 알고리즘이므로, 알고리즘의 성능을 분석하는 두 가지 방법을 소개한다.

우선, 알고리즘 성능을 분석하는 기준은 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등이 있다.

이를 바탕으로 알고리즘 성능 분석 방법은 두 가지로 나뉘게 된다.

 

1. 공간 복잡도(Space Complexity) : 실행에서 완료까지 필요한 총 저장 공간을 의미한다.

= 알고리즘을 실행하는데 필요한 공간(메모리)를 추정하여 성능을 분석하는 방법

 

Sp = Sc + Se (공간 복잡도 = 고정 공간 + 가변 공간)

 

고정 공간 : 프로그램의 실행이 끝날 때 까지 고정적으로 필요한 메모리 공간

가변 공간 : 실행 과정에서 사용되는 자료와 변수를 저장하는 공간과 함수를 실행하는데 관련된 정보를 저장하는 공간

 

2. 시간 복잡도(Time Complexity) : 실행에서 완료까지 필요한 총 시간을 의미한다.

 

시간 복잡도 = 프로그램의 컴파일 시간 + 프로그램 실행 시간 

 

다만, 프로그램의 컴파일 시간은 프로그램 특성과 관련 없으므로, 고정된 같은 시간으로 가정한다.

= 코드를 수정하지 않는 이상 컴파일은 여러번 하지 않으므로 유의미 하지 않음

 

---

 

5. 알고리즘 성능 분석 표기법

앞서, 두 가지 성능 분석 방법을 학습하였다. 

일반적인 알고리즘의 주요 성능 차이는 실행 시간의 차이에서 발생하므로, 알고리즘을 비교하기 위해선 보통 시간 복잡도 표기를 사용한다.

 

표기 방법은 크게 3가지로 빅-오 표기법, 빅-오메가 표기법, 빅-세타 표기법 으로 나뉜다.

(보통 Big-O 표기법만 사용) / (추후 자세히 다룰 예정)