[Reading] 열혈강의 자료구조 - CHAPTER 01

열혈강의 자료구조

C로 만드는 자료구조와 적용 알고리즘 해설서로 기본 자료구조, 고급 자료구조, 알고리즘 으로 크게 구성된다. 자료구조를 이해하기 전 기본지식을 시작으로 기본 자료구조에 해당하는 ‘선형 자료구조’를 지나 고급 자료구조를 공부하며 공부한 이를 바탕으로 몇 가지 핵심적인 알고리즘을 공부하자.

CHAPTER 01 - 자료구조의 시작

1. 자료구조의 정의

프로그래밍을 시작한 초보자에게 프로그램 개발에 대해 설명하기 위해 자주 사용하는 예 중 하나가 ‘건물 건축의 비유’다. 컴퓨터 프로그래밍에 있어 가장 기초적인 학문분야로 인식되고 있는 자료구조는 마치 높은 건물을 짓기 전에 필요한 기초 공사와 마찬가지로 컴퓨터 프로그램이 효율적이고 안전하게 동작하기 위해 반드시 필요한 프로그램의 기본 골격에 해당한다. 당연한 얘기지만 프로그램의 크기가 커질수록 간단한 기능 하나 추가하는 것이 기존에 돌아가던 기능을 마비시키거나, 수많은 오류와 버그들을 야기할 수 있기 때문이다.

프로그램 설계 전 사용자의 요구 사항과 주위 환경 분석이 선행되어야 한다. (=== 자료구조의 설계 및 구현은 프로그램의 구체적인 사용 목적과 환경에 따라 이루어져야 한다.)

오늘날 사용하는 다양한 컴퓨터 프로그램은 2가지 공통점이 있다. 1) 컴퓨터에 의해 실행되는 명령어들의 집합 2) 명령을 수행하기 위해 내부적으로 여러 자료(Data)를 저장한다.

결국 자료구조란 컴퓨터에 자료를 효율적으로 저장하는 방식을 말한다. 이는 필요한 메모리를 절약할 뿐 아니라, 프로그램 수행 시간을 최소화 하는 기능을 수행한다.

즉, 하나의 프로그램이 정상적으로 동작하려면 내부적으로 자료를 저장하고 있을 뿐 아니라 이러한 자료를 처리하기 위한 명령어들의 집합을 가지고 있어야 됨 효율적인 알고리즘(컴퓨터 명량 자체의 효율성을 증가시키기 위한 절차(방법))이 가능하기 위해서는 먼저 효율적인 자료구조가 선행되어야 한다. ex) 파일 탐색기의 트리구조, 최근 문서의 스택

2. 자료구조의 분류 (Data의 Type에 따른 자료구조의 분류 방법)

1. 단순 구조(Primitive Data Structure) 1) 정수(int), 실수(float / double), 문자와 문자열(char) 2) 선형 구조, 비선형 구조를 이루는 구조

2. 선형 구조(Linear Data Structure) 1) List, Stack, Queue, Deque 등 2) 각각의 자료들 사이의 앞뒤 관계가 1:1인 경우

   

3. 비선형 구조(Non-Linear Data Structure) 1) 트리, 그래프 2) 자료 사이의 선후관계가 1:1 관계가 아닐 수 있다

   

4. 파일 구조(File Organization) 1) 보조기억장치(ex 하드디스크)에 저장되는 파일에 대한 자료구조 2) 선형, 비선형처럼 메모리가 아닌 디스크에 저장된다는 가정에 기반을 둔 것으로, 주로 메모리에 한 번에 올릴 수 없는 대용량의 자료들을 대상으로 한다. 3) 파일의 구성 방식에 따라 순차적(Sequential), 상대적 파일 구조(Relative), Indexed Sequential 및 다중 키 파일 구조(Multi-key)등이 있다.

3. 추상 자료형(ADT, Abstract Data Type)

자료구조를 기술하는데 추상 자료형이 필요한 이유는 보통 정보 은닉을 이야기 한다. 정보 은닉은 컴퓨터 프로그래밍에서 중요하게 사용되는 개념 중 한가지로 중요한 정보만 나타내고, 중요하지 않은 정보는 숨기는 것을 말한다. 궁극적으로는 개발 효율성을 증가시키려는 목적으로 사용된다.

