[ Data Structure ]

<< 자료구조 (Data Structure) >>

[ 정의 ]

사전적의 의미로는 데이터의 집합을 의미하며, 데이터의 처리를 조금 더 효율적으로 수행할 수 있도록 한 구조 입니다.

 

[ 목적 ]

데이터를 효율적으로 저장하고 관리하고 처리할 수 있으며, 메모리 용량을 절약할 수 있습니다.

 

[ 분류 ]

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

선형 자료구조는 데이터가 일렬로 나열된 구조 이며, 비선형 자료구조는 어떤 특정한 형태를 띄고 있는 구조 입니다.

 

---

<<  선형구조 >>

[Array (배열)]

여러 데이터들을 하나의 이름으로 그룹핑하여 관리할 수 있는 자료구조 입니다.

index를 통해 데이터에 접근할 수 있습니다.

정적으로 저장 공간이 정해지기 때문에, 만약 데이터가 저장 공간을 초과할 경우 새로 배열을 재 할당 하고 데이터들을 복사해야 합니다.

Array	List
순서가 유지되고, 중복으로 데이터를 저장할 수 있습니다.
고정길이 초기에 지정된 크기를 초과하면 해당 배열을 재 할당해야 하는 번거로움이 있습니다.	가변길이 크기에 제약이 없기 때문에 배열처럼 굳이 재 할당할 필요가 없습니다.

 

[ ArrayList ]

배열과 같이 데이터가 연속적으로 저장되는 데이터 구조 입니다.

맨 끝에 데이터 추가 및 삭제시 유용하지만, 만약 중간에 데이터를 추가하거나 삭제해야 할 시 그 뒤에 있는 데이터들을 앞 당기거나 밀러나야 하는 추가적인 연산이 필요하기 때문에 연산이 느려질 수 있습니다.

 

[ LinkedList ]

ArrayList와 달리 데이터를 연속적으로 저장되는 형태가 아니라, 임의의 공간에 기억시키고 순서에 따라 인접한 데이터끼리 서로 연결되어 있는 구조 입니다.

ArrayList와 달리 중간에 데이터를 추가하거나 삭제 할 시 인접한 데이터의 링크만 수정해주면 되므로 추가적인 연산이 일어나지 않습니다. 단, 특정 데이터를 찾을 때 순차적으로 찾아야 하므로 탐색속도가 느리다는 단점이 있습니다.

 

[ Stack 스택 ]

나중에 들어간 데이터가 먼저 나오는 후입선출 방식의 자료구조 입니다.

 

[ Queue 큐 ]

데이터가 입력되는 순서대로 나오는 선입선출 방식의 자료구조 입니다.

큐는 주로 데이터가 입력된 순서대로 처리해야 할 필요가 있는 상황에 이용합니다.

즉 프로세스 관리나 CPU관리에 쓰입니다.

 

---

<<  비선형구조 >>

[ Tree ]

계층적인 관계를 표현하는 자료구조 이며 Node로 이루어져 있습니다.

 

[ Hash Table ]

key 와 value를 가지는 자료구조 입니다. key를 통해 데이터를 바로 가져올 수 있으며, 이 때문에 속도가 빠르다는 장점을 가지고 있습니다.

 

주로 Hash Function을 이용하여 사용자가 설정한 key를 인덱스로 변환하여 사용하곤 하는데, 이때 같은 인덱스를 반환하게 되면

서로 값이 충돌되는 경우가 발생 할 수 있습니다. 즉, Hash Function을 이용해서 key값을 인덱스로 변환했는데, 그 인덱스로 접근했을 때 이미 다른 값이 그 자리를 차지하는 경우입니다. 이런 경우를 해시충돌이라고 합니다.

이 해시 충돌을 해결하는 방법은 크게 두 가지 방법이 있습니다.

 

첫번째는 개방 주소 방식 입니다.

해시 충돌이 발생하면 다른 해시 버켓을 찾아서 해당 자료를 삽입하는 방식입니다.

즉 충돌이 발생하면, 해당 데이터를 저장할 장소를 찾습니다.

이때 이 장소를 찾는 방식에도 세 가지 방식이 있는데, 선형탐색방식과, 제곱탐색방식, 마지막으로 더블해싱방식이 있습니다.

 

두번째는 분리연결법 입니다.

해시테이블의 셀 마다 연결리스트를 하나씩 저장하도록 하고 충돌이 발생하는 데이터는 그 연결리스트의 다음 노드로 계속 추가하는 방식입니다.

 

[ Graph ]

정점과 간선의 집합을 가지는 구조를 그래프라고 합니다.

이때 정점과 간선의 연결방식에 따라 방향성이 없으면 Undirected Graph

방향성이 있으면 Directed Graph 라고 합니다.

 

DFS 깊이우선탐색	BFS 넓이우선탐색
그래프 상 존재하는 임의의 정점으로 부터 연결되어 있는 한 정점으로 만 나아가면서 탐색하는 기법 입니다. 모든 정점을 방문해야 할 때 사용하며 BFS보다 간단하지만 검색속도가 느립니다.	루트 노드부터 시작해서 인접한 노드들을 탐색하는 기법입니다. 주로 최단거리를 탐색할 때 쓰입니다.