정해진 데이터 vs 임의의 데이터 집합

정해진 데이터 vs 임의의 데이터 집합

자료구조(ex,tree)문제를 풀다 보면 데이터 집합이 정해진 문제가 나오거나 조건을 만족하는 모든 데이터의 집합을 구하는 문제가 나옵니다. 예전에, 저는 이러한 문제들을 자료구조라는 카테고리에 묶어두었는데, 자료구조에 대한 내용은 데이터 집합이 정해졌 때 행해지는 operation에 대한 정의라고 생각합니다.

정해진 데이터

자료구조에 대한 내용을 보면 자료구조의 construction, insert,delete 등의 연산이 정의되어 있습니다.

예시를 들어 보겠습니다.

이러한 이진 트리가 주어졌다고 하겠습니다. 이진 트리의 operation은 위와 같이 트리가 정해져 있어야 합니다. 15라는 노드를 삽입할려면 14의 노드의 right child node로 삽입을 합니다. 13이라는 노도를 삭제하려면 14의 left child가 None 노드를 가리키게 했습니다. [8, 3, 10, 1, 6, 14, 4, 7, 13] 라는 시퀸스가 주어졌을 때 binary search tree를 construct 하면 위와 같은 binary search tree가 나올 겁니다. data 집합이 정해지고 이에 대한 질문이 들어온다면 자료구조의 정의와 operation 및 application 지식을 이용하면 될 거 같습니다.

임의의 데이터 집합

노드가 n개인 모든 binary serach tree를 찾으라는 문제가 주어질 수 있습니다. 어떤 조건이 주어졌을때 , 이를 만족하는 모든 data structure를 찾으라고 주어질 수 있습니다. 이러한 경우, 모든 경우의 수를 생각하는 brute-force(backtracking)을 먼저 떠올린 다음에 이를 최적화는 dynamic programming으로 문제해결전략을 정하면 좋은거 같습니다.

결론

사실 , 별거 아닌 내용일 수 있는데 , 언젠가 나중에 data structure 에 관련된 알고리즘 문제를 보게 된다면 , operation을 먼저 떠올리는 상황이 발생할 거 같습니다.그래서, 한번 회고 느낌으로 정리해봤습니다.