자료구조 종류는 아래와 같다
하나씩 살펴보는 시간을 가지도록 하자
교수님... 왜 더 중요하다고 알려주시지 않으셨나요
** 나무위키와 파이썬 알고리즘 인터뷰를 참고 하였다 **
1. 단순 구조
우리가 흔히 말하는 데이터 타입 또는 자료형이 여기에 해당된다
나는 Python 같이 자료형에 유연한 언어를 사용할 때
가장 적응 안되는게 자료형이었다
C나 C++은 자료형에 엄하다
자료형의 종류는 링크를 통해 보면 좋을 것 같다
자료형 범위나 크기 같은 상세 부분은 다른 게시물로 정리하겠다
2. 선형구조
선형구조는 위에 그림에서 본 것처럼 리스트, 스택, 큐, 덱 등으로 구성된다
그림에는 없지만 배열도 포함됨 ㅇㅇ
리스트는 선형 리스트(Linear List)와 연결 리스트 (Linked List)가 있다
선형 구조는 자료를 구성하는 데이터가
순차적으로 나열되어 있는 형태여서 선형이라고 불린다
(1) 배열 (Array)
배열은 인덱스(index)를 가진 원소들이 순차적으로 나열되어 있는 자료구조이다
인덱스를 가졌다는 것은 위 그림처럼 0, 1, 2... 이렇게
번호가 붙어져 있는 것을 의미한다
그래서 각 원소에 접근하는데 드는 시간은 O(1)이라고 설명된다
시간 복잡도
- 원소 접근 → O(1)
- 원소 찾을 때 드는 시간 → O(1)
- 원소 대입시 위치 찾아야 하니까 → O(1)
- 원소 삭제 시 → O(n)
(삭제 후 배열 길이가 하나 줄어서 다 한 번씩 이동하니까)
** 참고 **
시간 복잡도의 O 표기
O는 점근 표기법이라고 해서 함수의 증가하는 모양을 비교하는 표기 법이다
큰 O-표기법 (Big O 표기법) 또는 란다우 표기법(Landau)으로 부르기도 한다
시간 복잡도에 대해서는 다른 게시물로 다시 정리하겠다
배열은 인덱스를 통해 array[3] 이렇게 원하는 위치에 접근할 수 있다
메모리 주소가 연속되기 때문에, 배열을 크기를 늘리는 건 할 수 없다
정의한 크기만큼 사용 가능하단 얘기 ㅇㅇ
자료구조 malloc으로 메모리 할당받는 걸 싫어해서
배열은 정말 자주 쓰는 듯.
(2) 리스트 (List)
리스트는 어떤 순서를 가지고 원소들이 일렬로 쭈욱 나열한 형태의 자료구조이다
리스트도 각 원소에 번호를 붙일 수도 있고
원소를 찾을 수 있는 연산도 구현 가능하다
(그래서 배열을 리스트에 포함시키기도 한다)
가장 많이 쓰는 종류는 연결 리스트이다
말 그대로 연결이 되어 있는 모양이어서
각 node(그림에서 직육면체 것들)들이 다음 node의 주소를 알고 있고
그 주소를 통해 데이터를 삽입/삭제하는 것이 가능하다
내가 제일 많이 쓰는 경우는 각 node에 기억해야 할 key와 value를 저장하고
(예를 들어 사람 주민번호 같은 key랄까?)
그 key로 해당 value를 찾을 때 쓴다
C++은 iterator 개념이 있지만 C는 그런 게 없어서 직접 구현하다 보니
core가 참 많이 난다 ㅎㅎ
시간 복잡도
- node 검색 → O(1) 또는 O(n)
(바로 찾으면 이득인데 끝까지 다 찾게 되면 n 시간임)
- node 삽입 → O(1)
- node 삭제 → O(1)
* O(1)가 한번 걸리는 속도라는 의미는 아님. 상수를 뜻하는 것일 뿐
(3) 스택 (Stack)
스택은 한 번쯤 들어봤을 LIFO(Last In First Out)를 가지는 자료구조이다
나중에 온 놈이 먼저 나간다~
(큐는 선입선출인 FIFO이다)
스택 모양 자체는 데이터가 쌓여있는 모양이다
리스트에서 노드를 추가/검색/출력/삭제 하듯이, 스택도 입력 연산이 있는데,
추가 개념을 Push, 출력 개념을 Pop 이라고 부른다
맨 위의 데이터 조회 연산은 Peek라고 한다... 피크는 처음 알았다;;
구현할 때 index 관리에 대해서만 잘하면 다른 자료형에 비해
쉽다고 하니, 연결 리스트와 비교한 그림만 보고 넘어가도록 하겠다
시간 복잡도
- Push → O(1)
- Pop → O(1)
- Peek → O(n)
** 참고 **
Stack Overflow (스택 오버플로우)
스택 포인터가 스택의 경계를 넘어설 때 일어나는 현상?으로
(4) 큐 (Queue)
큐는 내가 제일 좋아하는 자료구조다
위에서 스택은 후입선출인 LIFO라고 언급하였다
큐는 그 반대인 선입선출인 FIFO (First In First Out) 개념이다
먼저 온 놈이 먼저 나간다~
(큐 영어 뜻은 표를 사러 일렬로 늘어선 사람들로 이루어진 줄이라고 한다)
스택에서는 Push/Pop/Peek 개념이 있다고 했다
큐는 Put(Insert)/Get(Delete) 연산이 사용된다
또한 큐에서 데이터가 나가고 들어가고 하는 걸
Enqueue/Dequeue 라고 부른다
바로 요렇게..!
먼저 들어온 친구를 Front, 마지막에 들어온 친구를 Back이라고 표현한다
FIFO니까 먼저 들어온 Front가 먼저 Dequeue 된다
시간 복잡도
- Push → O(1)
- Pop → O(1)
- Search → O(n)
큐는 맨 앞에 애가 나가면 앞에 자리가 비어서 정렬을 다시 해줘야 함...
그래서 나온 거 방식이 원형 큐이다
원형 큐
말 그대로 원형으로 된 큐이다
원형 큐에는 Front 와 Back 용어 대신 Front와 Rear라는 용어가 사용된다
Front → 값이 있는 가장 첫 번째 위치 (무조건 0이어서 front가 아님)
Rear (후방) → 값이 있는 가장 마지막 위치
처음 시작 위치는 front와 rear가 같은 값을 갖는다
그리고 그다음에 들어온 친구가 있으면 rear 값을 +1 시킨다
큐는 가장 먼저 들어온 친구가 먼저 나가기 때문에
deQueue가 되면 front에 있는 값이 나간다
그러면 front 값을 +1 시키면 됨ㅋ
이런 식으로 마치 빙빙 돌면서 큐 배열을 사용하기 때문에 원형 큐라고 한다
기본 큐 (선형 큐)를 보완하기 위한 방식이다
(5) 덱 (Deque)
덱은 큐와 다르게 front와 back 둘 다에서 삭제와 삽입이 가능한 자료구조이다
메모리 크기가 가변적이고, 중간중간 삽입/삭제도 쌉파써블
( 앞/뒤 보다 중간 노드 연산은 성능이 안 좋음 )
얘는 그림만 첨부하고 정리를 마치겠다
시간 복잡도
- Push → O(1)
- Pop → O(1)
- Search → O(1)
3. 비선형 구조
비선형 구조는 일렬로 나열하기가 어렵고, 자료의 순서가 불규칙해서
자료를 연결하기 복잡한 구조를 뜻한다
대표적으로 트리와 그래프가 있다
자료구조 공부할 때 여기서부터 공부 안 했던 기억이 난다
이제 알면 되는 거지 ^^7
(1) 트리
트리는 위에 첨부한 비선형 구조의 그림과 같은 모양을 가진다
나무처럼 가지를 뻗은 모양이 연상돼서 트리라고 부르는 듯
나무를 뒤집어 놓은 모양이랄까!?
트리에는 용어 정리가 조금 많이 필요하다
노드(node): 트리를 구성하는 기본이 되는 친구 (다른 자료구조의 그 노드 맞습니다)
루트 노드(root node/root): 뿌리(?). 부모가 없는 최상위 노드임
부모 노드(parent node): 루트에 직접 연결되어 있는 노드
자식 노드(child node): 부모 노드에 붙어 있는 노드
형제 노드(siblings node): 같은 부모 노드를 바라보는 노드들
리프 (leaf) 혹은 단말(terminal) 노드: 잎. 차수가 1인 노드. 제일 끝 노드다
링크(link): 노드를 연결하는 선. Edge 또는 branch라고 부름. 간선
경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
길이(length): 출발 노드에서 도착 노드까지 거치는 노드의 개수
깊이(depth): [루트 노드 - 현재 노드]까지의 거리
레벨(level): 0부터 시작하는 링크의 단계
높이(height): [루트 노드 - 리프 노드] 까지의 거리
차수(degree): 각 노드의 자식의 개수[5]
트리의 차수(degree of tree): 트리의 최대 차수 = max[deg1, deg2, ..., degn]
크기(size): 노드의 전체 개수
너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기
또한 이진트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree) 등의 여러 종류가 있다
정리하려고 보니 종류가 생각보다 다양해서 요것도 따로 정리하는 걸로
(2) 그래프
그래프는 트리와 비슷하게 노드와 엣지로 구성되는데
부모/자식 관계로 계층이 이루어진 게 아니라
노드와 노드들끼리 연결되어 구성되는 자료구조이다
흔히 알고 있는 차트 형식의 그래프도 그래프 맞습니다
다만 컴퓨터가 알아먹을 그래프로 바꾼 것뿐
노드들 사이에는 방향/무방향 경로를 가질 수 있어서
그래프 종류도 방향 그래프와 무방향 그래프가 있다
바로 요렇게...
방향 그래프
간선에 방향성이 존재하는 그래프 (화살표로 표현됨)
A → B를 연결하는 간선은 (A, B)로 표기
무방향 그래프
양방향으로 간선을 통해 갈 수 있는 그래프
A와 B를 연결하는 간선은 (A, B)와 (B, A)로 표기
또한 그래프에는 트리 용어에 이어서 추가된 용어가 있다
정점(vertext): 그래프에서 위치를 나타냄
인접 정점(adjacent vertex): 엣지에 직접 연결된 정점
사이클(cycle): 한 정점에서 시작~다시 도착해서 돌아오는 경로
입력 차수(in-degree): 정점에 들어오는 간선의 수
출력 차수(in-degree): 정점에서 나가는 간선의 수
그리고 그래프에서는 꼭 알아야 할 개념이 두 가지가 있다
A. 인접 행렬 (Adjacency Matrix)
→ Edge 추가 삭제가 빈번할 때 사용하는 게 좋음
그래프는 위 그림처럼 배열로 표현될 수 있다
행렬은 0과 1로 표현할 수 있지 않갔습니까?
그래서 엣지가 존재하는 노드면 배열로 (0, 1) 이런 식으로
쓸 수 있다 이말이다
엣지로 연결되어 있지 않은 (예를 들어 (0, 2))는 행렬에 0으로 표기 ㅇㅇ
배열로 만들어 모든 정보를 알고 있는 건 장점이지만
항상 n^2의 2차원 배열의 크기가 잡히니까 공간 낭비가 있을 수도
전에 CNN 공부했을 때 가중치 그래프 용어가 잠깐 나왔었는데
이제 이해가 가는구나...
시간 복잡도
(N은 노드 개수, E는 Edge의 전체 개수)
- Node 추가 → O(N^2)
- Node 삭제 → O(N^2)
- Edge 추가 → O(1)
- Edge 삭제 → O(1)
특정 셀만 변경하면 상수 시간인데, 노드 추가/삭제하니까
모든 셀 다 채워줘야 해서 오래걸려버림...이크
B. 인접 리스트 (Adjacency List)
→ Node 추가 삭제가 빈번할 때 사용하는 게 좋음
인접 리스트는 말 그대로 리스트로 표현한 거다
각 노드들은 헤더 노드로 표현할 수 있고, 정점의 개수만큼 리스트는 존재한다
존재하는 간선만 관리할 수 있어서 행렬보다는 메모리면에서 효율적임
근데 두 정점을 연결하는 간선 조회나 차수를 구하려면 리스트 탐색을 해야 해서
쪼끔 오래 걸릴 수됴
(일단 구현이 어려움)
시간 복잡도
(N은 노드 개수, E는 Edge의 전체 개수)
- 노드 추가 → O(1)
- 노드 삭제 → O(N+E)
(노드 삭제하면 삭제된 공간을 다시 채워줘야 하니까 이만큼)
- 엣지 추가 → O(1)
- 엣지 삭제 → O(E)
(한 줄로 다 연결이 되어 있으면 다 뒤져야 함)
4. 파일 구조
파일 구조는 컴터 보조기억 장치에 저장되는 파일의 자료구조이다
파일에 저장하는 방식이다
[ 출처 ]
https://namu.wiki/w/%EB%B0%B0%EC%97%B4
https://www.onlybook.co.kr/entry/algorithm-interview
파이썬 알고리즘 인터뷰
파이썬 알고리즘 인터뷰 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트 박상길 지음 | 정진호 일러스트 724쪽 | 38,000원 | 2020년 7월 15일 출간 | 180*235*35 | ISBN 9791189909178 판매처 [교보문고] [Y..
www.onlybook.co.kr
'CS > 개념정리' 카테고리의 다른 글
| Composite Pattern (0) | 2023.03.01 |
|---|
