소프트웨어 개구리

Abstract Data Type

data type, 혹은 데이터형

C언어에서 변수들은 data type을 가진다.

가장 대표적인 것인 int, 

int는 정수값을 말한다. 

int형의 변수에는 음의 정수, 0, 양의 정수를 저장할 수 있다.

실수값을 저장할 수 있는 data type은 float, 혹은 double

또는 새로운 데이터형을 만들 수도 있다.

struct를 이용하는 것이다.

예를 들어,

와 같이 하면

struct A라는 새로운 data type을 만든 것이다.

그리고 struct A a라고 하면,

a 라는 변수를 만든 것이고,

이 변수의 data type은 struct A가 된다.

abstract data type

Abstract Data Type (줄여서 ADT)라는 것이 있다.

data type은 데이터형이니 이해하는 데 아무 문제가 없을 것인데,

abstract가 앞에 붙었다.

Abstract의 사전적 의미는 '추상적'이다.

우리말로 하면, ADT는 추상데이터형 이라고 번역하면 되겠다.

그래도 이게 뭔지 잘 이해가 되지 않을 것이다.

우선, 정의부터 얘기하자면

ADT라는 것은 '데이터를 저장할 수 있는 공간'과 '그 공간을 사용하는 방법'을 정의한 것이다.

정의를 얘기해도 뭔말인지,, 

그럼, 비유를 들어서 얘기해보자.

데이터 '물'이 있다. 먹는 물을 말하는 것이다.

물을 저장할 수 있는 공간을 신이 창조하면서 '냄비'라고 했다고 하자.

'물을 저장할 수 있는 공간' = '냄비' = '데이터를 저장할 수 있는 공간'

'냄비'는 data type이 된다.

'냄비'를 사용할 수 있는 방법을 생각해 보자.

1. 물을 넣다.

2. 물을 비우다.

3. 물을 데우다.

(1, 2, 3 방법) = '냄비를 사용하는 방법' = '고 공간을 사용하는 방법' 

이렇게 '냄비'라는 저장공간을 만들면서, 그 공간을 사용하는 방법까지 정의한 것을

abstract data type이라고 한다.

비유를 다 걷어내고 말하면,

Abstract data type이란 데이터공간구조와 그 구조를 사용할 수 있는 방법을 같이 정의한 것

데이터구조란 결국 ADT를 정의하고, 그것을 프로그래밍 언어로

구현한 것에 불과하다.

예를 들어, 필요한 ADT가 다음과 같은 것이라고 하자.

숫자를 저장하는 공간인데, 

거기에 숫자를 넣을 수도 있고,

꺼낼수도 있는데, 꺼낼 때는 넣은 순서대로 꺼내어진다.

데이터공간구조는 "숫자를 저장하는 공간"이고,

사용방법은 "숫자를 넣고, 넣은 순서대로 꺼내어진다."가 된다.

위에서 설명한 ADT는 Queue(큐)라는 것이다.

이런 ADT도 있다.

숫자를 저장하는 공간인데,

거기에 숫자를 넣을 수도 있고,

꺼낼 수도 있는데, 꺼낼 때는 넣은 순서의 역순으로 꺼내어 진다.

이것은 Stack (스택)이라는 ADT이다.

데이터구조를 공부한다는 것은

이러한 ADT들을 공부하고,

필요에 따라 새로운 ADT들을 만들 수 있는 능력을 키우는 것이다.

typedef 사용하기

매크로

C언어에서 macro라는 것이 있다.

말로 설명하기는 좀 그렇지만,

#define AAA 10

이런 거다.

이것은 소스코드에 나타나는 AAA를 모두 10으로 처리하게 하는 것이다.

왜 이런 매크로를 사용하는가?

1. 가독성

2. 편리성

3. 오류방지

세 가지 정도의 이유가 있다.

예를 들어, 3.1415921564,, 파이값, 원주율을 소스코드에서 사용한다고 하자.

그것도 아주 많이.

이 숫자가 길어서, 문제가 많다.

1. 소스코드가 지저분해서 보기가 싫다. --> 가독성이 떨어진다.

2. 숫자가 긴 파이값을 입력하기가 불편하다 ---> 편리성이 떨어진다.

3. 파이값 입력하다가 오타나기가 쉽가 --> 오류가 쉽게 생긴다.

그래서,

#define PI 3.1415921564

이렇게 해놓고, 소스코드에서는 PI만 쓰면

문제점, 1, 2, 3를 한 번에 해결할 수 있다.

typedef

