Ⅰ 자료구조

Chapter 01 자료구조와 알고리즘

1. 자료구조란?

데이터를 특성에 따라 분류하여 효율적으로 구조화하고 저장 및 처리하는 모든 작업

 

프로그램을 작성할 때, 다량의 자료를 체계적으로 정리하는 것은 매우 중요하다. 자료가 뒤죽박죽이면 찾기도 어렵고 낭비도 심할 것이다. 도서관의 책들을 아무데나 꽂는 것이 아니라 도서의 분류와 구조를 갖춰야 하는 것과 마찬가지 입니다. 컴퓨터 내에서도 자료를 어떤 식으로 처리할 것인가에 대해 궁리할 필요가 있다.

 

언어는 소통의 수단이며 도구인데 자료구조를 배우는 것은 그 도구를 잘 사용하기 위한 과정이라고 할 수 있어요. 프로그래밍 언어 사용법만 안다고 해서 프로그래밍을 잘한다고 볼 수 없다. 사용법을 아는 것과 잘 작성하는 것은 다른 것이다. 자료구조는 정보처리기사의 중요한 5가지 파트 중 하나이기도 하다. 이후, 데이터베이스를 학습할 때에도 밀접한 연관이 있고, 컴퓨터 소프트웨어 개발에 있어서  매우 기초적이고 중요한 핵심 과목이니 집중해서 공부해야 된다.

 

자료구조의 핵심은 ‘효율성’이다. 어떻게 하면 자료가 효율적으로 구조를 갖출 수 있는지’가 핵심인 것이다.

먼저, 프로그램에서 빈번하게 사용되는 자료구조를 살펴본 뒤 (배열, 구조체, 리스트, 스택, 큐, 트리, 그래프) 그리고 이러한 구조들을 조직하는 다양한 연산 알고리즘을 배우고 활용하여 문제를 해결할 것이다. 문제의 답이 나오는 게 중요한 게 아니라, 효율적으로 작성하는 법을 궁리하는 것이 중요하다.

 

 

 

 

 

 

2. 알고리즘

① 알고리즘이란?

어떠한 문제를 풀이하는 단계적 절차

 

알고리즘을 정확히 작성하는 것은 중요하지만, 무턱대고 코딩하는 것은 의미 없다. 처음 시작할 때 생각을 많이 해서 프로그램으로 넘어가는 게 중요하다.

 

 

② 알고리즘의 조건

입력: 0개 이상의 입력이 존재

출력: 1개 이상의 출력이 존재

명백성: 각 명령어의 의미는 모호하지 않고 명확해야 한다.

유한성: 한정된 수의 단계 후에는 반드시 종료된다.

유효성: 각 명령어들은 실행가능한 명령어들의 집합

 

 

③ 알고리즘의 기술 방법

1) 영어나 한국어와 같은 자연어: 사람이 읽기 쉽다. 그러나, 자연어의 단어들을 정확하게 정의하지 않으면 의미가 모호해질 우려가 있다.

 

2) 흐름도(flow chart): 순서도, 흐름도라고도 한다. 순서대로 간단한 기호와 도형으로 도식화한 것,

직관적이고 이해하기 쉬운 알고리즘 기술 방법, 그러나 복잡한 알고리즘의 경우 상당히 복잡해진다.

 

3) 의사 코드 (pseudo-code): pseudo = 유사하다, 유사 코드라고도 한다. 실제 프로그램 코드와 아주 비슷한 형태,

알고리즘 기술에 가장 많이 사용한다. 프로그램을 구현할 때의 여러가지 문제들을 감출 수 있다. 즉 알고리즘의 핵심적인 내용에 사용한다. 

 

4) 프로그래밍 언어

 

 

 

 

 

 

 

3. 프로그램이란?

프로그램 = 자료구조 + 알고리즘

 

