[알고리즘] 자료구조란 ?

자료구조

; 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장

- 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령을 의미

- 신중히 선택한 자료ㅏ구조는 보다 효율적인 알고리즘을 사용할 수 있게 함

 

 

배열

; 가장 일반적인 구조. 메모리 상에 같은 타입의 자료를 연속적으로 저장

#include <iostream>
using namespace std;

int main(){
	int array={1,2,3};
    cout<<array[1];
	return 0;
}

 

튜플

; 둘 이상의 자료형을 묶음으로 다루는 구조

ex) c++ 에서

#include <iostream>
#include <tuple>

using namespace std;

int main()
{
    tuple <int, int, int , int> t1 = make_tuple(1,2,3,4);
    cout << get<0>(t1) << endl;  // 1
}

 

연결 리스트

; 노드(자료와 다음 노드를 가리키는 참조값으로 구성)로 구성된 리스트

- 원형 연결 리스트 ; 마지막 노드가 처음 노드를 가리키는 연결 리스트

- 이중 연결 리스트 ; 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된 연결 리스트

- 환형 이중 연결 리스트 ; 원형 연결 리스트 + 이중 연결 리스트

 

해시 테이블

; 개시가 해시값에 따라 인덱싱 됨

 

선형 구조

스택(Stack)

; LIFO(Last In First Out)구조 ; 가장 마지막에 넣은 자료가 가장 먼저 삭제되는 구조

- 함수 호출 시 복귀 주소 저장할 때 사용

- 수식의 계산할 때 사용(일반적으로 후위 표기법에 사용)

 

큐(Queue)

; FIFO(First In First Out)구조  ; 가장 먼저 넣은 자료가 가장 먼저 나오는 구조

- head, tail 두개의 변수 사용 => 데이터 추가 시 tail 변수값 +1, 데이터 삭제 시 head 변수값 +1

- 시스템에서 프로세스의 순차처리와 보조기억장치를 이용한 spool처리 등에 사용

# spool 처리 ; CPU -> I/O로 보낼 때 임시로 보조기억장치에 저장하는 과정

 

선형 큐

- front는 삭제되는 데이터, rear는 추가되는 데이터를 가리킴

- 데이터 추가

char queue[],item;
{
	int front,rear;
	if(rear==n-1) overflow;
    else{
        rear++;
        queue[rear]=items;
        }
    }
}

- 데이터 삭제

char queue[],item;
{
	int front,rear;
    if(front==rear) underflow;
    else{
    	front++;
        item=queue[front];
        return item;
    }
}

 

무빙 큐

; 데이터 삭제 시 데이터를 한칸 왼쪽으로 이동시킴 -> 많은 시간적 손실 초래

 

원형 큐

; 배열의 끝 인덱스에서 배열의 시작 인덱스로 연결되는 큐

- 선형 큐의, tail이 배열의 마지막 인덱스를 가리킬 때 앞에서 발생한 배열의 빈 공간을 활용할 수 없는 문제점을 해결

- 데이터 추가

{
    if(tag==1) overflow;
    else{
        rear=(rear+1)%n;		// n은 배열의 크기
        if(rear==front)tag=1;	// rear+1을 했는데, front와 곂쳤다 = 배열이 꽉 찼다는 의미
        else
            queue[rear]=item;	// 배열이 꽉차지 않았다면, item을 queue에 삽입
        }
    }
}

- 데이터 삭제

{
	char item;
    if(rear==front && tag==0) underflow;
    else{
    	front=(front+1)%n;
        if(rear==front) tag=0;
        else item=queue[front];
	}
    return item;
}

 

덱(Deque)

; 양쪽에서 넣기와 빼기를 할 수 있는 일반적인 선형 구조

 

비선형 구조

그래프 ; 꼭짓점과 꼭짓점을 잇는 변으로 구성

- 방향 그래프

- 무방향 그래프

 

트리

[트리 알고리즘]

https://peter-coding.tistory.com/9?category=1279953 

트리(Tree)

- 이진 트리 ; 자식이 최대 2개인 트리

- 힙 ; 완전 이진 트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조