만약에,

int 라는 데이터형 이름이 마음에 안든다고 하자.

왜 마음에 안들지?

글쎄,, 날 버리고 매몰차게 떠난 그 사람의 이름이 "김int"라고 하자.

가뜩이나 힘들어 죽겠는데,

C언어 프로그래밍 할 때마다, int가 나오면 이건 더 죽을 맛이다.

이 때 int 대신 다른 것을 쓸 수 있도록 해주는 것이 typedef이다.

이렇게 하면, int 대신에 byebye를 해도 된다.

int a, b, c; 이렇게 코딩하던 것을 

byebye a, b, c; 이렇게 해도 된다는 것이다.

물론,,,

헤어진 연인의 이름을 피하기 위해 typedef가 생기지는 않았다.

typedef는 긴 data type이름을 사용하는 불편함을 없애기 위한 것이다.

긴 data type 이름이란 무엇인가?

구조체를 새로 만들어 보자.

이제 새로운 data type struct ABCD가 생긴 것이다.

이 type을 갖는 변수를 만들려면,

다음과 같이 해야 한다.

이렇게 했을 때 문제점은

1. 불편해

2. 틀리기 위해

3. 소스가 지저분해져

이를 해결하려면 typedef를 사용하면 된다.

1. struct를 정의하면서 이름을 바로 YYY로 하는 방법도 있고,

2. struct abc를 정의한 후에, typedef를 이용해서 이름을 YYY로 개명하는 방법도 있다.

위에서 설명한 내용을 동영상에서 "무미건조"하게 설명합니다.

알고리즘이 우수한가?

같은 문제에 대해 이를 해결할 수 있는 알고리즘은 여러 개가 있을 수 있다.

어느 것이 더 우수한지 비교할 수 있는 기준은 무엇인가?

기준은 크게 두 가지가 있다.

하나는 시간이고, 다른 하나는 공간이다.

시간은 알고리즘을 이용해서 문제를 풀 때 시간이 얼마나 소요되느냐 하는 것이다.

공간은 알고리즘이 수행되기 위해서 얼마만큼의 메모리가 필요하느냐 하는 것이다.

시간복잡도,  

알고리즘의 우수성을 사용하는 시간측면에서의 기준을 말한다.

영어로는 time complexity.

예를 들어,

1부터 정수 숫자 n까지 모든 숫자를 더해서 합을 구하는 문제를 생각해보자.

이 문제를 푸는 방법에는 두 가지가 있다.

즉, 두 가지 알고리즘이 있다.

첫 번째 알고리즘은 누구나 생각할 수 있는 간단한 방법이다.

1부터 n까지 숫자를 하나씩 더하면 된다.

C언어로 프로그래밍하면 다음과 같다.

두 번째 알고리즘은 파스칼이 생각해낸 방법이다.

어린 시절 파스칼은 1부터 10까지의 합이 55라는 것을 

아래와 같은 천재적인 방식으로 알아냈다.

어느 것이 시간복잡도면에서 더 우수한가?

첫 번째 알고리즘은 n이 커질수록 계산하는 데 시간이 더 오래 걸린다.

for-loop 반복횟수가 많아지기 때문이다.

두 번째 알고리즘은 n의 크기와 상관없이 아래와 같은 공식으로 계산이 가능하다

따라서 두 번째 알고리즘이 첫 번째보다 시간 복잡도면에서 우수하다고 할 수 있다.

Big-O notation

시간 복잡도를 나타내기 위해서 사용하는 표현식이다.

읽을 때는 '빅 오 노테이션'이라고 읽는다.

첫 번째 알고리즘의 시간복잡도를 big-O notation으로 쓰면

O(n)이 된다. 

즉, n에 비례하여 걸리는 시간도 그만큼 증가한다는 것이다.

두 번째 알고리즘의 시간복잡도는 O(1)이다.

즉, n에 상관없이 항상 일정(1)하다는 것이다.

특히 어떤 문제에 대해 O(1) 알고리즘을 만들어 낼 수 있다면 

최상의 해결책을 찾아낸 것이다. 

다양한 시간복잡도

O(n) 시간복잡도의 알고리즘과 시간복잡도를 보자면

당연히 후자 알고리즘이 시간이 더 많이 걸린다는 것이다.

이 외에도 같은 것도 있다.

이것은 보다는 우수하지만, O(n)보다는 시간이 오래 걸리니 좋지 않다.

알고리즘의 시간복잡도를 나타내는 Big-O notation에 대해서 설명합니다.