100개의 데이터 중에서 최댓값을 구하는 프로그램을 작성하고 싶다면, 100개의 데이터가 어떤 구조를 갖게 할 것인지를 생각해야 합니다. 가장 좋은 방법은 배열에 순서대로 집어 넣는 것이다. 배열을 사용하지 않으면 각각의 데이터를 100번 집어 넣어야 하므로 매우 번거롭다. 따라서, 배열에 집어 넣는다는 것도 일종의 자료구조라고 볼 수 있다. 최댓값을 어떻게 구할 것인지 생각해서 적어보는 것은 알고리즘이다. 문제해결의 절차를 알고리즘이라고 하는데, 프로그램을 작성하기 위해서는 자료구조와 알고리즘이 결정되어야 한다. 그래서 프로그램은 자료구조와 알고리즘으로 구성된다 볼 수 있다.

 

 

문제

1) 문제를 풀기위한 단계적 절차는 (             )이다.

 

2) 알고리즘을 기술하기 위한 방법에는 자연어, 흐름도, (            ), 프로그래밍 언어가 있다.

 

3) 알고리즘이 되기 위한 조건이 아닌 것은?

   ① 출력           ② 명백성          ③ 유효성          ④ 반복성

 

<문제풀이>

1) 문제를 풀기위한 단계적 절차는 알고리즘이다.

2) 알고리즘을 기술하기 위한 방법에는 자연어, 흐름도, 의사코드, 프로그래밍 언어가 있다.

3) 알고리즘이 되기 위한 조건이 아닌 것은?    ④ 반복성

 

 

 

 

 

 

 

 4. 자료형

① 자료형 개념

자료형(data type): 데이터의 종류. 데이터의 집합과 연산의 집합.

자료형은 가질 수 있는 데이터의 범위를 지정해주고 가능한 연산이 무엇인지 정의하는 것이다.

자료형은 그 자료형이 갖는 데이터가 무엇인가, 그 데이터를 가지고 할 수 있는 연산이 무엇인가를 알면 만들 수 있다.

 

정수, 실수, 문자열 등 - 기초적인 자료형 ex

  int x;

  자료형 변수 ;

 

 

자료형은 이 데이터로 할 수 있는 연산이 무엇인지 알려준다. int x에서 x가 할 수 있는 연산은 사칙연산이다. char c에서 c가 가질 수 있는 데이터는 문자, 가질 수 있는 데이터가 True 혹은 False인 자료형은 논리형 데이터다. 자료형은 데이터의 종류를 의미하며, 기초자료형, 크게 숫자, 문자, 논리형 데이터 등이 있다. 위의 그림에는 나와 있지 않지만 사용자 정의 자료형의 대표적인 데이터형은 클래스다.

 

기초 자료형	사용자 정의 자료형
데이터가 하나 사용자가 만들지 않았지만 주어진 자료형	종합선물세트 사용자가 직접 만든 자료형

 

자료형을 만든다는 것은 그 자료형이 갖는 데이터가 무엇인가, 그 데이터를 가지고 할 수 있는 연산이 무엇인가를 알면 만들 수 있다.

 

 

② 추상 데이터 타입 (ADT: Abstract Data Type)

데이터 타입을 추상적(수학적)으로 정의한 것

 

추상데이터 타입에서는 일반적인 자료형과는 달리, 데이터나 연산이 무엇(What)인지는 정의되지만 데이터나 연산을 어떻게(How) 컴퓨터 상에서 구현할 것인지는 정의되지 않는다. 이러한 추상 데이터 타입의 개념은 객체 지향 프로그래밍과도 연관된다.

 

 

③ 객체지향프로그래밍

객체는 뭘까? 추상데이터 타입이라는 건데 추상 데이터 타입하면 뭐가 떠오를까? 바로 '클래스'다. 추상데이터 타입은 '클래스'다. 그럼 클래스는 뭐고, 객체는 뭘까? 클래스는 결국 '자료형'이다. 자료형의 용도는 변수를 선언하는 것으로, 자료형 중에서 클래스의 변수에 해당하는 것을 '객체'라고 부른다. 데이터 타입이 클래스인 변수를 객체라고 한다. 클래스로부터 객체를 선언해서 진행하는 프로그래밍 언어를 객체지향 프로그래밍 언어라고 한다.

 

