🍒What I did today(자료구조 - 스택, 큐, 그래프, 트리)

✅자료구조(스택, 큐)

여러 개의 데이터들을 효율적으로 관리하기 위해 저장 순서나 처리 순서를 정해둔 '자료 구조'에 대해 배웠다.

가장 먼저 스택(Stack), 큐(Queue)에 대해 공부했는데 개념만 봐서는 이해하기 어려웠다.

각각의 자료 구조들의 관련된 메서드들을 코드로 작성해보기도 했지만, 이해가 어려웠다.

오히려 공부하다보니 개념이나 로직같은 것은 이해가 됐었지만, 그것을 코드로 옮기기가 정말 어렵고 힘들었다.

처음으로 포기할까... 생각을 여러번 했던 부분인 것 같다.

지금도 계속 보면서 이해하려고 노력중이다. 

내가 생각한 자료 구조를 코드로 옮기는 부분은 계속 연습해야 될 것 같다.

1. 수도 코드를 조금 더 잘 써보려고 노력하기

2. 자료구조를 언제 사용하는 게 효율적일 지 생각하기

실제로 스택이 일반적으로 구현되어 사용되는 부분이 있을까?

자료를 탐색하는 방법은 많이 사용한다고 한다.

앞으로 Tree나 Graph 자료구조를 배우게 될 텐데, 이들 자료구조는 큐와 스택을 모르면 이해도 어렵고 구현하기도 쉽지않다고 한다. 

큐와 스택을 써야지! 하고 쓴다기보다는 순서를 고려해야 하는 상황이거나 우선적으로 선택해야 하는 상황에서 많이 사용한다고 한다. (어떤 것을 선택하고, 어떤 것을 버려야 하는 문제가 아니라, 어떤 것을 먼저 선택할 것이냐의 문제에서는 대부분의 경우 사용한다.)

 

✅자료구조(그래프, 트리, BST(Binary Search Tree))

그래프, 트리, BST 자료 구조들의 메서드들의 개념을 생각하고 그것을 코드로 작성하는 시간도 가졌다.

세가지 구조 모두 기본적으로 노드(node)라고 하는 요소들과 노드와 노드를 연결하는 간선으로 구성된다.

트리랑 이진 검색 트리는 순서나 방향이 정해져 있다. 그래도 나는 트리랑, 이진 검색 트리가 그나마 제일 괜찮았다.

트리와 이진 검색 트리를 코드로 작성할 때 재귀를 사용했던 것 같다.

재귀가 어떤식으로 실행되는지 스터디 하는분이랑 콘솔창으로 확인까지 했을 때 행복했다...(좀 친해진 느낌....)

그리고 그래프를 대충 설명하자면... 연결되어 있는 객체 간의 관계를 표현할 수 있는 것이 자료 구조 그래프(Graph)이다.

처음엔 데이터들끼리 다 연결되어 있는 그래프구나 생각했다.

간단하다고 생각했지만 공부하다보니 방향성 여부에 따라서도 구분되고, 구현하는 방식도 인접 리스트 방식 인접 행렬 방식 두가지로 나누어져서 알아봐야했다.

인접 리스트는 그래프 내에 간선이 많이 없는 희소그래프일 때 많이 사용하고, 간선이 많아 관계가 복잡할 때는 인접 행렬을 주로 사용한다고 했다.

(자료구조에 대해(?) 개념정도는 블로깅해두어야겠다고 한다. 결국 코드로 작성하는 것이 제일 어렵지만...💧)

 

 

🍒Remember

---

✅Coplit을 풀다가 알게 된 내용들(?)

1. fill() : 배열의 시작 인덱스부터 끝 인덱스의 이전까지 하나의 값으로 채워버리는 메서드

(ex. let x = new Array(10).fill(0) => 0이 10개 들어있는 배열 생성)

2. shift(), unshift() : 배열 메서드 중 맨앞 요소를 삭제하고 추가하는 shift, unshift는 요소들을 하나씩 다 옮겨야해서 시간복잡도가 무려 O(n)이다.

3. splice() : 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경하는 메서드이다.

(ex. let months =['Jan', 'March', 'April', 'June'] months.splice(1, 0 'Feb') Feb라는 인덱스를 1번째에 추가 0은 교체할 자리)

 

✅트리 순회 방식

전위 순회(Preorder Traversal): 부모 → 좌 → 우

중위 순회(Inorder Traversal): 좌 → 부모 → 우

후위 순회(Postorder Traversal): 좌 → 우 → 부모

코드로 작성할 때에도 위와 같이 작성해주어야한다. (예시)

 

✅그래프, 트리

그래프(Graph) : 정의 노드간 관계를 간선으로 연결한 자료구조(네트워크 모델)

트리(Tree) : 노드들을 간선으로 연결한 계층형 자료구조(계층 모델)

 

✅자료구조란?

여러 데이터들의 묶음을 어떻게 저장할 것이고, 사용할 것인지 정의한 것

대부분의 자료구조는 특정한 상황에 문제를 해결하는 데에 특화되어 있습니다.

 

✅자료구조 이해의 목표

1. 자료구조가 무엇인지 설명할 수 있다

2. Stack, Queue, Tree, Graph 자료구조에 대해 이해할 수 있다.

3. 알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체하여 흉내낼 수 있다.

4. 각 자료구조의 개념과 구조를 파악하고 목적을 이해할 수 있다.

5. 알고리즘 문제의 각 상황에 맞는 자료구조를 떠올릴 수 있다.

6. 트리 및 그래프의 탐색 기법에 대해 이해할 수 있다.

7. Binary Search Tree를 이해할 수 있다.

8. BFS와 DFS의 개념을 이해하고 알고리즘 문제에서 사용할 수 있다.

9. 자료구조를 활용하여 알고리즘 문제에 접근할 수 있다.

 

🍒More Study

---

✅우선순위큐(heap)

✅원형큐

✅그래프와 트리의 차이점?

✅시간복잡도

 

2021-03-04~07 

---

03.04~05(목, 금) 😥

자료구조를 배우기 시작했고, 스택, 큐, 그래프, 트리 등으로 개념을 이해하기 시작했다.

자료 구조에 대한 개념은 이해했는데 코드로 작성하라고 하니까... 너무 어려워서 처음엔 아무것도 못했다.

페어 분이 알고리즘 문제 같은 것은 캐리해주셨고, 그것을 바탕으로 계속 코딩해보고 정리를 무한반복했다.

그래도 쉽지 않았다. 자료 구조를 이해한 것을 바탕으로 코드로 작성한다는 것이 이번 목표에서 제일 어려운 부분인 것 같다.💧

 

주말엔 공부를 할까 했지만! 머리도 식힐 겸 서울로 놀러갔다왔다ㅎㅎㅎㅎ

맛있는거 많이먹고 머리를 식혀주는 느낌을 많이 받았다. 

다 포기할까 생각했는데? 또 기분 전환을 하고오니 다시 열심히 해야겠다라는 마인드가 돌아왔다😄

쉬었으니 자료 구조 정리해야지? ㅎㅎ..😅