사용자의 관점에서 불필요한 정보를 제거, 사용자에게 반드시 필요한 것만을 심플하게 제공해 개발 효율성을 증가시키려는 접근 방법.

기존 구현된 자료구조를 사용하는 이유는 쉽고 빠르게 개발을 하기 위해서인데 자료구조의 사용을 위해 하나하나 분석해야 한다면, 직접 자료구조를 개발하는 편이 더 편하다고 생각할 수 있다.

특정 자료구조가 추상 자료형을 통해 사용자에게 제공된다면, 자료구조를 사용하는 사용자가 손쉽게 해당 자료구조를 사용할 수 있을 것이다. 이는 추상 자료형이 자료구조를 사용하는 데 필요한 인터페이스만을 간단하게 전달하기 떄문.

3-1. 자료, 자료형

-. 자료형: 자료와 자료를 처리하기 위한 명령 혹은 연산의 집합
-. 자료: 프로그램에서 처리되는 대상으로 특정 값을 의미(ex: 정수형 === +,-,/,*..)

3-2. 추상화와 추상 자료형

화가가 이해한 사물의 본질 혹은 중요 특성에 의해 관념적으로 그리는 그림의 추상화와 비슷한 의미로 추상 자료형은 추상적으로 정의된 자료형을 의미한다. 1) 세부적이고 복잡한 것을 생략하고 2) 대표적인 것, 중요한 것만을 나타냄 을 의미한다.

예를 들어 GPS 프로그램을 작성한다고 가정했을 때, 저장해야 하는 자료는 지도에서의 위치 자료이다. X,Y 좌표로 구성되며 연산으로는 1) 위치 자료의 변경, 2) 위치 자료 사이의 거리 계산, 3) 두 개의 위치 자료 사이의 비교 연산 을 생각해볼 수 있다.

-. 자료와 연산으로 구성
-. 가장 중요하고 핵심적인 자료만을 나타내었음
-. 정의된 연산은 각 이름, 입/출력과 알고리즘 설명(각각의 연산에 대한 이름을 통해 대략 어떠한 동작을 수행하는지 파악)

추상 자료형을 통해 자료구조의 내부 구현 소스에 대한 분석 없이 신속하게 자료구조를 이용할 수 있다. 명령을 식별할 수 있는 이름, 명령 호출을 위한 입력 및 호출 결과인 출력으로 구성되어 있다.

또, 개발자(공급자)의 관점에서 추상 자료형의 정의는 자료구조를 구현하기 전에 설계도를 미리 그려보는 것과 동일한 기능을 수행한다. 자료구조의 인터페이스가 유지된다고 가정하면, 자료구조의 개발자와 사용자 간 간섭 문제도 해결 가능하다. 자료구조의 내부 기능(로직)이 변경된다 하더라도 기존 자료구조를 사용하던 쪽의 소스 코드는 변경될 필요가 없다.

추상 자료형은 외부에서 호출할 수 있는 일종의 인터페이스를 정의한 것이라면, 자료구조는 이러한 인터페이스뿐 아니라 모든 내부 변수 및 내부 구현 연산을 포함하고 있다.

추상 자료형은 복잡한 자료형을 정의할 때 복잡한 세부 구현 내용은 생략하고, 앞으로 변경될 가능성이 적은 대표적이면서도 핵심적인 내용만을 간략히 기술한다. 자료구조의 핵심적인 나용을 간략하게 표현 복잡한 내부 구현 부분을 감추기 위해

4. 알고리즘

컴퓨터 공학에서 일반적으로 이야기 하는 알고리즘은 어떠한 문제를 해결하기 위한 절차를 말한다. 예를 들어 1-100까지의 합을 구할 때 1부터 1씩 차례대로 증가시켜 100까지의 모든 정수를 하나씩 더하는 방법. 그러나 컴퓨터 공학에서 이야기 하는 알고리즘은 컴퓨터로 주어진 문제를 해결하기 위한 절차이기에 컴퓨터가 이해할 수 있는 언어로 이러한 절차를 기술(표현)해야한다.

