목차

1. 확정적 결과

2. 복잡도

3. 데이터 구조
   a. 포함 계층 구조

4. 결론

1. 확정적 결과

프로그램을 설계할 때 가장 중요한 것은 불확실성이 생기면 안된다는 것이다. 알고리즘을 설계할 때도 마찬가지이다. 대표적인 불확실성으로 cycle(순환)을 예로 들 수 있다. 만약 cycle(순환)이 없으면 확정적 결과는 무조건 찾을 수 있다. 그렇다면 그 다음 관건은 복잡도 효율성이다.

2. 복잡도

알고리즘에서 많이 사용하는 개념으로 시간 복잡도라는 것이 있다. 시간 복잡도란 “문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.” [위키백과] 같은 결과를 얻는 방법이라면 시간복잡도가 가장 낮은 알고리즘, 즉 가장 빨리 결과를 찾아내는 방법을 채택하는 것이 일반적인 경우일 것이다.

3. 데이터 구조

앞서 말한 확정적 결과를 얻고 복잡도를 개선하기 위해서는 알맞은 데이터 구조를 선택해야한다. 데이터 구조는 노드와 링크로 구성된다. 노드란 데이터를 포함하고 있는 원소를 의미하고, 링크는 노드와 노드를 연결하며 방향성을 가지고 있다.

• Linear List (선형 구조) : 부모와 자식을 1대1로 연결하는 리스트 구조이다.
• Tree : 부모와 화살표 끝이 무조건 1개여야 하는 제약조건이 존재한다. 최상위 부모는 Root, 최하단 자식은 Leaf 노드라고 부른다. 트리의 종류로 “Binary Tree(이진 트리), Ternary Tree, Binary Search Tree(이진 탐색 트리), Complete Binary Tree(완전 이진 트리), Full Binary Tree, Perfect Binary Tree 등”이 있다. [출처 : https://lifelife7777.tistory.com/133]
• Graph : Tree 구조에서 부모가 1개여야 하는 제약 조건이 없어진 구조를 의미한다. 그래프 구조는 cycle이 생길 수 있기 때문에 확정적 결과를 얻지 못 할 가능성이 생긴다.

a. 포함 계층 구조 (Aggregation Hierarchy)

구성하는 부품에 대한 것을 포함하고 있는 구조를 포함 계층 구조라고 한다. 대표적으로 Tree 구조가 이에 해당된다. Tree 구조에서 자식을 가진 노드(다른 것으로 구성된)는 composite node라고 하고, 제일 하단에 존재하는 노드들은 primitive node라고 한다. Tree 구조는 복잡도가 낮아 데이터 검색 시간을 줄여주기 때문에 사람들이 가장 많이 쓰는 자료구조이다. 포함 계층 구조는 실생활에서도 많이 쓰인다. 예를 들어 옷장은 외투, 상의, 하의 옷장 등으로 구성되어 있고 또 각각의 옷들로 구성되어 있다. 또한 우리나라의 도-시군구-읍면동 주소 체계, html tag 구조 등 수많은 구조들이 tree 형태로 되어 있다.

4. 결론

프로그램을 설계할 때에는 확정적 결과와 복잡도에 대해 고민해야 한다. 확정적 결과를 얻기 위해서는 cycle(순환)이 발생하지 않도록 올바른 데이터 구조를 사용하여 데이터들을 정리해야 한다. 그렇게 하기 위해서는 다양한 데이터 구조들을 정확하게 이해하고 있어야 할 것이다.