추상 데이터 타입은 객체 지향 프로그래밍 언어를 이해하는 데 있어서 가장 중요한 개념이라고 할 수 있다.

추상 데이터 타입에서 '추상'이라는 말은 무슨 뜻일까?  '구체적이지 않음'을 의미한다. 데이터나 연산이 무엇인가는 정의되지만 데이터나 연산 무엇인지는 정의되지만 데이터나 연산을 어떻게 컴퓨터 상에서 구현할 것인지는 정의되지 않는다. What은 아는데 How는 모른다. 예를 들면, 리모콘 각각의 버튼 기능과 사용법은 알지만 작동과 제작 원리는 알지 못하는 것과 같다. 어떻게 구현하여 작동되는지는 모르고 사용하는 것을 '추상'이라고 일컫는 것이다. 이것이 바로 객체 지향의 핵심이다.

 

데이터 타입을 추상적으로 정의한 것으로, ADT를 모르면 객체지향을 하나도 모르는 것이라고 해도 과언이 아닐 정도로 이 둘은 연관이 깊으므로  꼭 기억하도록 하자.

 

 

④ 추상 데이터 타입의 정의

추상화(abstraction)은 정보 은닉

객체: 추상 데이터 타입에 속하는 객체 정의

연산: 이들 객체들 사이의 연산이 정의된다. 이 연산은 추상 데이터 타입과 외부를 연결하는 인터페이스의 역할을 한다.

 

밖에서 볼 때는 내부가 안 보인다. 그래서 '정보 은닉'이다. 정보가 숨겨져 있다. 정보를 왜 숨길까? 정보를 보호하는 차원에서 외부에 노출 시키지 않는 것이다. 즉, 보안상의 이유라고 말할 수 있다.

 

 

하나의 자료형을 구조체로 만들 것이다. 이것이 발전하면 스택이라는 클래스를 만드는 것이다. 큐라는 자료형을 만드는 것은 구조체를 만드는 것으로, 구조체를 만드는 것은 이후 C++이나 Java에서 클래스를 만드는 것과 원리가 동일하다. 구조체도 추상자료형으로 만드는 것이기 때문이다.  

 

이 책에서는 '가질 수 있는 자료의 집합'을 '객체'로 설명하고 있다.

추상 데이터 타입의 예: 자연수

객체: 0에서 시작하여 INT_MAX까지의 순서화된 정수의 부분 범위

추상 데이터 타입을 만들 때는 가질 수 있는 값의 범위(객체)와 연산(함수)을 써주지만(기능), 구체적인 구현 방법은 넣어 놓지 않는다.

 

 

⑤ 용어 정리

자료구조: 추상적 자료형이 정의한 연산들을 구현한 구현체,

프로그램 내의 자료들을 정리하고 보관하는 여러 구조.

 

자료: 현실세계에서 관찰 및 측정을 통해 수집된 값이나 사실 (ex. 자로 길이를 재는 것, 체온계로 체온을 재는 것)

 

정보: 어떤 상황에서 정확한 의사결정을 할 수 있게 하는 지식. 자료가 의미를 가지게 된 것.

 

추상화: 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 자료구조에 관해 공통 특징만을 뽑아 정의한 것.

시스템의 정말 핵심적인 구조나 동작에만 집중하는 것. 좋은 추상화는 사용자에게 중요한 정보는 강조되고 중요하지 않은 구현 세부사항은 제거된다.

 

ADT: 실제적인 구현으로부터 분리되어 정의된 자료형. 자료형을 추상적(수학적)으로 정의함을 의미한다. 

  - 연산을 정의할 때 연산명, 매개변수, 반환형은 정의하지만 연산을 구현하는 구체적인 코드는 주어지지 않는 것

  - ADT 안에 객체(objects)와 함수(functions)들이 정의된다.

  - 객체지향언어에서는 '클래스' 개념을 사용하여 ADT가 구현된다.

 

 

 

 

 

 

5. 알고리즘의 성능분석

