자료구조 (DataStructure)
- 프로그래밍에서 데이터를 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미
- 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미
<자료구조 형태>
선형구조 : 자료 간 관계가 1 대 1인 구조
(배열, 연결리스트, 스택, 큐, 덱)
비선형구조 : 자료 간 관계가 1 대 다 혹은 다 대 다인 구조
(트리, 그래프)
<알고리즘 & 자료구조 평가>
- 컴퓨터에서 알고리즘과 자료구조의 평가는 시간과 공간 두 자원을 얼마나 소모하는지가 효율성의 중점
- 평균적인 상황에서와 최악의 상황에서 자원 소모량이 기준이 됨
- 일반적으로 시간을 위해 공간이 희생되는 경우가 많음
- 시간복잡도 : 알고리즘의 시간적 자원 소모량
- 공간복잡도 : 알고리즘의 공간적 자원 소모량
<Big-O 표기법>
알고리즘의 복잡도를 나타내는 점근표기법으로 가장 높은 차수의 계수와 나머지 모든 항을 제거하고 표기함.
표기법 덕분에 알고리즘의 대략적인 효율을 파악할 수 있음
배열 (Array)
- 연속적인 메모리상에 동일한 타입의 요소를 일렬로 저장하는 자료구조
- 초기화때 정한 크기가 소멸까지 유지됨 (처음 힙영역에 할당해서 중간 변동없이 소멸까지 유지되는 컨셉으로 만들어짐)
*중간에 크기가 변동되면 힙영역에 저장된 크기 변동이 쉽지 않기 때문에
- 배열의 요소는 인덱스를 사용하여 직접적으로 엑세스 가능
* 배열의 인덱스찾기 : 동일한 크기의 자료형을 사용하다 보니 주소값과 주소값 사이의 길이가 모든 자리가 동일하여 찾을때 주소값(i) + i * 자료형 크기로 정해진다. 배열의 경우 배열 처음([0])부터 시작해서 해당 주소값까지 탐색을 함.
* 배열의 시간복잡도
접근 : O(1) 탐색 : O(N)
선형리스트 (Linear List)
- 배열과 달리 유동적이게 런타임 중 크기를 확장할 수 있는 배열기반의 자료구조
- 배열요소의 갯수를 특정할 수 없는 경우 사용
- 리스트는 얼마나 할당될지 특정할 수 없기에 큰 빈 공간을 미리 만들어 둔다 이걸 capacitor라고 부른다.
* 생성된 capacitor의 크기 보단 초과 할경우 더욱 큰 공간을 새로 만들어 본래 데이터를 새로운곳에 복사하고 새로운 capacitor를 사용하는걸로 크기를 늘린다.
- 배열에서는 Length이 아닌 Count를 사용하는 이유는 List는 길이가 아닌 갯수로 길이를 판단하기 때문임.
- 삽입, 삭제 기능이 추가로 구성되어있지만 삽입, 삭제의 시간적 효율도는 좋지못하다 이유는 배열기반의 자료구조이기 때문임.
* List의 시간복잡도
접근 탐색 삽입 삭제
O(1) O(N) O(N) O(N)
연결리스트 (Linked List)
- 데이터를 포함하는 노드들을 연결식으로 만든 자료구조
*데이터와 다른 부수적인 자료를 포함한게 노드임
- 노드는 데이터와 이전/다음 노드 객체를 참조하고 있음
- 노드가 메모리에 연속적으로 배치되지 않고 이전/다음노드의 위치를 확인
* 연속적으로 저장하지 않아 삽입, 삭제에 시간효율도가 좋은편이지만 index개념을 사용할수가 없다 이유는 index는 자료가 연속적으로 저장된 곳에서 사용이 가능해서이기 때문임, 그래서 연결리스트는 다음 데이터의 참조하는 주소값을 갖고있는 노드를 사용함.
- index를 사용하지 못하기 때문에 접근에 있어서 시간효율도가 좋지못함.
- 연결리스트는 노드의 연결구조에 따라 단반향, 양반향, 환형으로 나뉜다.
*LinkedList의 시간복잡도
접근 탐색 삽입 삭제
O(N) O(N) O(1) O(1)
<리스트와 연결리스트의 차이점>
- index를 사용하거나 못사용하는 이유 : 연속적과 비연속적 저장방식 때문에 등 비교를 하면댐
스택 (Stack)
- 선입후출(FILO), 후입선출(LIFO) 방식의 자료구조
- 가장 최신 입력된 순서대로 처리해야 하는 상황에 이용
큐 (Queue)
- 선입선출(FIFO), 후입후출(LILO) 방식의 자료구조
- 입력된 순서대로 처리해야 하는 상황에 이용
- 큐 배열에서 앞부분 데이터를 출력하면 기본 배열처럼 뒤 전체 데이터가 옮겨야 하기애 보완하고자 전단, 후단이라는 처음과 끝을 표시하는 식으로 데이터가 나가면 배열에 데이터 움직임없이 전단과 후단만 움직이는 것으로 데이터자리가 옮겨지는걸 막는데 배열 크기의 끝에 가면 선단과 후단이 만나기 때문에 이걸 보완하기 위해 원형구조가 나왔고 원형구조에서 전단이 후단을 추월할 경우를 보완하기 위해 후단 바로 뒤에 빈칸을 하나 둔다.
- 구현시 어댑터패턴을 사용하여 구현을 하기도 하지만 사용시 가비지컬랙터가 작동되는 확률이 올라가기 때문에 이론적으로 큐의 구조를 바꾸어 사용하는식으로 구현한다.(선형=>환형)
힙 (Heap)
- 부모 노드가 항상 자식노드보다 우선순위가 높은 속성을 만족하는 트리기반의 자료구조
- 많은 자료 중 우선순위가 가장 높은 요소를 빠르게 가져오기 위해 사용
- 힙상태를 만들때 왼쪽이 오른쪽 보다 우선순위가 높게 설정된다.
- 탐색을 할경우 log(n)의 시간복잡도를 가진다.
- 트리형태로 저장하기보단 배열형태로 저장하는것이 공간복잡도에 있어 효율적이다
* 힙상태의 유지
- 두 자식보다 우선순위가 높은걸 부모로 두는 식을 유지하면서 삽입, 제거에도 그걸 유지한다.
- 새로운 노드를 추가하는 삽입의 경우 : 트리의 맨끝에 추가하고 힙상태를 유지한채로 부모와 자식을 정리하는 과정을 진행하며 우선순위를 정해준다.
- 노드를 제거하는 경우(최상단 노드를 제거) : 맨끝의 노드를 최상단에 자리시키고 삽입의 반대의 작업(하단과정)을 진행해주면서 힙상태를 유지하면서 우선순위를 정리한다.
* 완전이진트리
- 노드기반의 자료구조여도 배열기반에 자료구조에 그대로 넣어도 문제가 없는 구조임.
- index의 개념과 비슷한 자리값을 갖고 있어서 데이터의 자리를 쉽게 유추할수있음.
* 부모와 자식의 자리를 찾는법(k인덱스)
- 왼쪽 자식 노드 : 2k + 1
- 오른쪽 자식 노드 : 2k +2
- 부모 노드 : (k-1) % 2
<비선형구조>
- 트리 : 순환구조가 없음
- 그래프 : 순환구조가 있음
트리 (Tree)
- 계층적인 자료를 나타내는데 자주 사용되는 자료구조
- 부모노드가 0개 이상의 자식노드들을 가질 수 있음
- 한 노드에서 출발하여 다시 자기 자신의 노드로 돌아오는 순환구조를 가질 수 없음
이진탐색트리 (BinarySearchTree)
- 이진속성과 탐색속성을 적용한 트리
- 이진탐색을 통한 탐색영역을 절반으로 줄여가며 탐색 가능(탐색의 효율이 다른 자료구조보단 월등히 높다)
- 이진 : 부모노드는 최대 2개의 자식노드들을 가질 수 있음
- 탐색 : 자신의 노드보다 작은 값들은 왼쪽, 큰 값들은 오른쪽에 위치
- 부모를 기준으로 왼쪽이 작은값, 오른쪽이 큰값의 자식을 가지는 트리구조임
<이진탐색트리의 시간복잡도>
접근 탐색 삽입 삭제
O(logN) O(logN) O(logN) O(logN)
<이진탐색트리의 주의점>
- 이진탐색트리의 노드들이 한쪽 자식으로만 추가되는 불균형 발생 가능
* 정렬된 자료구조를 쓰다보니 불균형 문제는 자주 있어난다.
- 이 경우 탐색영역이 절반으로 줄여지지 않기 때문에 시간복잡도 증가
- 이러한 현상을 막기 위해 자가균형기능을 추가한 트리의 사용이 일반적
- 대표적인 방식으로 Red-Black Tree, AVL Tree 등을 통해 불균형상황을 파악
- 자가균형트리는 회전을 이용하여 불균형이 있는 상황을 해결
<트리순회>
- 트리는 비선형 자료구조로 반복자의 순서에 대해 정의하는데 규칙을 선정해야 함
- 순회의 방식은 크게 전위, 중위, 후위 순회가 있음
- 전위순회 : 노드, 왼쪽, 오른쪽
- 중위순회 : 왼쪽, 노드, 오른쪽 <- 이진탐색트리에서 중위순회시 오름차순으로 데이터를 순회가능
- 후위순회 : 왼쪽, 오른쪽, 노드
해시테이블 (HashTable)
- 키 값을 해시함수로 해싱하여 해시테이블의 특정 위치로 직접 엑세스하도록 만든 방식
- 해시 : 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑
- Dictionary와 비슷한 구조를 가지고 있음
- 박싱, 언박싱
<해시테이블의 시간복잡도>
접근 탐색 삽입 삭제
X O(1) O(1) O(1)
<해시함수의 조건>
- 입력에 대한 해시함수의 결과가 항상 동일한 값이어야 함
<해시함수의 효율>
1. 해시함수의 처리속도가 빠를수록 효율이 좋음
2. 해시함수의 결과가 밀집도가 낮아야 함
3. 해시테이블의 크기가 클수록 빠르지만 메모리가 부담됨
<해시테이블 주의점 - 충돌>
해시함수가 서로 다른 입력 값에 대해 동일한 해시테이블 주소를 반환하는 것
모든 입력 값에 대해 고유한 해시 값을 만드는 것은 불가능하며 충돌은 피할 수 없음
대표적인 충돌 해결방안으로 체이닝과 개방주소법이 있음
<충돌해결방안 - 체이닝>
해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식
단점 : 해시테이블 외 추가적인 저장공간이 필요
<충돌해결방안 - 개방주소법>
- 해시 충돌이 발생하면 다른 빈 공간에 데이터를 삽입하는 방식
- 해시 충돌시 선형탐색, 제곱탐색, 이중해시 등을 통해 다른 빈 공간을 선정
- 장점 : 추가적인 저장공간이 필요하지 않음, 삽입삭제시 오버헤드가 적음
- 단점 : 해시테이블에 자료가 많아질수록 성능저하가 많음
- 해시테이블의 공간 사용률이 높을 경우 성능저하가 발생하므로 재해싱 과정을 진행함
* 재해싱 : 해시테이블의 크기를 늘리고 테이블 내의 모든 데이터를 다시 해싱
'개발관련공부자료' 카테고리의 다른 글
| 알고리즘 (0) | 2023.10.06 |
|---|---|
| 오버헤드(Overhead)에 관하여 (0) | 2023.10.05 |
| 기업의 CS 적성 정리 (0) | 2023.09.25 |
| 객체지향 프로그래밍 (0) | 2023.09.22 |
| 메모리 구조 (0) | 2023.09.22 |