올해 초에 본 독학사 컴퓨터공학과 시험 중 한과목인 자료구조에 대해 연습장에 정리했던 내용을 한번 쭉 보고 파이썬자료구조에 대해 공부하려 한다. 시험대비용 공부였기 때문에 실무보다는 시험용에 가깝긴 하지만 그래도 전체적인 기본개념은 같기 때문에 여기에다가 다시 한번 정리해 보려 한다.
자료구조
선형구조 - 데이터를 저장할 때 연속적인 기억공간에 배정하는 자료구조
: 배열, 순서리스트, 연결리스트, 스택, 큐, 데크
비선형구조 - 기억공간 내의 위치와 별개로 독립하여 저장하는 구조
: 트리, 그래프
배열
- 연속된 메모리 블록을 이용
- 순차적 메모리 할당 방식으로 인덱스와 원소의 쌍으로 이루어진 집합
순서리스트
- 노드의 삽입,삭제시 노드의 이동 횟수가 많아진다
- 기억공간의 효율성은 1이다
- 연속되지 않은 기억공간에 저장할 수 없다
희소행렬
- 전체 원소 수에 비하여 극소수의 원소만 0이 아닌 행렬(원소 값이 대부분 0)
- 기억공간의 낭비가 많아지기 때문에 이를 위해서 희소행렬은 연결리스트로 표현하는 게 기억장소가 절약된다
스택, 큐, 데크
스택 : 선형리스트의 한쪽 끝에서만 입출력
큐 : 선형리스트의 한쪽 끝에서 입력되고, 다른 한쪽에서 출력
데크 : 선형리스트의 양 끝에서 입출력
스택
- 가장 나중에 삽입된 원소가 가장 먼저 삭제
- 후입선출(LIFO : Last In First Out)
- 삽입은 push, 삭제는 pop
- 삽입 : top=top+1 -> top pointer 를 증가시켜 공간확보 후 원소삽입
- 삭제 : top pointer를 1 감소시킨다
- top pointer <= 0 이면 스택이 비어있는 상태
- 스택의 응용 분야 : 서브루틴 호출, 수식계산, 인터럽트 처리, 순환호출
큐
- 먼저 삽입된 원소가 먼저 삭제
- 선입선출(FIFO : First In First Out)
- 삽입되는 끝을 rear, 삭제되는 끝을 front 라 함
- 작업스케줄링에 유용
-> 원형 큐
- 선형큐에서 queue-full 신호가 발생하면 큐에서 많은 데이터 이동이 일어나는데 이를 방지하기 위해 이용
- 유용공간이 있는데도 오버플로우가 발생되는 단점 보완을 위해 원형으로 표현
- front = rear -> 큐가 비어있는 상태
데크
- 스택과 큐의 동작을 복합시킨 방식
- 입력제한데크(Scroll) : 어느 한쪽으로만 삽입하고 양쪽으로 삭제할 수 있는 구조
- 출력제한데크(Shelf) : 양쪽으로 삽입하고 삭제는 어느 한쪽으로만 할 수 있는 구조
연결리스트
- 연속된 공간없이 부분적인 공간이 여러개 존재할 때 자료저장을 위해 적절
- 연속적인 공간이 아니라도 링크로 다음 노드를 지정할 수 있음
- 새로운 자료를 추가하거나 제거하는 경우에 다른 자료들의 이동이 없어서 적합
- 데이터필드와 링크필드로 구성. <원소,주소> 쌍의 저장 구조
- 포인터로 연결되어 있어서 포인터를 찾아가는 시간이 필요하여 선형리스트에 비해 접근속도가 느림
이중 연결 리스트
- 앞의 노드를 찾으려면 단순연결리스트는 처음부터 다시 순회해야 하고, 원형연결리스트는 한바퀴를 순회해야 하는 단점을 개선하고자 등장
- 각 노드에는 2개의 링크 필드가 있다. llink - data - rlink
- 데이터를 중심으로 왼쪽 링크 필드는 이전데이터의 주소, 오른쪽 링크 필드는 이후 데이터의 주소를 가지고 있음
- 앞의 노드를 찾으려면 왼쪽 링크 필드의 주소 값을 이용하여 쉽게 찾을 수 있다
원형 연결 리스트
- 마지막 노드와 첫번째 노드가 연결되어 있는 리스트
- 어떤 위치에서도 모든 노드 탐색 가능
- 리스트 헤드가 있음 -> 무한루프에 빠지는 경우 방지
- 단순 연결 리스트보다 데이터 처리에 시간이 적게 소요됨
- 데이터를 순환적으로 탐색 가능
트리
- 비선형구조, 계층적구조, 각 노드사이에 사이클이 형성되지 않음
- 루트노드 : 1개 존재. 가장 상위 레벨.
- 부모노드 : 바로 위의 상위노드 / 자식노드 : 바로 아래의 하위노드
- 형제노드 : 부모가 같은 노드 / 단말노드 : 자식이 없는 노드
- 차수 : 한 노드가 가지고 있는 서브 트리수 * 단말노드 : 차수 0
이진 트리
- 레벨 i에서의 최대 노드수는 2^i (트리의 레벨은 1부터 시작)
- 깊이가 k인 이진트리가 가질 수 있는 최대 노드수는 2^k-1
- 깊이가 k인 포화이진트리는(full binary tree) 깊이가 k이고, 노드수가 2^k-1 인 이진트리이다
- 완전 이진 트리 : 깊이가 k이고 노드수가 n인 이진트리에서 노드의 레벨 순서 번호들의 각 위치가 포화이진트리의 번호 1에서 n까지 모두 일치하는 트리( 배열로 표현했을 때 공백이 없는 트리)
이진트리의 순회
전위 순회 : 루트노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리
중위 순회 : 왼쪽 서브 트리 -> 루트 노드 - > 오른쪽 서브 트리
후위 순회 : 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트 노드
힙
- 여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있도록 구성된 자료구조
- 완전이진트리이다
- 최대히프와 최소히프가 있다
- 최대히프 : 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리. 부모노드의 키값은 자식 노드의 키값보다 항상 크거나 같다. 루트노드는 키값들 중 가장 큰 노드
- 최소히프 : 키값이 가장 작은 노드를 찾기 위한 완전 이진 트리. 부모노드의 키값은 자식 노드의 키값보다 항상 작거나 같다. 루트노드는 키값들 중에 가장 작은 노드
- 삽입 : 배열의 가장 마지막 부분에 위치(트리의 끝부분)시킨 후, 직계 조상과 비교하여 알맞은 위치로 찾아감
- 삭제 : 루트를 제거한 후, 배열의 가장 마지막 부분에 위치한 노드를 루트로 올리고, 직계 자손과 비교하여 알맞은 위치로 찾아감
이진 탐색 트리
- 공백이 가능한 이진 트리
- 서브트리들도 모두 이진 탐색트리로 구성
- 모든 원소는 키를 가지며 어떠한 두 원소도 동일한 키를 가질 수 없다
- 왼쪽 서브 트리의 키는 루트키보다 작다
- 오른쪽 서브 트리의 키는 루트키보다 트다
- 삽입되는 노드는 항상 단말 노드가 된다
개발자꿈나무🌲