CalcSum(n) {
  sum
  for(i<-1;i<=n;i<-i+1){
    sum <- sum + i
  }
  return sum
}

주어진 문제를 반드시 해결해야 하기 때문에 문제 해결 조건으로 다음과 같은 다섯가지 특성을 필수로 가져야 한다.

1. 입력(input): 외부에서 제공되는 자료가 0개 이상 있어야 한다.
2. 출력(output): 적어도 1개 이상의 결과를 만들어야 한다.
3. 명백성(definiteness): 각 명령어는 의미가 모호하지 않고 명확해야 한다.
4. 유한성(finiteness): 한정된 수의 단계 뒤에는 반드시 종료된다. 무한히 동작해서는 안된다.
5. 유효성(effectiveness): 모든 명령은 실행 가능한 연산이어야 한다. 예를 들어 0으로 나누는 연산과 같이 실행 불가능한 연산은 포함해선 안된다.

같은 자료라 하더라도 어떻게 표현되고 저장되느냐에 따라 사용 가능한 알고리즘이 달라지기 때문에 자료구조는 알고리즘과 밀접한 관련이 있다. 효율적인 자료구조의 설게는 알고리즘의 설계에 영향을 끼치기에 프로그램의 성능을 결정짓게 하는 가장 중요한 요인 중 하나이다.

알고리즘은 자료구조를 기반으로 도출되지만, 반대로 자료구조의 특정 연산을 구현하기 위해 알고리즘이 필요한 때도 있다. (즉, 자료구조의 기본적인 연산을 구하기 위해 알고리즘이 사용되기도 하기 때문에 정확한 이해가 필요하다.)

4-1. 알고리즘의 표현

알고리즘을 표현하는 대표적인 방법 4가지를 요약하면 아래와 같다.

일반적으로 의사코드 혹은 순서도를 많이 사용하고 있다.(컴퓨터가 이해할 수 있는 명백한 언어가 아닌 문제점. / 구현 소스를 통해 매우 자세하고 엄격하게 나타내야 한다는 문제점 등)
간단한 알고리즘 혹은 알고리즘의 대략적인 흐름을 전달할 때는 순서도 이용, 복잡한 알고리즘일 경우 주로 의사 코드를 많이 사용하고 있다.
이는 의사코드가 자연어와 프로그래밍 언어의 중간 정도에 해당하기 때문에 어느정도 명백성과 체계적으로 알고리즘의 기술이 가능하기 때문이다.

4-2. 순서도와 의사 코드

ㅁ 의사 코드를 기술하는 방법

1. 지정문 - 변수에 특정 값을 대입하는 명령
   • sum이라는 변수의 값을 10 증가시키는 의사코드
   • ‘처리’ 기호를 통해 나타낼 수 있다.
2. 조건문 - 조건식을 만족하는 지에 따라 흐름이 결정되는 명령
   • if-then-else 문이 있으며 외에 switch-case문 등이 있다.
   • ‘판단’ 기호를 통해 나타낼 수 있다.
3. 반복문 - 특정 명령을 여러 번 반복적으로 수행하는 구조
   • for, while, do-while 등이 있다.
   • 초기값을 먼저 설정하고, 조건식을 만족할 때 까지 명령문을 실행한다.

4-3. 알고리즘의 성능 분석

주어진 문제를 해결하기 위해 다양한 알고리즘을 적용할 수 있는데, 이 때 어떤 알고리즘을 사용해야 하는가?
=> 가장 효울적인 문제 해결

1. 공간 복잡도와 시간 복잡도
   • 얼마나 더 많은 저장공간 / 얼마나 더 많은 시간이 필요 한가
   • 향상된 하드웨어 기술로 ‘시간 복잡도’에 더 많은 집중 - 실행되는 명령문의 개수를 측정
   • 시간 복잡도 함수: 입력 값에 따른 실행 빈도수

2. 입력 값에 따른 실행 연산의 빈도수

3. 빅-오(O) 표기법
   

시간 복잡도 함수 중 가장 큰 영향력을 주는 n에 대한 항만을 표시하는 일반적인 방법.(Big-Oh Notation) 일반적으로 계수(Coefficient)는 생략하여 표시한다.
=== 최고 차항의 차수만을 사용