자료구조 (Data Structure)

데이터를 효율적으로 관리하기 위해서 만든 구조.

알고리즘 (Algorithm)

어떠한 문제를 해결하기 위해 명확히 정의된 유한한 규칙과 절차들의 집합.


추상적 자료 구조 (Abtract Data Struct)

효율적인 자료구조를 만들기 위해 기능을 추상화하고 기능에 대한 연산 복잡도를 그 위에 추가적으로 정의한 것. 사용자는 내부를 몰라도 됨 == 인터페이싱

추상적 자료형(Abstract Data Type)와 비슷하지만, 자료 구조를 생성하는 데 한정되어 있다. 자료구조를 사용해 연산에 대한 복잡도를 추가된 것.

일반 ADT >> 데이터 + 절차

>> 삽입, 삭제, 검색을 위해서는 연산 시간이 얼마나 걸릴지.

>> 연산 복잡도 = 시간 복잡도 + 공간 복잡도

알고리즘 :

주어진 문제를 해결하기 위해 명확하게 정의된 절차와 규칙들의 유한 집합이다.

-> 문제 해결 방법. 문제를 해결 하기 위한 단계적인 절차



ex) 동대문 시장에서 김씨를 찾아와라 최대한 빠르게.

-> 1. 찾는 것이 가장 중요. [아무리 빠르더라도 문제를 해결하지 못하면 무쓸모]

-> 2. 문제 해결 중에서 얼마나 더 빠르게 할 수 있는지,


-> 3. '유한'해야한다. 알고리즘은 검증할 수 있어야하는데, 무한한 절차와 규칙을 수행한다면 이것은 검증 될 수 없다.


최대 공약수와 최소 공배수도 알고리즘.

1을 제외한 수로 곱해서..



What , How 생각 모델.


What -> 무엇을

How -> 어떻게


What1 -> How1

What2(How1) -> How2

What3(How2) -> How3


How가 나오면, 해당 How는 새로운 What이 된다.


What : xx은행 옆에 있는 빵집을 찾아야한다

How : 찾기 쉬운 xx은행을 먼저 찾는다.


What : 찾기 쉬운 xx 은행을 찾아야한다

How :: xx 은행이 어디 있는지 사람들에게 물어본다.




What -> 문제 (목적)

How -> 알고리즘 (해결 방법)


알고리즘의 조건 5가지


1. 입력('없음'입력도 입력이다. void. 0개 이상의 입력이 필요하다)

2. 출력[입력과 출력이 없다면 그것은 프로시저(절차)]

3. 명확성[어떤 것을 하는지 좋고 나쁨이 확실해야함] 

4. 유한성[종결성](끝나지 않으면 검증 , 사용할 수 없다)

5. 효율성(물론 실행이 가능해야한다.)



오토마타(Automata) 이론



자료구조 : 










'프로그래밍 > 자료구조, 알고리즘' 카테고리의 다른 글

덱(deque)  (0) 2016.01.29
빨간 눈의 승려 문제.  (0) 2015.04.12
자료구조 / 알고리즘  (0) 2015.04.02
Posted by GENESIS8

댓글을 달아 주세요