후기
자료구조, 알고리즘 코플릿 문제가 어려웠다. 로직을 짜기도 어렵지만 엣지 케이스를 생각해서 조건을 추가해주는 것은 더 어려웠다. 며칠 동안 데일리 코딩과 코플릿 한 문제를 2, 3시간 넘게 붙잡고 있으니 비효율적이라고 느꼈다. 막상 문제를 풀어도 의도한 바와 달라 내가 고민한 시간이 공부 시간이라고 할 수 있을까? 라는 생각이 들면서 힘이 빠지는 경우도 있었다. 정한 시간이 초과하면 레퍼런스로 넘어가 논리 흐름을 확인하고 다시 풀어봐어보는 것을 반복해야겠다.
Chapter1. 자료구조
-1. 자료구조
-2. 자료구조 Roadmap
Chapter2. Stack과 Queue
-1. Stack
-2. 큐(Queue)
Chapter3. Tree와 Graph
-1. Tree
-2. Binary Search Tree
-3. Tree Traversal
-4. Graph
-5. BFS와 DFS
<Chapter1. 자료구조>
1.자료구조
1) 정의
여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것
2) 분류
3) 자료구조 사이트
-Data Structure Visualizations
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
-Visualgo
https://visualgo.net/en
<Chapter2. Stack과 Queue>
Stack, Queue -> 선형구조
1.Stack
1) Stack의 구조
가장 먼저 들어간 데이터가 가장 나중에 나옴
-push: Stack에 데이터를 넣는 것
-pop: Stack에 데이터를 꺼내는 것
-top:가장 위에 있는 데이터
2) Stack의 특징
-LIFO(Last In First Out), 후입선출
-데이터는 하나씩 넣고 뺄 수 있음(한꺼번에 여러 개❌)
-하나의 입출력 방향
-저장되는 데이터는 유한하고 정적이어야 함
- 유한: 그 다음 함수가 종료될 때마다 최상위 블록이 지워지므로, 해당 함수에 의해 스택에 들어간 모든 변수가 지워짐.
- 정적: 정적 특성을 가져야지만 컴파일 시간이 결정
- 스택에 저장되는 일반적인 데이터: 로컬 변수(value type 또는 프리미티브, 프리미티브 상수), 포인터, 함수 프레임
-스택의 크기는 제한
3) Stack의 실사용 예제
-브라우저의 뒤로 가기, 앞으로 가기 기능
2.큐(Queue)
1) Queue의 구조
가장 먼저 들어간 데이터가 가장 먼저 나옴
뒤(rear)로 들어가서 앞(front)으로 나옴
-front: 맨 앞쪽에 있는 데이터
-rear: 맨 뒤쪽에 있는 데이터
-enqueue: rear++, 해당 위치에 요소 삽입(Queue에 데이터를 넣는 것)
-dequeue: front++, 해당 위치의 요소 삭제(Queue에 데이터를 꺼내는 것)
2) Queue의 특징
-FIFO(First In First Out), 선입선출
-데이터는 하나씩 넣고 뺄 수 있음
-두 개의 입출력 방향
3) Queue의 실사용 예제
-프린터 출력
4) 원형 큐
선형 큐의 front와 rear값이 계속 증가하기만 한다는 문제점을 극복한 구조
-front: 첫 번째 요소의 하나 앞에 있는 데이터(❗️일반 queue와 front 개념이 다름)
-rear: 마지막 데이터
-enqueue: rear++%큐 사이즈, 해당 위치에 요소 삽입
-dequeue: front++%큐 사이즈, 해당 위치의 요소 삭제
출처: https://www.geeksforgeeks.org/advantages-of-circular-queue-over-linear-queue/
<Chapter3. Tree와 Graph>
Tree, Graph -> 비선형 구조
Graph가 Tree 포함
1.Tree
1) Tree의 특징
-하나의 데이터 아래에 여러 개의 데이터가 존재 가능(비선형 구조)
-아래로만 뻗어나감 -> 사이클이 없음(시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 돌아올 수 없음)
2) Tree의 구조
-노드: 트리 구조를 이루는 모든 개별 데이터
-루트: 트리 구조의 시작점이 되는 노드
-부모 노드: 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
-자식 노드: 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
-리프: 트리 구조의 끝 지점이고, 자식 노드가 없는 노드
-깊이: 위부터 0
-레벨: 위부터 1, 같은 깊이를 가지고 있는 노드를 묶어서 표현, 같은 깊이 -> 같은 레벨 -> 형제노드
-높이: 아래서부터 0중 최댓값
-서브 트리: 트리 안의 트리
3) Tree의 실사용 예제
-컴퓨터 디렉토리 구조
-월드컵 토너먼트 대진표
-가계도(족보)
-조직도
2.Binary Tree & Binary Search Tree
Binary Tree가 Binary Search Tree 포함
1) Binary Tree(이진 트리)
-정의
자식 노드가 최대 두 개인 노드로 구성된 트리(왼쪽 자식, 오른쪽 자식)
-Full Binary Tree(정 이진 트리): 자식 노드가 0개 아니면 2개
-Complete Binary Tree(완전 이진 트리): 마지막 레벨을 제외한 노드 -> 가득 차 있어야 함, 마지막 레벨의 노드 -> 왼쪽부터 채워져야 함
-Perfect Binary Tree(포화 이진 트리): 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리(피라미드 모양, 2^n - 1개의 노드), ✅Perfect -> Full, Complete ❌Full, Complete ->. Perfect
2) Binary Search Tree(이진 탐색 트리)
-구조
- 각 노드에 중복되지 않는 키(Key)가 있음
- 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있음
- 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있음
- 좌우 서브 트리도 모두 이진 탐색 트리여야 함
-특징
- 기존 이진 트리보다 탐색이 빠름
- 트리의 높이가 h(height)라면 o(h)의 복잡도
- 반드시 트리의 높이(h) 이하의 탐색이 이뤄지게 됨
- 트리 안에 찾고자 하는 값이 없다면 트리의 높이(h) 번의 연산 및 탐색이 진행
-탐색 과정
① 루트 노드의 키와 찾고자 하는 값을 비교. 만약 찾고자 하는 값이라면 탐색 종료.
② 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색 진행.
③ 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색 진행.
④ 찾을 때까지 반복
3.Tree Traversal
트리 순회: 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽
1) 전위 순회(preorder traverse)
루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색
루트 부모 -> 왼쪽 자식 -> 오른쪽 자식
2) 중위 순회(inorder traverse)
제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색
제일 왼쪽 끝에 있는 노드 왼쪽 자식 -> 부모 -> 오른쪽 자식
이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰임
3) 후위 순회(postorder traverse)
트리 삭제시 사용(자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문)
제일 왼쪽 끝에 있는 노드 왼쪽 자식 -> 오른쪽 자식 -> 부모
4.Graph
그래프: 여러 개의 점이 서로 복잡하게 연결된 관계를 표현한 자료구조
1) 구조
정점(vertex): 점
간선(edge): 선
직접적인 관계 -> 선으로 이어짐
간접적인 관계 -> 몇 개의 점과 선에 걸쳐 이어짐
단방향 간선 2개, 양방향 간선 1개
2) Graph의 표현 방식
2-1) 인접 행렬
-구조
정점이 이어져 있음 -> 1(true)
정점이 이어져 있지 않음 -> 0(false)
만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장
출처: https://cloudstudying.kr/challenges/368
-사용 예시
가장 빠른 경로(shortest path)를 찾기
2-2) 인접 리스트
-구조
각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
각 정점마다 하나의 리스트를 가지고 있음
각 리스트는 자신과 인접한 다른 정점을 담고 있음
진출 차수가 2개 이상을 경우 리스트 순서는 보통 중요하지 않음. 우선순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용하는 것이 합리적
-사용 예시
메모리를 효율적으로 사용하고 싶을 경우(인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지)
2-3) 알아둬야 할 Graph 용어들
정점(vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
간선(edge): 정점 간의 관계를 나타냄(정점을 이어주는 선)
인접 정점(adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
가중치 그래프(weighted Graph): 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프
비가중치 그래프(unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프
무(방)향 그래프(undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있음.
진입차수(in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄.
인접(adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점
자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현. 다른 정점을 거치지 않는다는 것이 특징.
사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울로 이동이 가능하므로, 사이클이 존재하는 그래프.
비연결 그래프: 무방향 그래프에서 특정 정점 사이에 경로가 존재하지 않는 경우
연결 그래프: 무방향 그래프에 있는 모든 정점에 대해 항상 경로가 있는 경우
2-4) Graph의 실사용 예제
-내비게이션(가중치 그래프)
5.BFS와 DFS
그래프 탐색: 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적
1) BFS(Breadth-First Search), 너비 우선 탐색
-방법
가까운 정점부터 탐색. 그리고 더는 탐색할 정점이 없을 때, 그다음 떨어져 있는 정점을 순서대로 방문
-장점
최적해를 찾음을 보장
-단점
최소 실행시간보다는 오래 걸린다는 것이 거의 확실
최악의 경우, 실행에 가장 긴 시간이 걸릴 수 있음
-특징
그래프 규모가 작고, depth가 얕을 때 고려
-사용 예시
두 정점 사이의 최단 경로를 찾을 때 사용
2) DFS(Depth-First Search), 깊이 우선 탐색
-방법
하나의 경로를 끝까지 탐색한 후, 다음 경로로 넘어가 탐색
-장점
최선의 경우, 가장 빠른 알고리즘
‘운 좋게’ 항상 해에 도달하는 올바른 경로를 선택한다면, 깊이 우선 탐색이 최소 실행시간에 해를 찾음
-단점
찾은 해가 최적이 아닐 가능성이 있음
답이 아닌 경로가 매우 깊다면, 그 경로에 깊이 빠질 우려 있음
최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해에 도달하는 데 가장 오랜 시간이 걸림
-특징
그래프가 매우 클 때 고려
-사용 예시
경로의 특징을 저장해야 하는 경우(ex. a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 됨)
