Algorithms

[Algorithms] 자료구조 - 선형구조 / 비선형구조

devran 2023. 1. 27. 15:42

정리에 앞서 도움 받은 글 및 이미지 출처

https://go-coding.tistory.com/4

이분의 글을 차례로 보면 전반적인 알고리즘 개념을 잡는데에 큰 도움이 된다.

트리구조, 그래프 관련 + 기타 더 딥한 알고리즘 정보

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

이 글도 도움이 많이 되었음!

아무리 생각해도 ,, 조금 더 기초적인 부분을 짚고 넘어가야 겠다는 생각이 들었다.

비참하지만 지금 깨달아서 다행이다. 전공수업을 들었음에도, 코테는,,여윽시 기초가 정말 중요하다고 느꼈다 🤖

✅ 자료구조

현실세계에 존재하는 데이터를 효율적으로 저장할 수 있는 구조화 표현의 개념.

다음과 같은 구조로 이루어져 있음.

단순 구조

프로그래밍시 변수도 크기가 커지면 여러공간에 변수를 나눠서 저장하게 된다.

변수의 데이터 타입에 따라 구조도 바뀐다.

선형 구조

자료가 저장 관계가 1:1인 경우이다. 쉽게 말해 자료가 한줄로 똑바로 서있다고 생각!

비선형 구조

자료의 저장 관계가 1:N인 경우이다. 복잡하지만 효율적인 자료구조

파일 구조

서로 관련된 필드들로 구성된 레코드의 집합인 파일에 대한 자료구조

이론은 다 쉬운데, 진짜 도움 되는 공부를 해보자.

선형구조와 비선형구조에 사용되는 알고리즘을 직접 공부하고, 구현해보자.

✅ 선형구조

선형구조에서 가장많이 쓰이는 용어는 FIFO 와 LIFO

FIFO(First In First Out) : 선입선출, 가장 먼저들어온 데이터가 가장 먼저 출력.

LIFO(Last In First Out) : 후입선출, 가장 나중에 들어온 데이터가 가장 먼저 출력.

⚠️ 스택(Stack)

스택은 **Push()와 Pop()**기능이 있다.

Push()를 하면, 스택안에 자료 순차적으로 쌓이고, 가장 최근에 들어온 자료는 Top이 된다.

Pop()을 하면, 가장 최근에 들어온 자료가 방출된다.

Top인 자료가 방출되고 그 밑에 있는 자료가 Top이 된다.

즉 선입선출, FIFO! 구조이다.

ex) 괄호 검사, 역순 문자열 만들기, 후위 표기법으로 변환 등이 있다.

⚠️ 큐(Queue)

큐도 **Push()와 Pop()**기능이 있다.

Push는 삽입, Pop은 삭제 기능이다.

큐는 한쪽 끝(rear) 에서는 삽입만 되고,

다른 한쪽 끝(front) 에서는 삭제만 되는 유한 순서 리스트이다!

보통 데이터가 입력된 순서대로 처리해야 하는 경우에 많이 사용된다. ex)은행 번호표, 콜센터, BFS 등

먼저 삽입된 Item이 먼저 삭제가 이루어지는 선입선출, FIFO 구조이다.

⚠️ 덱(Deque)

덱은 양쪽 모두에서 Push와 Pop기능이 가능한 구조다.

두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다.

큐와 스택을 합친 형태라고 볼 수 있다.

→ 앞으로 넣기, 앞으로 빼기, 뒤로 넣기, 뒤로빼기가 모두 가능함

✅ 비선형 구조

비선형 자료구조는 하나의 자료 뒤에 여러개의 자료가 존재할 수 있다.

1:N의 관계를 가지고, 계층적 구조를 나타내기에 적당하다.

⚠️ 트리(Tree) 구조

트리(Tree)구조는 노드(Node, 동그란거)와 간선(Edge, 화살표)을 이용하여 사이클을 이루지 않도록 구성한 그래프 형태다. 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이고, 부모와 자식간의 계층 구조가 명확하다.