우선 자료구조가 뭔데..?
자료구조란 여러데이터들의 묶음을 저장하고 사용하는 방법을 정의한 것이다.
여기서 의미하는 데이터란 문자, 소리, 숫자, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다! 하지만 데이터 자체로만으로 어떠한 정보를 가지기는 힘들다. 소리라는 데이터만 알고 있다면 이게 강아지의 소리인지 사람의 소리인지 모르니까😱
이처럼 데이터는 분석하고 정리하며 활용해야지만 의미를 가질 수 있다 !!!
이렇게 많은 데이터를 규칙없이 저장하는것 보다는 체계적으로 정리하여 저장해두는 것이 훨씬 유리하기 때문에 우리의 천재 선배 개발자들께서 여러 방법을 연구해두셨다..😺
그 방법을 모두 모아 자료구조라는 이름을 붙였는데 코딩테스트에 가장 자주 나오는 네가지를 알아보자!
Stack
stack은 쌓다 라는 뜻을 가지고 있는데 접시쌓기형태를 생각하면 된다.
말 그대로 data를 순서대로 쌓는 자료구조인데 일상생활에서도 예시를 찾아볼 수 있다.
이런 막다른 길에 자동차 여러대가 동시에 들어가게 된다면 어떻게 될까?
이 골목의 끝은 막혀 있기때문에 마지막으로 들어온 자동차가 먼저 후진하여 나와야한다!
여기서 골목을 stack, 자동차는 data로 비유할 수 있다.
그렇다면 컴퓨터에서 stack은 어떻게 사용될까?
대표적으로 우리가 자주 사용하는 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 자료구조 Stack이 활용된다
브라우저에서 자료구조 Stack이 사용될 때에는 다음과 같은 순서를 거치게된다👻
1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관합니다.
2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옵니다.
3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는, Next Stack의 가장 마지막으로 보관된 페이지를 가져옵니다.
4. 마지막으로 현재 페이지를 Prev Stack에 보관합니다.
이렇게 자료구조 Stack을 이용하면, 뒤로 가기와 앞으로 가기 버튼을 구현할 수 있다~
Queue
queue는 대기형렬이라는 의미이다.
쉽게 생각해서 stack과는 반대되는 개념으로 먼저들어간 data가 먼저나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징으로 가지고 있다!
톨게이트를 생각하면 편하다!
톨게이트에서는 가장 먼저 진입한 자동차가 가장 먼저 톨게이트를 통과한다.
다시 말해, 가장 나중에 진입한 자동차는 먼저 도착한 자동차가 모두 빠져나가기 전까지는 톨게이트를 빠져나갈 수 없다😴
다른 예로 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄하려면 어떻게 해야 할까?
우리가 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 (임시 기억 장치의) Queue에 들어갑니다.
프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄합니다.
컴퓨터(출력 버튼) - (임시 기억 장치의) Queue에 하나씩 들어옴 - Queue에 들어온 문서를 순서대로 인쇄
만약 Queue에 들어온 순서대로 출력하지 않는다면, 인쇄 결과물이 뒤죽박죽일 거다👾
Graph
그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.
직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다. 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어집니다. 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 한다.
Tree
자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있다. 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있습니다. 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부른다.
tree예시!
하나의 폴더 안에 여러 개의 폴더가 있고, 또 그 여러 개의 폴더 안에 또 다른 폴더나 파일이 있습니다. 위 그림처럼, 제일 첫 번째 폴더에서 출발하여 도착하려는 폴더로 가는 경로는 유일하다. 사용자들이 사용하기 편하게 사용하기 위한 파일 시스템 등에서는 트리 구조를 이용해 만들어져 있다😀😀😀
