옥수수, 기록
[자료구조/알고리즘] Stack, Queue, Tree, Graph 본문
자료구조
자료구조란?
여러 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것
데이터: 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값
데이터 그 자체만으로는 어떤 정보를 가지기 어렵고 분석하고 정리하여 활용해야만 의미를 가질 수 있음(ex 전화번호라는 데이터만 가지고 있을경우 누구의 전화번호인지 알 수 없음)
데이터를 정해진 규칙 없이 저장하거나 하나의 구조로만 정리하고 활용하는 것보다
→ 데이터를 체계적으로 정리하여 두는 것이 데이터활용에 유리
자료구조의 분류
자료 구조의 분류
자료구조의 특징
대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는 데 특화되어 있음
많은 자료구조를 알아두면 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제 해결 가능
Stack
Stack이란?
쌓다, 포개지다 란 뜻을 가지고 있으며 마치 접시를 쌓아 놓은 형태와 비슷한 자료구조
→ 데이터를 순서대로 쌓는 자료구조
구조
골목을 자료구조 Stack, 자동차를 데이터에 비유
ex) 골목에 자동차가 1,2,3,4,5 순서대로 들어가고 자동차1이 막다른 골목을 맞이했을 때 자동차5부터 빠져나와야 하는 구조
- 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근
- 이런 Stack 자료구조의 정책을 LIFO(Last In First Out) or FILO(First In Last Out)이라고 부르기도 함
- Stack에 데이터를 넣는 것 = “PUSH”
- 데이터를 꺼내는 것 = “POP”
특징
1 LIFO(Last In First Out)
먼저 들어간 데이터가 제일 나중에 나오는 후입선출의 구조
예1) 1, 2, 3, 4를 스택에 차례대로 넣습니다.
stack.push(데이터)
---------------------------
1 <- 2 <- 3 <- 4
---------------------------
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.
예2) 스택이 빌 때까지 데이터를 전부 빼냅니다.
stack.pop()
---------------------------
---------------------------
4, 3, 2, 1
제일 마지막에 있는 데이터부터 차례대로 나오게 됩니다.
위의 특성으로 인해 스택 구조는 조회가 필요 X
해당 자료구조를 사용해 데이터를 저장하고 검색하는 프로세스가 매우 빠름
최상위 블록에서 데이터를 저장하고 검색하면 된다는 장점
2 데이터는 하나씩 넣고 뺄 수 있음
데이터가 아무리 많아도 하나씩 데이터를 넣고, 뺌
한꺼번에 여러 개를 넣거나 뺄 수 X
3 하나의 입출력 방향
Stack 자료구조는 데이터의 입출력 방향이 같음
입출력 방향이 여러 개라면 Stack 자료구조
4 저장되는 데이터는 유한하고 정적
ex. Stack 자료구조를 사용한 콜 스택(Call Stack)을 예시
콜 스택 내부에 함수의 실행 데이터는 스택의 프레임으로 저장(각 프레임은 해당 기능에 필요한 데이터가 저장되는 공간 블록)
함수가 새로이 변수를 선언할 때마다 스택의 최상위 블록으로 PUSH
→ 함수가 종료될 때 마다 최상위 블록이 지워지므로(후입선출) 해당 함수에 의해 스택에 들어간 모든 변수 삭제 → 저장된 데이터가 정적 특성을 가져야만 컴파일 시간이 결정됨
스택에 저장되는 일반적인 데이터는 로컬 변수(value type or 프리미티브, 프리미티브 상수), 포인터 및 함수 프레임
5 스택의 크기는 제한되어 있음
힙(heap)에 비해 스택의 크기가 제한되어 있음 → 스택 오버플로(Stack Overflow)같은 에러가 자주 발생
대부분의 언어는 스택에 저장할 수 있는 값의 크기가 제한되어 있음
Stack의 실사용 예제
대표적으로 브라우저의 뒤로 가기, 앞으로 가기 기능구현에 자료구조 Stack 활용
1 새로운 페이지에 접속 → 현재 페이지를 Prev Stack에 보관
2 뒤로 가기 버튼 Click → 현재 페이지 Next Stack에 보관 → Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옴
3 앞으로 가기 버튼 Click → Next Stack의 가장 마지막으로 보관된 페이지 가져옴
4 마지막으로 현재 페이지를 Prev Stack에 보관
빈통에 1 push → TOP은 1
stack.push(2) → TOP은 2
stack.push(3) → TOP은 3
stack.push(4) → TOP은 4
stack.pop() → TOP은 3
stack.pop() → TOP은 2
stack.pop() → TOP은 1
stack.pop() → TOP값이 -1(초기값)출력
프링글스통 갖고있음
stack.push(1)
stack.push(2)
stack.push(3)
stack.pop() > 3
stack.push(4)
stack.push(5)
stack.pop() > 5
stack.pop() > 4
stack.pop() > 2
stack.pop() > 1
출력순서 3, 5, 4, 2, 1
프링글스통 갖고있음
stack.push(1)
stack.push(2)
stack.push(3)
// 현 시점 입력된 스택구조
3
2
1
//
stack.pop() > 3
stack.push(4)
stack.push(5)
stack.pop() > 5
stack.pop() > 4
stack.pop() > 2
stack.pop() > 1
출력순서 3, 5, 4, 2, 1
Stack과 Array의 차이
Array는 배열들에 대한 인덱스를 다 가지고 있지만 Stack은 TOP 인덱스밖에 없음
Queue
Queue?
줄을 서서 기다리다, 대기행렬이라는 뜻을 가지고 있음
ex) 톨게이트를 차례대로 통과하는 자동차를 생각하면 이해가 빠름
돌게이트는 Queue 자료구조, 자동차는 데이터
구조
Stack과 반대되는 개념
통이 수평으로 누워져 있는 형태
데이터를 넣고 빼는 구멍이 양쪽 두 군데
데이터를 넣을때 → 뒷 쪽
데이터를 뺄 때 → 앞 쪽
앞쪽에 있는(가장 처음에 넣은) 데이터부터 뺄 수 있는 선입선출(FIFO) 형 or LILO(Last In Last Out)
“enqueue” : Queue 데이터를 넣는 것
“dequeue” : Queue 데이터를 꺼내는 것
특징
1 FIFO(First In First Out)
먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조
예1) 1, 2, 3, 4를 큐에 차례대로 넣습니다.
queue.enqueue(데이터)
출력 방향 <---------------------------< 입력 방향
1 <- 2 <- 3 <- 4
<---------------------------<
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.
예2) 큐가 빌 때까지 데이터를 전부 빼냅니다.
queue.dequeue(데이터)
출력 방향 <---------------------------< 입력 방향
<---------------------------<
1, 2, 3, 4
제일 첫 번째 있는 데이터부터 차례대로 나오게 됩니다.
2 데이터는 하나씩 넣고 뺄 수 있음
데이터가 아무리 많아도 하나씩 데이터를 넣고 뺄 수 있음
한꺼번에 여러개 X
3 두 개의 입출력 방향
Stack과 다르게 데이터의 입력 출력 방향이 다름
입출력 방향이 같으면 Queue 자료구조 X
Queue의 실사용 예제
컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄할 때
1 문서를 작성하고 출력버튼 클릭 →해당 문서는 인쇄 작업(임시 기억 장치) Queue에 들어감
2 프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄
컴퓨터(출력 버튼) → (임시 기억 장치의) Queue에 하나씩 들어옴 →Queue에 들어온 문서를 순서대로 인쇄
버퍼(Buffer)
컴퓨터 장치들 사이에서 데이터를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용하는데 이것을 통틀어 버퍼라고 함
대부분의 컴퓨터 장치에서 이벤트가 불규칙적으로 발생하지만 CPU와 같이, 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 가짐
그리고 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼를 사용
컴퓨터와 프린터 사이의 데이터 통신
- 일반적으로 프린터는 속도가 느림
- CPU는 프린터와 비교, 데이터를 처리하는 속도가 빠름
- 따라서 CPU는 빠른 속도로 인쇄에 필요한 데이터를 만듦 →인쇄 작업 Queue에 저장하고 다른 작업 수행
- 프린터는 인쇄 작업 Queue에서 데이터를 받아 일정한 속도로 인쇄
유튜브와 같은 동영상 스트리밍 앱 → 다운로드 된 데이터가 영상을 재생하기에 충분하지 않은 경우가 있음 →Queue에 모아 두었다가 동영상을 재생하기에 충분한 양의 데이터가 모였을 때 동영상을 재생
queue.enqueue(1)
//휴지심 내부 상태
-----------------
1
-----------------
queue.enqueue(2)
-----------------
1 2
-----------------
queue.enqueue(3)
-----------------
1 2 3
-----------------
queue.enqueue(4)
-----------------
1 2 3 4
-----------------
queue.dequeue()
-----------------
2 3 4
-----------------
queue.dequeue()
-----------------
3 4
-----------------
queue.dequeue()
-----------------
4
-----------------
queue.dequeue()
-----------------
-----------------
출력된 순서
1, 2, 3, 4
inqueue(1)
inqueue(2)
inqueue(3)
---------
1 2 3
---------
dequeue() > 1
---------
2 3
---------
inqueue(4)
inqueue(5)
---------
2 3 4 5
---------
dequeue() -> 2
---------
3 4 5
---------
dequeue() -> 3
dequeue() -> 4
dequeue() -> 5
dequeue() >> 큐에 아무것도 남아있지 않을때 코드를 작성해줘야한다.
Tree
Tree?
이름 그대로 나무의 형태를 가지고 있음 → 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습
그래프의 여러 구조 중 단방향 그래프의 한 구조
하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 트리 구조라 부름
데이터가 바로 아래에 있는 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결된 계층적 자료구조
데이터를 순차적으로 나열시킨 선형 구조 X →하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조
트리 구조는 계층적으로 표현이 되고 아래로만 뻗어나감 → 사이클이 없음 → 하나의 연결그래프(Connected Graph)
🚨사이클: 시작노드에서 출발해 다른 노드를 거쳐 시작노드로 돌아옴 →→ 사이클이 존재한다!
구조와 특징
루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결
노드(Node): 각 데이터
두 개의 노드가 상하 계층으로 연결되면 부모-자식 관계를 가짐
위 그림에서는 A= B,C의 부모 노드, B,C = A의 자식노드
자식이 없는 노드는 나무의 잎과 같다고 해 리프 노드라고 부름
깊이(depth)
트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있음
루트 노드는 깊이 0
레벨(Level)
같은 깊이를 가지고 있는 노드를 묶어 레벨로 표현 가능
깊이가 0인 루트 A의 레벨은 1
같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 함
높이(Height)
리프 노드를 기준으로 루트까지의 높이를 표현할 수 있음
리프 노드와 직간접적으로 연결된 노드의 높이를 표현, 부모 노드의 높이 = 자식 노드의 가장 높은 높이값 + 1
트리 구조의 높이를 표현할 때 리프 노드의 높이를 0으로 놓음
위 그림 기준 H, I, J, E, F의 높이 0 (E,F도 리프 노드이므로)
서브 트리(Sub tree)
트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에 트리 구조를 갖춘 작은 트리
DHI, BDE, CFGJ도 서브트리
용어정리
- 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
- 루트(Root) : 트리 구조의 시작점이 되는 노드
- 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
- 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
- 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드
실사용 예제
컴퓨터의 디렉토리 구조(파일탐색기)
프로그램이나 파일을 찾을 때 폴더에서 폴더로 진입하고 그 안의 폴더에서 또 폴더로 진입해 프로그램을 찾음
모든 폴더는 루트 폴더(/)에서 시작돼 가지를 뻗어나가는 모양새를 띰
추가예제 : 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등
이진 트리
자식 노드가 최대 두 개인 노드들로 구성된 트리, 두 개의 자식 노드는 왼쪽자식노드, 오른쪽자식노드로 나뉨
이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉨
특징
정 이진 트리(Full binary tree)
각 노드가 0개 혹은 2개의 자식 노드를 가짐
포화 이진 트리(Perfect binary tree)
정 이진 트리이면서 완전 이진 트리인 경우
모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리
완전 이진 트리(Complete binary tree)
마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 함
이진 탐색 트리(Binary Search Tree)
이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 이진트리
이진 탐색의 효율적인 탐색 능력유지 + 빈번한 자료 입력과 삭제 가능
특징
각 노드에 중복되지 않는 키(key)가 있음
루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있음
루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있음
좌우 서브트리도 모두 이진 탐색 트리여야 함
이진 탐색 트리는 균형 잡힌 트리가 아닐 때 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있음
균형이 잡히지 않은 트리는 탐색하는데 시간 ↗ → 해결해야 할 문제임
→ 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘 추가 가능
특징 2
기존 이진 트리보다 탐색이 빠름 → 이진 탐색 트리의 연산은 트리의 높이가 h(height)라면 o(h)의 복잡도를 가짐
탐색과정
1 루트 노드의 키와 찾고자 하는 값을 비교 → 찾고자 하는 값이라면 탐색 종료
2 if (찾고자 하는 값 < 루트 노드의 키) 왼쪽 서브 트리 탐색
3 if (찾고자 하는 값 > 루트 노드의 키) 오른쪽 서브 트리 탐색
찾고자 하는 값을 찾을 때까지 위의 과정반복, 값을 찾지 못하면 그대로 연산 종료
→ 탐색 과정을 거치면 최대 트리의 높이만큼 탐색을 진행
위와 같은 트리에서 5라는 값을 찾고자 하면 처음에는 루트 노드(10)과 비교
찾으려고 하는 5는 루트 노드보다 작기때문에 왼쪽 서브 트리로 탐색 시작
탐색 직후 마주친 노드가 7이므로 5보다 크니 또 왼쪽 서브 트리로 탐색
트리 조회 방법
트리 순회 = 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에 모든 노드를 순회하는 방법에 크게 3가지가 있음
트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽
전위 순회(preorder traverse)
전위 순회에서 가장 먼저 방문하는 노드는 루트
루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색
→ 부모 노드가 제일 먼저 방문되는 순회 방식
주로 부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용
중위 순회 (inorder traverse)
루트를 가운데에 두고 순회
제일 왼쪽 끝에 있는 노드부터 순회하기 시작, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동해 마저 탐색
부모 노드가 서브 트리의 방문 중간에 방문되는 순회방식
이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰임
후위 순회 (postorder traverse)
루트를 가장 마지막에 순회
제일 왼쪽 끝에 있는 노드부터 순회하기 시작, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤 제일 마지막에 루트를 방문
트리를 삭제할 때 사용 → 자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문
Graph
Graph?
여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
통상적으로는
위와 같은 그래프를 떠올리기 마련이지만 컴퓨터 공학에서의 자료구조 그래프는 다른 모습임
구조
직접적인 관계가 있는 경우 두 점 사이를 이어주는 선 ⭕️
간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어짐
하나의 점을 그래프에서는 정점(vertex), 하나의 선은 간선(edge)이라고 표현
표현 방식
인접 행렬
두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다라고 이야기 함
인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타냄
A라는 정점과 B라는 정점이 이어져 있음 → 1(true), 이어져 있지 않음 → 0(false)로 표시한 일종의 표
만약 가중치 그래프라면 1대신 관계에서 의미 있는 값을 저장
인접 행렬은 언제사용?
- 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지 없는지 확인하기 용이
- 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용
인접 리스트
각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
각 정점마다 하나의 리스트를 가지고 있으며 이 리스트는 자신과 인접한 다른 정점을 담고 있음
인접 리스트 예시
A→C→Null
B→A→C→Null
C→A→Null
B는 A와 C로 이어지는 간선이 두 개가 있는데 왜 A가 C보다 먼저인가?
순서는 중요 X
그래프, 트리, 스택, 큐 등 모든 자료구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/ 삭제 가능
그래프를 인접 리스트로 구현할 때 정점별로 살펴봐야 할 우선 순위를 고려해 구현할 수 있음
이때 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있는데 우선 순위가 없다면 연결된 정점들을 단순하게 나열한 리스트가 됨
인접 리스트는 언제 사용?
- 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용
- 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지
알아둬야 할 Graph 용어들
- 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
- 간선 (edge): 정점 간의 관계를 나타냄(정점을 이어주는 선)
- 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻함
- 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프를 뜻함
- 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻함
- 무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있음
- 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄
- 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점
- 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현. 다른 정점을 거치지 않는다는 것이 특징
- 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프
Graph의 실사용 예제
포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 네비게이션 등에서 사용하는 자료구조
BFS(Breadth-First Search)
너비를 우선적으로 탐색하는 방법
주로 두 정점 사이의 최단 경로를 찾을 때 사용
만약 경로를 하나씩 전부 방문한다면 최악의 경우 모든 경로를 다 살펴보아야 함
DFS(Depth-First Search)
깊이를 우선적으로 탐색하는 방법
한 정점에서 시작해 다음 경로로 넘어가기 전 해당 경로를 완벽하게 탐색할 때 사용
BFS보다 탐색시간은 조금 오래 걸려도 모든 노드를 완전히 탐색할 수 있음