S2U2 [자료구조/알고리즘] 자료구조 회고

[Stack]

🛒 Stack은 입출력이 한 쪽에서 이루어지는 자료구조이다. FILO(First In Last Out) = LIFO 방식이다. 데이터를 넣는 것은 push, 꺼내는 것은 pop이다. 대표적인 사용 예는 브라우저 <-뒤로가기 와 앞으로가기-> 구현이다. 버튼을 누르면 현재 페이지 기준 바로 직전에 보았던 페이지로 이동한다.

가볍게 자료구조 강의를 들으면서 구현해본 적이 있던 터라 이해하기는 수월했다. 다만 그래프 탐색에서 활용하거나 하는 데에 쉽게 활용을 못 한다는 점...?? 많이 쳐보고 연습해본다면 해결될 문제일 거라 생각한다! 그나저나 옛날에 stack it up 많이 들었는데ㅎㅎㅋㅋ

---

[Queue]

🛒 Queue는 입출력이 양쪽에서 이루어진다. 하지만 입출력 방향은 한 쪽으로 고정되어 있어, 가장 처음 들어간 데이터가 가장 처음으로 꺼내진다. 이는 FIFO(First In First Out) = LILO 방식이다. 데이터를 넣는 것은 enqueue, 꺼내는 것은 dequeue이다. 대표적인 예는 프린터 대기열이다. 가장 먼저 인쇄요청을 한 페이지가 가장 먼저 출력된다.

큐는 스택과 유사해서 여기까진 괜찮았다... 아 참 이러한 자료구조들은 추상자료형이기에 기존 컬렉션을 이용해 구현해주어야 한다. 난 처음에 Stack처럼 Queue라는 클래스가 존재하는 줄 알았다😓.. 큐는 LinkedList를 사용하면 쉽게 구현 가능하다. 그런데, 찾아보니 이 경우에 dequeue 작업을 하면 기존 데이터들을 다시 앞으로 당겨오는 작업을 해야하기 때문에(O(n)) 데이터가 커지면 효율이 좋지 못 했다. 추가 학습에 있던 원형 큐를 살펴보았다. 원형 버퍼를 구현하면 데이터를 매번 이동해주지 않아도 됐다! 기존 리스트를 동그랗게 말아주는 느낌으로, 커서를 두 개 놓아 그것들로 연산하면 보다 간단하다. 데이터 대신 커서를 옮겨가며 작업을 수행하는 것이다. 그런데 이러면 생성할 때 size를 배열마냥 미리 정해놔야 하는 것 아닐까? 아직 직접 손대보진 않아서 잘 모르겠다. 원래 원형 큐도 꼭 살펴봐야겠다 라고 쓰고 넘어가려 했는데 그러면 분명 안 할 것 같아서 당장 찾아봤다ㅎㅎ; 양쪽에서 양방향 입출력이 가능한 Deque도 회고를 마친 뒤 구조와 구현을 익히는 정도로 찾아보아야겠다! (이건 진짜)

---

[Tree]

🛒 Tree는 하나의 루트 노드로부터 쭉쭉 하위 노드 가지를 쳐나가는 비선형 구조이다. 대표적으로 컴퓨터 디렉토리 구조를 생각하면 쉽다. C드라이브에는 ProgramFiles, Users... 여러 하위 디렉토리가 있고 그 디렉토리들은 각각 또 다른 하위 디렉토리들을 갖는다.
트리를 이루는 각 데이터 요소는 [노드(Node)]이다. 가장 꼭짓점 노드는 [루트(Root)]이다. 상대적인 관점으로 위쪽에 있는 노드는 [부모(Parent) 노드], 아래는 [자식(Child) 노드]가 된다. 자식이 없는 노드는 [리프(Leaf)노드]라고 한다. (새로 안 사실) 리프 노드가 항상 마지막 레벨인 것은 아니다!
노드의 [깊이(Depth)]는 루트를 0으로 하여 아래로 가지를 칠 수록 +1 된다. 이렇게 같은 깊이를 가진 노드들은 [레벨(Level)]도 같은데, 다만 기준이 되는 루트의 레벨은 깊이처럼 0이 아닌, 1이다. 레벨이 같은 노드들은 [형제 관계]이다.
[높이(Height)]는 깊이와 반대된다. 기준이 되는 노드는 최하위 노드이고, 높이 0으로 시작되어 루트쪽으로 올라갈수록 +1된다.

