최근 다시 Data structure와 Algorithm을 학습하기 위해 찾은 Site가 아래의 사이트이며,
책은 현재 C로 구현한 알고리즘 및 기타 책으로 보고 다시 확인을 하고 있다.
기본적으로 한글 번역서는 영어 용어와 가끔 혼동이 있어,
이를 가끔적 영어를 사용하려하고 표기하려고 한다.
정말 아래의 사이트 진심으로 감사 할뿐이다.
https://www.tutorialspoint.com/data_structures_algorithms/index.htm
2. Data Structure 의 기본 학습
한글로 하면, 데이타의 구조이며, Data 구조의 특성을 나타내는 것인 것 같다.
간단하게는 int, float, char 부터 C언어의 array가 될 수도 있고,
복잡하게 들어간다고 하며, C언어에서는 structure문으로 구성하여 data를 저장하고
간단한 저장방식을 제공하는 연산이 필요한 Linked List , Set ,Stack, Queue가 이에 포함되겠다.
Data Structure 기반으로 어떻게 구현 어떻게 효율적으로 동작하게 하는 것이 알고리즘이 되겠다.
2.1 Data Structure 관련 용어
- interface
interface는 오직 지원되는 동작 기능중 지원하며, interface가 사용가능한 parameter 받고 return을 해준다.
예를 들면, LIFO, FIFO, Single Linked List , Double Linked list interface가 아닐까 싶다.
- Implementation
예를들면, Data structure의 구현된 전체 구조를 말하며, Linked List, Set , Stack, Queue 같은 구현물이 아닐까 싶다.
2.2 Data Structure의 특성
- Correctness
Linked List나 Set , Stack은 보면 알수 있겠지만, 당연한 말 같다.
- Time Complexity
- Space Complexity
https://www.tutorialspoint.com/data_structures_algorithms/data_structure_overview.htm
2.3 Data Structure 의 기본
Data structure의 Data Type은 두가지로 구분이 되며,
- Built-in Data Type (기본적 Data Type)
- Derived Data Type (파생된 Data Type)
- List : Linked List를 말하는 것 같다.
- Array : Built-in Data or Structure의 단순 Array 방식
- Stack : Array or Linked List
- Queue: Array or Linked List
- Graph : Graph도 내부적으로 보면, Set or Matrix로 표현이 가능한데,
- Set : Linked List로 구현 가능
- Tree: Binary Tree or Tree는 Set으로 구현 가능
- Basic Operation 설명
아래와 같이 Tree기준으로 보면 간단히 설명을 하면, 아래와 같은 Operation들이 존재하며,
구지 Tree가 아니라도, 기본적인 Operation들은 거의 유사하다.
- Traversing : 순회, Tree에서 자주사용이 되며 Tree를 전체 순회를 하는것이다.
- Searching : 찾기, Tree에서 자주사용이 되며, 비교하여 하나를 선택하여 찾는방식
- Insertion: 삽입, Item을 삽입하는 방식
- Deletion: 삭제 , Item을 삭제하는 방식
- Sorting : 정렬, Item들을 대소를 비교하여 정렬을 한다.
- Merging: 합치기, Tree에서 자주 볼수 있지만, Set에서도 볼수 있다.
사실 위 Operation 때문에, Algorithm 과 Data Structure의 구분이 약간 모호 한 것 같다.
Tree or Graph 는 Data structure 이고, 기본 Operation을 제공을 하며 움직인다.
여기까지는 Data structure이지만, 최소신장 Tree 처럼 Tree를 이용하여 다시 새로운
Operation을 하는 것이 이런 부분이 알고리즘으로 구분이 되는 것 같다.
https://www.tutorialspoint.com/data_structures_algorithms/data_structures_basics.htm
https://www.tutorialspoint.com/data_structures_algorithms/array_data_structure.htm
3. Algorithms analysis 알고리즘 기본분석
이 사이트에서 책보다 새롭게 Data structure와 Algorithm의 구분이 명확하게되었다.
일단 Algorithm은 Data structure 기반으로 구성이 되어있으며, 이 관점에서 본다면,
아래의 다섯가지로 나누어진다.
알고리즘은 Data structure 기반으로 움직이는 방식으로 보면되겠다.
물론 이 방식이 여러 방식이 존재 하겠지만, 이에 따라 알고리즘역시 변경이 되겠고,
동일한 Data structure를 가지고, 다른 알고리즘을 사용하여 비교 할수도 있겠고,
Data structure를 변경하여 , 동일한 알고리즘을 사용해도 되겠다.
그러기에 알고리즘(Algorithms)은 자료구조(Data Structure) 와 분리 하기는 어렵겠다.
왜냐하면, 알고리즘의 목표는 성능인데, 자료구조 역시 성능에 영향을 미치기 때문이다.
기본적으로 알고리즘의 성능분석은
Time Complexity의 거의 촛점이 맞추어져 있으며,
더불어 측정을 한다면, Space Complexity도 이용하여 알고리즘의 성능분석하자.
이럴 경우, 아래와 같이 나누어서 살펴보자.
- Best Case : 거의사용되지 않는다고 한다.
- Average Case : 평균의 상황 , 이는 측정이 어렵고, 정확하지가 않다.
- Worst Case : 최악의 상황
이 분석에서 가장 중요한 것은 Worst Case이다.
대부분의 알고리즘이 Worst Case에 근사하게 움직이며 동작하기이라고 한다.
그리고, Average Case도 사용이 되지만 측정이 어렵고, 정확하지가 않다.
하지만, 예외사항 같이 확률적으로 적용할 경우, 이야기는 좀 달라진다.
Quick Sort 같이 정확한 확률적으로 계산적용을 한다면, Average Case가 중요하다.
그래도, Worst Case를 절대 간과해서는 안된다.
내 개인적인 생각으로는 통계치 기반으로 된 데이타기반으로 된 경우에는
Best Case 인 경우는 알고리즘을 적용하고 한다면 아주 중요하게 될 것 같다.
이것은 내 개인적인 생각이다.
이를 표시하는 방법도 다양하지만, 거의 Big O Notation을 사용한다.
다른 것은 생략하며 아래 사이트를 참고하자.
https://www.tutorialspoint.com/data_structures_algorithms/algorithms_basics.htm
https://www.tutorialspoint.com/data_structures_algorithms/asymptotic_analysis.htm
4. WEB 에서 기본 TEST 환경
현재 내가 가장 익숙한 언어는 C 언어이며, Java와 여러 언어를 경험을 했지만,
그래도 C가 가장 익숙하고 편한다.
만약 현재 Build 환경이 구축이 되지 않았다면, 아래의 사이트에서 Compile 및 결과를 확인가능하다.
아래사이트는 Memory 사용량을 계산을 해주기때문에, 너무 감사하다.
http://ideone.com/