[자료구조] 1. 자료구조와 알고리즘, 추상 자료형(ADT)

 

1.1 자료구조와 알고리즘

      1) 자료구조

      2) 알고리즘

 

1.2  추상 자료형(ADT) 

 

1.1 자료구조와 알고리즘

 

1) 자료구조 

 

자료구조 : 데이터의 표현 및 저장 방법.
                 자료들을 정리하여 보관하는 여러 가지 구조들.

 

[자료구조 분류]

2) 알고리즘 

 

 

알고리즘 : 문제의 해결 방법.
                  컴퓨터로 문제를 풀기 위한 단계적인 절차.
                  특정한 일을 수행하는 명령어들의 집합.

 

자료구조가 결정되어야 그에 따른 효율적인 알고리즘을 결정할 수 있기 때문에 자료구조와 알고리즘은 밀접한 관계를 갖고, 알고리즘은 자료구조에 의존적이다. 

 

 

[알고리즘의 조건]

입력 : 0개 이상의 입력이 존재해야 한다. 

출력 : 1개 이상의 출력이 존재해야 한다. 

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

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

유효성 : 실행 가능한 연산이어야 한다.

 

 

[알고리즘의 기술 방법]

자연어 

흐름도 (flowchart)

의사코드 (pseudo-code)

프로그래밍 언어

 

---

1.2 추상 자료형

 

자료형(data type) : 데이터의 종류.
                                데이터의 집합과 해당 데이터 간에 가능한 연산.

 

•   기초 자료형 - int / float / double / char 
•   파생 자료형 - 배열 / 포인터
•   사용자 정의 자료형 - 구조체 / 공용체 / 열거형 

 

* 가능한 연산의 종류를 결정하는 것도 자료형의 일부. => 자료형의 정의에 기능 또는 연산과 관련된 내용을 명시할 수 있음.

 

// 자료형 Wallet 정의
typedef struct _wallet
{
 int coin100Num; // 100원짜리 동젂의 수
 int bill5000Num; // 5,000원짜리 지폐의 수
} Wallet;

// 자료형 Wallet 정의의 일부 (가능한 연산)
int TakeOutMoney(Wallet * pw, int coinNum, int billNum); // 돈 꺼내는 연산
void PutMoney(Wallet * pw, int coinNum, int billNum); // 돈 넣는 연산

 

 

 추상 자료형(ADT : Abstract Data Type) : 추상적, 수학적으로 자료형을 정의한 것.
구체적인 기능의 완성 과정을 언급하지 않고 순수하게 기능이 무엇인지를 나열한 것.

 

=> 구현 세부 사항은 외부에 알리지 않고 외부와의 인터페이스만을 공개한다. 인터페이스만 정확하게 지켜진다면 ADT는 여러 가지 방법으로 구현될 수 있다. (구현으로부터 명세의 분리)

* 각종 자료구조들의 ADT는 표준이 아니다. ADT는 필요에 따라 내용에 차이가 있을 수 있고 확장도 가능하다.

* ADT를 명시하는 별도의 정해진 표기법이 있는 것은 아니다.

 

[ADT 예시]

Wallet의 ADT

Operations : 

    ◾ int TakeOutMoney(Wallet * pw, int coinNum, int billNum)
        - 첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다. 
        - 두 번째 인자로 꺼낼 동전의 수, 세번째 인자로 꺼낼 지폐의 수 를 전달한다. 
        - 지갑에서 꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다.

     ◾ int PutMoney(Wallet * pw, int coinNum, int billNum)
        - 첫 번째 인자로 전달된 주소의 지갑에 돈을 넣는다.
        - 두 번째 인자로 넣을 동전의 수, 세 번째 인자로 넣을 지폐의 수를 전달한다. 
        - 지갑에 넣은 만큼 동전과 지폐의 수가 증가한다. 

자연수 Nat_Number의 ADT

◾ 객체 : 0에서 시작하여 INT_MAX까지의 순서화된 정숭의 부분 범위
◾ 함수 : 
     Nat_Number zero()   ::= 0
     Nat_Number successor(x)   ::= if (x == INT_MAX) return x
                                                       else return x+1
     Boolean is_zero(x)   ::= if (x) return FALSE 
                                           else return TRUE
     Boolean equel(x,y)   ::= if (x ==y) return TRUE
                                           else return FALSE
     Nat_Number add(x,y)   ::= if ( (x+y) <= INT_MAX ) return x+y
                                                else return INT_MAX
     Nat_Number sub(x,y)   ::= if (x<y) return 0
                                               else return x-y