선형 구조를 무사히 마치고, 비선형 구조가 되는 순간 뇌정지가 온다. 매번 공부할 때마다 그랬던 것 같다. 뭐든 순차적으로 관리하면서 효율적이라면 참 좋을텐데.. 무튼 Node를 만들고 저장 값(data), 왼쪽 Node, 오른쪽 Node를 가지게 구현하면 된다는 것까진 이해했다. 기본적인 이진 트리의 구조이다. 다중 노드 트리를 구현하는 것은 아직 손대보지 않았다..😉
항상 느끼는 거지만 트리 객체 구현. 그래 알겠다... 순회 구현. 할 수 있다. 이걸 써먹어보라 하면 어렵다ㅋㅋㅠ 아직 그 단계에 있는듯 하다.

---

[Graph]

🛒 그래프는 [정점(vertex)]과 [간선(edge)]로 이루어진 비선형 구조이다. 간선의 종류로는 단방향/양방향 간선이 있다.
그래프를 표현하는 방식은 크게 두 가지로, 인접 행렬 또는 인접 리스트이다.
인접 행렬은 정점 간의 연결 상태를 2차원 배열로 나타낸다. 정점이 연결되어있으면 1(가중치 그래프라면 의미있는 값), 연결되어있지 않다면 0으로 표현한다. 큰 표의 모습을 하기 때문에 관계를 확인하기에 용이하다. 좌표값만 안다면 쉽게 파악할 수 있다. 가장 빠른 경로를 찾는 데에 주로 사용된다.
인접 리스트는 정점 간의 연결 상태를 리스트 형태로 표현한다. 인접 행렬과 가장 큰 차이점은 오직 연결된 관계([인접,adjacency])만 담고있다는 것이다. 그렇기 때문에 인접 행렬보다 메모리를 효율적으로 사용할 수 있다.
한 정점에서 진출한 간선이 다른 정점을 거치지 않고 곧바로 자신에게 돌아온다면 [자기 루프(self loop)]를 가졌다라고, 여러 정점을 거쳐 다시 자신에게 돌아온다면 [사이클(cycle)]이 존재한다고 표현한다.
그래프는 검색 엔진, 내비게이션 등에서 활용될 수 있다.

아직은 인접행렬을 통해 그래프를 구현하는 게 더 익숙하다. 앞서 말했듯이 자료구조를 구현한다는 게 꼭 그 그래프라는 기존 인터페이스나 구현체를 사용하는 거라고 생각했는데(Stack때문인 것 같다. 다 그렇게 이미 존재하는 건 줄 알았다..ㅎ), 배열이나 리스트 등을 이용해서 직접 만들어야 한다는 걸 이번 유닛을 통해서 잘 알게 된 것 같다. 아직 좀 혼란스럽긴 하지만(?) 무튼 비가중치 그래프밖에 사용해보지 않았는데, 가중치 그래프를 사용하는 것도 살펴봐야겠다. 트리와 마찬가지로 문제에 직접 적용하는 건 아직 한참 남은 것 같다.

---

[Binary Search Tree]

🛒 이진 탐색 트리(Binary search tree)에 앞서, 이진 트리를 간단히 정의하자면, 자식 노드가 최대 두 개로 구성된 트리이다. 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree) 세 가지로 분류할 수 있다.
정 이진 트리는 각 노드의 자식이 0개 혹은 두 개인 이진트리.
완전 이진 트리는 마지막 레벨을 제외한 모든 노드가 두 개씩 가득 차있는 트리. 만약 마지막 레벨의 노드가 하나만 채워진다면 왼쪽이어야 한다.
포화 이진 트리는 정 이진트리이면서 완전 이진트리이다. + 마지막 레벨까지 모든 노드가 꽉꽉 채워져있어야 한다.
이진 탐색 트리는 값이 정렬되어있다. 정렬 순서는 왼쪽 자식 < 부모 < 오른쪽 자식 이다.

