자료구조(Data Structure)

자료구조 (Data Structure)

많은 사람들이 코딩테스트를 통과하기 위해 자료구조와 알고리즘을 공부하곤 합니다.

그렇게 접근하는 경우가 많다보니, 때로는 자료구조 = 알고리즘 이라는 잘못된 지식을 갖고 계신 분들고 적지않게 보았습니다.

 

그렇다면, 자료구조는 대체 무엇일까?

저는 자료구조는 데이터를 "효율적"으로 관리할 수 있는 구조 라는 것이 제일 적합하다고 판단됩니다. ( 더 좋은 정의표현이 있으면 알려주세요 )

데이터의 집합, 명령, 관계 등등이 설명에 포함되지만, 결국 "효율적"으로 관리하는 구조를 만들기 위함이겠지요.

 

 

자료구조(Data Structure) 종류

배열(Array)

배열리스트(ArrayList)

연결리스트(LinkedList)

스택(Stack)

큐(Queue)

힙(Heap)

트리(Tree)

그래프(Graph)

등등...

정말 많은 자료구조 들이 있습니다. 각 자료구조는 특징을 갖고 있고, 그 특징은 따로 각 자료구조에 따른 설명글로 대체하겠습니다.

 

선형 구조와 비선형 구조

자료구조는 크게 선형구조와 비선형구조로 나뉩니다.

어떤 기준에서 나뉘는가를 생각해보면, 간단하게

선형구조 : 배열, 스택, 큐 등

A - B - C - D - E

처럼 순서대로 구조를 이룹니다.

이처럼 앞의 데이터와 뒤의 데이터가 1:1 로 나열된 구조입니다.

 

비선형구조 : 트리, 그래프 등

A - B - C

A - C - D

처럼 A 다음에 B,C 로 갈수있고, B 는 C 로 갈수있고, C는 D로 갈수 있습니다.

이처럼 앞의 데이터와 뒤의 데이터가 1:1 or 1:n or n:1 or n:m 등으로 나열된 구조입니다.

 

어떤 자료구조(Data Structure) 선택의 기준

자료구조를 선택한 이후 효율적인 알고리즘(문제해결과정) 이 정해지는 경우가 있고, 또는 1차적으로 알고리즘 이후에 자료구조가 정해지는 경우도 있습니다.

그러나 중요한 것은 "자료구조" 는 반드시 결정되어야 한다는 것입니다.

이런 측면에서 우리는 어떤 "자료구조" 를 선택해야 할까? 를 반드시 고민하게 됩니다.

 

1. 시간복잡도

2. 공간복잡도

 

가 적을수록 효율적이다. 라고 할 수 있겠습니다만, 이는 정말 쉽지 않습니다.

공간복잡도는 높지만, 시간복잡도가 낮은경우

시간복잡도는 높지만, 공간복잡도가 낮은경우

처럼 완전 비례하지 않는 경우가 생깁니다.

 

때에 따라서는 자신의 상황에 맞게 타협가능한 수준에서 효율성을 결정하고, 그에 따라 많은 자료구조의 특징을 학습하고, 그 자료구조중 무엇을 택해야 하는지 결정해야 하는 능력이 필요하다고 판단됩니다.