알고리즘을 공부하기 위한 기초 [ 자료 구조 ]

실 세계의 사실이나 현상을 기록한 것을 자료라고 할 수 있는데

알고리즘은 자료를 사용하려고 할 때, 주어진 문제를 해결하는 방법이다. 

 

문제 형태에 따라 

자료구조와 밀접한 관계를 가지고 있다. 

 

그렇기 때문에 자료구조에 대해 먼저 공부할 필요가 있다. 

 

자료구조란?

자료들 간 논리적인 관계라고 표현할 수 있다. 

 

자료구조는 형태에 따라

 

linear structure (선형구조)

non-linear structure (비 선형구조) 가 있다. 

 

먼저 선형구조는 대수학적으로 보면 집합으로 표현될 수 있다. 

 

선형구조에는 list, stack, queue, deque

비선형구조에는 tree, graph 가 있다.

 

1. list

linear list  :연속적인 기억장소에 저장

linked list : 비연속적으로 저장

 

linear list는 말 그대로 인접한 원소들의 배치이다. 배열이라고 보면 쉬울 것같다.

주기억장치의 address의 특징을 이용하여 인접하게 원소를 배치하는 것이다. 

순차리스트(sequence list) or 연접리스트 (dense list) 라고한다 .

 

linked list는 말 그대로 link로 연결시켜서 원소들을 배치한다. 원소들 간 논리적인 배치가 이루어져있다.

노드의 포인터 부분을 이용하여 서로 연결시켜 논리적으로 배치가 이루어 지게 한다.

 

linear list 의 

- 장점

저장구조가 간단하다, 기억장소 저장효율이 뛰어나다(순서대로 붙어있기 때문에), 접근속도(검색)가 빠르다

- 단점

삽입과 삭제 시 모든 자료의 이동이 필요하기 때문에 쉽지가 않다.

linked list 의

- 장점

자료의 삽입과 삭제가 용이하다, 리스트를 분리하기 쉽다

- 단점

접근속도(검색)가 느리다, 포인터를 위한 추가공간이 필요하다, 저장효율이 나쁘다, 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

- 종류

단순 연결 리스트, 이중 연결 리스트, 단순 환영 연결 리스트