- 시작하게 된 계기 및 다짐 😮
-
이번 코드스테이츠의
백엔드 엔지니어링 개발자 부트캠프에 참여하게 되면서 현직개발자 분들의 빠른 성장을 위한 조언 중 자신만의 블로그를 이용하여 배운 것 들을 정리하는게 많은 도움이 된다 하여 시작하게 되었다.- 그 날 배웠던 것을 길지 않아도 좋으니 정리하며 복습하는 습관 기르기
- 주말에 다음주에 배울 내용들을 예습
- 코딩 문제와 java코드들은 꾸준히 학습
- 자료구조를 이용한 알고리즘 문제 해결 학습
- 학습 목표 😮
| 목표 | 결과 |
|---|---|
| 알고리즘 문제를 stack/queue 자료구조를 배열로 대체하여 사용하기 | O |
| stack/queue에 대한 개념과 구조/목적을 이해 | O |
| 알고리즘 문제의 각 상황에 대한 stack/queue 사용 | O |
| Grahp를 통한 탐색(visit,not-visit) | O |
| Tree를 통한 데이터 검색 | O |
- 정리
Stack
- FILO(First in Last Out)형식을 지니고 있는 자료구조
- 한 방향으로 데이터를 저장/삭제를 할 수 있음(제한적 접근)
- 데이터는 하나씩 넣고 뺄 수 있음
- Push를 통해 데이터를 넣고 pop을 통해 가장 최근에 값을 뺄 수 있음
- 접시를 쌓는 형태로 볼 수 있음
- 브라우저의 페이지를 다음/이전 페이지를 사용할 떄 스택을 활용 할 수 있음
ex)
- ArrayList를 통해 이를 직접 구현 할 수 있음
- Stack<?> stack = new Stack<>();
- .push(), .pop()을 통한 데이터 조작
- show(), peek(), clear()
Queue
- FIFO(First In First Out)형식을 지니고 있는 자료구조
- 한 방향으로 데이터가 들어오고 다른 방향으로 데이터가 나가는 형식
- 데이터는 하나씩 넣고 뺄 수 있음
- enqueue를 통한 데이터 추가와 dequeue를 통한 데이터 삭제를 사용
- 데이터가 입력된 순서대로 처리할 때 보통 사용
- 처리속도가 빠른 장치와 느린 장치 사이에서 보통 사용하고, 큐에 먼저 처리한 장치의 데이터를 받아 놨다가 일정한 속도로 느린 장치에 넘겨서 데이터를 처리
ex)
- ArrayList를 이용하여 직접 구현 가능
- Queue<Integer> queue = new LinkedList<>()
- .add() : 값 추가
- .poll() : 첫 번째 값을 반환하고 제거
- peek(),show(),clear()
# Circular Queue(원형큐)
# 버퍼링 : 각 장치 사이에 존재하는 시간/속도 차이를 극복하기 위한 대기 공간
Graph
Graph
- 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
- 간선 (edge): 정점 간의 관계를 나타냅니다. (정점을 이어주는 선)
- 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
- 가중치 그래프 (weighted Graph): 연결의 강도가 얼마나 되는지 적힌 그래프
- 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프
- 무(방)향 그래프 (undirected graph) : 방향성이 없는 그래프 (양방향)
- 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지 나타냄
- 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 인접이라함
- 자기 루프 (self loop): 한 정점에서 바로 자기자신 정점으로 이어진 상태
- 사이클 (cycle): 한 정점에서 출발하여 다시 그 정점으로 돌아 올 수 있는 그래프 상태
- 인접행렬 : 두 정점의 연결관계
: 가장 빠른 경로를 찾을 때 주로 사용한다.
: 모든 경우의 수를 저장하기에 메모리 차지가 많음
- 인접리스트 : 각 정점이 어떤 정점과 인접해 있는지를 리스트의 형태로 표현
: 메모리를 효율적 사용하고 싶을 때
: 상대적으로 인접행렬보다 적은 메모리 사용
==> 모두 무방향 그래프로 사용 가능
# 사진
ex) 인접행렬 예시
int[][] graph;
1은 연결(갈수있다), 0은 비 연결
[0][2] == 1 --> A에서 C로의 연결이 한개 있다는 의미
ex) 인접리스트 예시
ArrayList<ArrayList<Integer>> graph;
Tree
Tree
- 비 선형 구조, 계층적 표현, 사이클이 없음
- 깊이,레벨,높이,서브트리
- 디렉토리/파일 시스템 등에서 사용
ex)
String value;
ArrayList<클래스> childern;
# 여러가지 트리 구조 추가 학습
BST (binary search tree) _ 이진탐색트리
- 왼쪽 자식의 값은 루트/부모보다 작고 오른쪽 자식의 값은 부모/루트보다 큰 값을 가자고 있음
1. 정 이진 트리(Full binary tree) : 자식이 모두 0 or 2의 노드를 가지고 있는 트리
2. 포화 이진 트리 : 정 이진트리이며 완전 이진트리인 경우, 노드의 레벨이 갖고 레벨이 가득 채워져 있음
3. 완전 이진 트리 : 마지막 레벨은 제외한 모든 노드가 가득차 있고 , 마지막 레벨의 노드는 전부 차있지 않아도 되지만 왼쪽부터 채워져야함
# (루트를 기준으로)
전위순회 : 루트 -> 왼쪽 -> 오른쪽 탐색
중위순휘 : 왼쪽 -> 루트 -> 오른쪽 탐색
후위순회 : 왼쪽 -> 오른쪽 -> 루트 탐색
---
Search 알고리즘
1. Tree traversal
- 전위순회 : 루트 -> 왼쪽 -> 오른쪽 탐색
- 중위순휘 : 왼쪽 -> 루트 -> 오른쪽 탐색
- 후위순회 : 왼쪽 -> 오른쪽 -> 루트 탐색
2. BFS (너비 우선 탐색)
- 같은 레벨의 노드들을 먼저 탐색하는 방법
# 장점 : 최적해를 찾음을 보장한다.
★ 재귀 / 큐 사용
답이 여러개/최단 경로가 존재하면 반드시 최장경로 찾음
노드 수가 적고 깊이가 얕은 해가 존재할 때 유리
큐를 사용해 노드들을 저장하여 DFS와 달리 저장공간이 큼
# 단점 : 최악의 경우 실행에 가장 긴 시간이 걸린다
3. DFS (깊이 우선 탐색)
- 하나의 노드의 깊이를 끝까지 우선 탐색하는 방법
# 장점 : 최선의 경우 가장 빠른 알고리즘이다.
찾아야할 노드가 깊이 있을 경우 유리
BFS에 비해 저장 공간이 적다
# 단점 : 최악의 경우 가장 오랜 시간이 걸린다.
답이 얕은 노드에 있을 경우 오랜 시간이 걸린다
답이 여러개면 찾은 해가 최단 경로라는 보장이 없음
- 피드백 😮
-
Stack/Queue/Graph/Tree 자료구조 형태에 대하여 학습을 해보았는데, 이에 관하여 이해는 되지만 실 문제에 적용하여 해결하기가 쉽지 않다.
-
Queue의 경우, 원형 Queue와 같은 추가적인 Queue의 형태가 존재하고 Stack과 비교하여 어떤것을 사용하여 문제를 해결할 지 잘 생각해 봐야 겠다.
-
Graph와 Tree는 앞의 Stack과 Queue에 비하여 좀 더 학습에 어려움을 겪었다. 이는 코플릿과 타 알고리즘 문제를 해결하면서 익숙해 져야 할 것 같다.
*Deque, Linked-List, Hash Table, HeapTree등 알아두면 좋은 자료구조에 대하여도 추
가적인 학습을 하여야 겠다.
- 앞으로 해야 될 것 😮
- 매일 꾸준히 할 것
- 꾸준히 velog 작성
- Java 언어 및 Algorithm 공부(Coding-Test)
- 틈틈히 운동 하기
- 내일 해야 할 것
- 코딩을 시작하기 전 어떤 식으로 해결할지 의사코드를 활용한 계획세우기
- 앞서 배웠던 재귀/자료구조를 활용하여 실제 알고리즘 문제를 해결하기
Will be great Backend-developer