[1] 자료구조

자료구조

대량의 데이터를 효율적으로 관리하는 메커니즘입니다.

자료구조가 필요한 이유는 수많은 데이터들을 추가하고, 읽어오고, 제거해야 할 때 효율적으로 관리를 해야 시간을 줄일 수 있기 때문입니다. 비효율적인 관리를 하는것은 작업을 할 때 연산을 더 많이 하게 만들고, 이것은 컴퓨터 리소스를 잡아먹는 것으로도 볼 수 있을 것입니다. 이런 이유로 효율적으로 자료를 다룰 수 있게 해주는 자료구조를 배워보도록 해겠습니다.

 

자료구조의 종류

대표적인 자료구조들의 종류는 아래와 같습니다.

1. 배열

2. 리스트

3. 스택

4. 큐

5. 트리

 

스택

데이터를 쌓아서 관리하는 방식입니다.

<스택>

데이터를 추가하는 작업을 푸시

데이터를 빼는 작업을 팝

이라고 합니다.

 

중간이나 아래처럼 먼저 들어간 것부터 뺄 수 없습니다.

 

스택 자료구조가 쓰이는 곳은 뒤로가기 버튼, 역순문자열, 실행취소, 후위표기법계산 등등이 있습니다.

막연히 자료구조로서의 스택만 봤을 때 보다 더 와닿는 것 같습니다.

 

큐

먼저 입력한 데이터가 먼저 출력되는 자료구조 입니다.

자료를 넣는 것을 인큐

자료를 빼는 것을 디큐

라고 합니다.

 

나중에 들어온 데이터가 먼저 나갈 수 없습니다.

 

큐는 순서대로 처리되야 하는곳에 쓰입니다.

업무대기열, 프로세스 관리, 고객 대기시간 등등

 

배열과 리스트

배열과 리스트는 공통점과 차이점이 있습니다. 아래의 표로 그 특징을 비교해 보도록 하겠습니다.

	배열	리스트
공통점	순서가 있는 데이터를 관리할 때 사용합니다.
차이점	정해진 위치에 있습니다. 차례대로 빈틈없이 메모리를 차지 합니다.	메모리상에 떨어져 있어도 상관없습니다.(포인터로 연결)
	유효한 데이터 개수를 관리할 때 다른 배열변수를 이용합니다.	다음데이터에 연결된 끈의 여부로 데이터의 끝을 파악합니다.
	배열이름과 인덱스로 즉시 데이터를 조회할 수 있습니다.	1번째 데이터부터 차례대로 포인터를 따라 조회합니다.(비교적 느림)
	데이터 추가에 시간이 오래걸린다.	데이터 추가시 해당 데이터의 포인터만 변경하여 시간이 빠르다.

순서가 있는 데이터를 관리할 때 배열과 리스트 모두 사용할 수 있지만, 장단점이 있어 상황에 따라 더 효율적인 방법을 쓸 수 있습니다.

배열은 참조 속도가 빠르기 때문에 추가, 제거 작업이 많이 없고, 조회 빈도가 많은 구조에 적합하고, 리스트는 조회보다 추가, 제거 작업이 잦은 경우 사용하면 좋습니다.

 

리스트에는 포인터라는 것으로 데이터를 연결하고 있는데요. 포인터는 C를 공부할 때 좀 더 상세히 적도록 하겠습니다.

리스트의 구조를 좀 더 자세히 보면, 데이터와 포인터 2가지 항목을 가지고 있습니다. 포인터는 다음 데이터를 가리키는 역할을 합니다.

리스트의 종류는 단방향리스트와 양방향 리스트로 나뉩니다.

 

단방향 리스트

첫번째 포인터에는  1번째 요소의 위치정보가 저장되어 있습니다. 그리고 마지막 요소의 포인터에는 다음 요소가 없음을 나타내는 종료정보가 들어있습니다.

만약, 요소가 리스트에 들어있지 않으면, 첫번째 포인터에는 종료정보가 저장됩니다.

 

양방향 리스트