이해를 하는데 큰 문제는 없었다. 문제가 있다면 나의 응용력이다! 자료구조/알고리즘인 만큼 공통된 느낀점인 것 같다. 목표가 있다면 이진 트리나 이진 탐색 트리 외에 또 다른 트리들과, 균형 이진 탐색 트리에 대해 더 알아보는 것이다! 균형 이진트리에 대해 지금까지 알아본 내용은 이렇다. 이진 탐색 트리는 자동으로 정렬을 하면서 데이터가 들어가기 때문에, 값이 입력되는 순서에 따라 분명 한 쪽으로 치우친 트리가 나올 수 있다. 이것을 방지하기 위해 추가적으로 재구축 연산을 수행해주면서 균형 이진 트리를 만들어주기도 한다. Java에서는 대표적으로 TreeMap, TreeSet이 균형 이진 트리 구조라고 한다. 이를 레드-블랙 트리라고도 부르는 모양인데, 더 찾아보려고 한다.

---

[Search Algorithm]

🛒 트리 순회 방법을 순회 순서에 따라 세 가지로 나눈다면, 전위(preorder)/중위(inorder)/후위(postorder) 순회가 될 것이다.
우선, 방법에 따른 순회 순서 이전에 공통적으로 갖는 순회 순서는 트리 왼쪽 -> 오른쪽 방향이다. 이 방향을 기초로, 부모(루트)를 먼저 순회하느냐/중간에 순회하느냐/ 마지막에 순회하느냐에 따라 분류되는 것.
그래프 순회는 크게 두 가지로 나뉜다. 너비 우선 탐색(Breadth First Search)/깊이 우선 탐색(Depth First Search)이다.
BFS는 가장 가까운 정점을 우선 모두 →탐색 한 후, 차차 떨어진 정점들을 순회한다. 주로 두 정점 사이의 최단 경로를 구할때 사용한다. 큐를 이용해서 구현한다.
DFS는 하나의 경로를 끝까지 ↓탐색한 후, 다음 경로를  순회한다. 스택 또는 재귀를 이용해 구현한다. (해당 경로 탐색이 끝나면 들어온 차례로 다시 나가야 하므로)
모든 정점을 순회해야 한다면 무엇을 이용해도 상관 없을 수 있지만, 검색 대상이 굉장히 크다면 DFS를, 규모가 크지 않고 depth가 별로 깊지 않다면 BFS를 사용하는 것이 좋겠다.

순회,, 정처기 공부하면서 빡세게 해가지고(순서 찾기 재미있었다) 순회 과정은 문제 없었다. 문제는 탐색 알고리즘을 직접 구현하는 것이다! 이번에 코플릿 연습문제를 풀면서 BFS, DFS 문제를 모두 풀어봤는데 이해 과정이 정말 오래걸렸다. 특히 DFS를 구현하면서는 재귀를 이용했는데, 그 과정을 하나하나 손으로 써가면서 살펴보면서 머리가 터질 것 같기도 했었다. 해당 문제는 이해가 됐지만 또 다른 문제에 응용하려면 꽤 많은 시행착오를 겪어야할 것 같다!

이해하려는 노력의 흔적을 남겨두었다(웃겨서,,,)

 

---

🪗 Unit 2. 자료구조를 마치고!

점점 학습 난이도가 높아지는 게 느껴져 좀 겁이 났던 유닛..(지금 알고리즘 하면서 똑같은 생각을 하고 있다ㅎㅎ) 각 챕터별로, 공통적으로 들었던 생각은 어느정도 이해가 되었으니 문제를 접하면서 최대한 많이 익혀봐야겠다는 것이었다. 스프링 들어가기 전에 꼭 짬을 내서 알고리즘을 많이 익혀야겠다. 분명 그 때 되면 자료구조나 알고리즘을 살펴볼 시간이 많이 부족할 것 같다... 무튼 이번 회고를 작성하면서 원형큐라던가 균형이진트리 등 조금 더 향상된 자료구조를 살펴볼 수 있어서 좋았다. 그와 함께 기록도 할 수 있으니 금상첨화였다. 더 알아보고 싶은 자료구조는 Heap Tree! 사실 이건 우선순위가 높진 않고, 시간이 나거나 문제풀다가 질릴 때 쯤 한 번 찾아보려고 한다. 알면 알수록 무궁무진한 자료구조의 세계.. 그래도 부트캠프를 지원할 때 내가 얻고자 했던 부분이 정확히 채워지고 있는 방향으로 가고있는 것 같아 기분이 좋다. 팟팅🫠