자료구조란?

자료구조의 역할 - 왜 중요한가?

Computer : 문제(계산)을 풀기 위한 H/W

Algorithm : 문제를 푸는 방법 S/W

Data Structure : 문제를 이루는 재료의 구성

 

알고리즘을 이용해서 문제를 풀 때 이 문제를 구성하는 어떠한 방식이 있는데 이때 이 방식을 자료구조라고 할 수 있다.  즉, 알고리즘은 자료구조에 굉장히 큰 영향을 받게 된다. 예를 들어, 문제를 스택을 쓰는 방식, 큐를 쓰는 방식 같이  자료구조가 달라진다면 알고리즘 또한 당연히 달라지게 된다.

 

Computer는 문제를 풀기위한 장치라고 했는데,

세상을 문제의 세계로 바라본다면...

1. 답이 있는 문제 

2. 답이 없는 문제

3. 답이 있는지 없는지 모르는 문제

세개로 구분할 수 있다. 

 

이러한 문제를 자료구조와 알고리즘을 이용해서 풀 수 있는데, 컴퓨터라는 하드웨어에서 돌아가게 된다.

컴퓨터라는 것은 유한하다. CPU, 메모리의 양이 한정적이라는 것이다. 문제를 푸는 공간이 유한하기 떄문에

우리는 비용의 한계, 시스템적인 한계의 바운더리 안에서 문제를 풀어야 한다.

1.답이 있는 문제는 알고리즘의 영역 이다.

2. 답이 없는 문제는 근사치를 구하는 방식을 이용할 것이다.

3. 답이 있는지 없는지 모르는 문제(Theory of Computation의 영역)

 

<핵심내용>

• 알고리즘은 답이 없는 문제를 다루지 않는다. 
• 알고리즘에서 다루는 문제는 모두 답(해)를 갖고 있다.
• 알고리즘은 최적의 해를 찾는 것이 핵심이다.
• Solution A,B,C가 있다고 해도 그 중에서도 가장 최적인 해를 찾는다.
• 알고리즘의 최적의 해는 자료구조의 영향을 받는다. 
• 컴퓨터로 문제를 풀어야하니, 모든 것은 비용(Cost)과 연계된다.