양방향 리스트는 앞,뒤를 가리키는 포인터가 있습니다. 위에서도 언급했다시피 리스트의 단점은 참조할 때 배열보다 시간이 더 걸린다는 점인데요. 양방향 리스트는 이 점을 보완하기 위해 구상한 것 입니다.

단방향 리스트와 같이 첫번째 요소의 위치정보를 담고있는 "헤드포인터"가 있고, 마지막 요소의 위치를 가리키는 "테일 포이터"가 하나 더 있습니다. 그리고 다음 요소를 가리키는 포인터와 이전 요소를 가리키는 포인터, 2가지 포인터를 사용합니다.

하지만, 이렇게 장점이 늘어난 동시에 단점도 생기는데... 그것은 포인터를 2번 쓰다보니 사용하는 메모리가 늘어난다는 점과 구현이 좀 더 복잡하다는 것입니다.

 

리스트 참고자료

https://opentutorials.org/module/1335/8940 

 

링 버퍼

배열구조는 끝에 다다르면 그것으로 끝나게 되는데, 마지막 요소 다음이 다시 첫번째 요소를 가리켜 순환구조를 만든 것입니다.

책에서는 배열을 예시로 설명하고 있지만, 찾아보니 큐에서 원형큐로 많이 사용하는 듯 보입니다.

링버퍼 참고자료(링버퍼를 사용하는 이유)

openstory.tistory.com/29

 

이진트리

최대 2개의 데이터로 뻗어 나가는 계층형 가지 형태의 자료구조입니다.

구성요소들을 "노드"라고 합니다. 자신의 아래에 있는 노드를 자식노드, 위에 있는 노드를 부모노드라고 합니다.

가장 처음이 되는 요소를 "루트"라고 하고,  자식노드가 없는 노드를 "리프"라고 합니다.

루트에서 특정한 노드까지 경로의 길이를 "깊이"라고 합니다.

 

이진트리의 쓰임

계층적인 자료를 표현하는데 주로 사용합니다.

예) 파일 폴더 구조, 조직도, 대진표 등등

 

힙
특정한 조건을 만족하는 이진트리를 힙이라고 합니다.

1. 부모 노드의 값은 항상 하위 노드의 값보다 작다. (또는 그 반대)

 

위의 조건에 의해 힙은 리프에 있는 값을 꺼내오면 되기 때문에 최소값(또는 최대값)을 찾는데 효율적이라고 합니다.

 

힙이 쓰이는 곳은 어디일까요?

스팀 장터?

 

힙 참고자료

velog.io/@doontagi/%ED%9E%99-84jxwqtmle

힙

 

해시 테이블

해시테이블은 배열과 리스트의 조합이라고 볼 수 있습니다.

데이터를 저장하기 위해서는 어디에 저장될지 루트배열부터 계산해야 합니다. 이 계산을 하는 것이 "해시함수"이고, 계산을 통해 나온 값이 "해시값"입니다.

 

해시값은 어떤 방식으로 계산할까요?

해시값을 계산하는 방법에는 여러가지 방법이 있습니다. 그 중에는 단순한 숫자 뿐만 아니라 문자열을 해시값으로 바꾸는 방법들도 있었습니다.

참고

mangkyu.tistory.com/102

[자료구조] 해시테이블(HashTable)이란?

 

많은 양의 데이터를 해시테이블로 관리하려고 하면 배열이 겹치게 되는데 이것을 "충돌"이라고 합니다. 이런 현상을 피하기 위해 리스트를 사용합니다. 배열이 같은 데이터가 생기면 리스트로 연결을 함으로써 많은 양의 데이터를 해시테이블로 관리할 수 있습니다.

 

그래프

2개 이상의 항목의 관계를 그림으로 표현한 것 입니다. 각 항목들을 "노드"라고 하고, 항목들의 관계를 나타내는 선을 "간선(edge)"라고 합니다.

그래프의 간선에는 방향성을 부여할 수 있는데, 방향성이 있는 그래프를 "방향있는 그래프", 그렇지 않은 그래프를 "방향없는 그래프"라고 합니다.