① 알고리즘 성능 분석 방법

1) 수행 시간 측정 (거의 사용하지 않음)

 - 두 개의 알고리즘의 실제 수행 시간을 측정하는 것

 - 실제로 구현하는 것이 필요

 - 동일한 하드웨어를 사용하여야 함

 

거의 사용하지 않는 이유: 반드시 프로그램 코드가 있어야 하므로 이것이 꽤 큰 제약이 된다. 간단한 프로그램이 아니라 굉장히 큰 프로그램을 1년을 소요하며 만들고나서 테스트 한 후, 안 좋다며 버려야 하기 때문이다. 치명적 단점: 실제 프로그램이 돼 있어야 한다. + 하드웨어 조건도 컴퓨터마다 맞춰줘야 한다.

 

2) 알고리즘의 복잡도 분석: 실행횟수를 계산하는 방법이다.

 - 직접 구현하지 않고서도 수행 시간을 분석하는 것

 - 알고리즘이 수행하는 연산의 횟수를 측정하여 비교

 - 일반적으로 연산의 횟수는 n의 함수

 

 

 

 

 

② 왜 프로그램의 효율성이 중요한가?

약간의 차이만 나도, 데이터의 개수가 커질수록 엄청난 차이가 발생하기 때문이다.

또한, 프로그램은 데이터의 개수가 워낙 많은 것이 일반적이다.

 

 

 

 

 

③ 수행 시간을 측정하는 방법 

(이런 방법이 있다는 것만 알면 된다.)

#include <time.h>

Start = clock();

…

Stop = clock();

Double duration = (double)(stop – start) .

CLOCKS_PER_SEC;

 

 

 

 

 

④ 복잡도 분석 방법

복잡도 분석의 종류:

   시간 복잡도(time complexity) – 시간을 얼마나 많이 사용하는가, 연산의 횟수를 계산하여 분석

   공간 복잡도(space complexity) – 메모리를 얼마나 많이 사용하는가 (요즘에는 따지지X, 메모리 축소, 가격인하)

- 알고리즘 A~C를 비교하며 복잡도를 분석한다.

 

 

 

 

 

⑤ 빅오 표기법

자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있다.

N = 1000인 경우

T( ) =  +  + 1

 99.9%,  + 1 = 0.1%

제일 중요한 건  이야. 그래서 제일 중요한  만 표기하는 것이 빅오 표기법이야.

연산의 횟수를 단순화하기 위해 빅오 표기법을 쓴다. 이게 핵심이야.

+ 과거 컴퓨팅 파워가 팩토리얼형(빅오 표기법의 종류)을 처리할 수 없었는데 이제는 가능하므로 AI개발이 가능해졌다.

 

 

 

 

 

⑥ 최선, 평균, 최악의 경우

알고리즘의 수행시간은 입력 자료 집합에 따라 다를 수 있다.

- 최선의 경우(best case): 수행 시간이 가장 빠른 경우, 의미가 없는 경우가 많다.

- 평균의 경우(average case): 수행시간이 평균적인 경우

- 최악의 경우(worst case): 수행 시간이 가장 늦은 경우, 가장 널리 사용된다.

 

“내 알고리즘은 최악의 경우에도 이 정도예요” 라고 말해주는 것이 더 설득력 있다.

최선의 경우는 의미 없고, 일반적으로 시간 복잡도는 최악의 경우를 따진다. 경우에 따라서 평균의 경우를 따질 때도 있지만 일반적으로는 최악의 경우를 많이 고려한다.

 

ex) 순차탐색 (이 배열에 내가 찾고자 하는 것이 있는지 탐색하는 것)

최선의 경우: 찾고자 하는 숫자가 맨 앞에 있는 경우: O(1)

최악의 경우: 찾고자 하는 숫자가 맨 뒤에 있는 경우: O(n)

평균적인 경우: 각 요소들이 균일하게 탐색된다고 가정하면

(1+2+…+n)/n = (n+1)/2: O(n)     *빅오 표기법: n으로 생각

 

 

 

 

 

1장이 끝났다.