🍒What I did today(시간복잡도, BFS, DFS)
✅목표 그리고 전제조건
Achievement Goals
- 알고리즘이 무엇인지 설명할 수 있다.
- 알고리즘 문제를 이해하고 전략을 세울 수 있다.
- 알고리즘 풀이에 필요한 수도 코드를 작성 할 수 있다.
- 수도 코드에서 세운 전략을 코드로 구현 할 수 있다.
- 내가 구현한 알고리즘을 자바스크립트 언어로 설명 할 수 있다.
Prerequisite
- 기본적인 (stack,queue,tree,graph 등)자료 구조에 대한 이해
- 모듈 단위로 나누어 생각하는 법
✅Big-O 표기법, 자료 구조와 연관지어 생각해보기
빅오(Big-O) 표기법은 알고리즘이 돌아가는 최악의 시간이고, 상수, 지수 등이 있다는 것만 알아두면 될 것 같다.
어떤 코드가 어느정도의 시간이 걸리는구나 라는 것을 대충 알게되는 것 같다.
빅오 표기법에 대해 정리하는 것은 시간이 남을 때 따로 정리해야될 것 같다.
조금씩 정리해두었던 것이 있기 때문에 주말에 차차 정리하지않을까 생각이 든다!
✅BFS(Breadth-First- Search) ? DFS(Depth-First Search) ?
BFS는 너비 우선 탐색이고, DFS는 깊이 우선 탐색이라고 한다.
그래프를 탐색하는 방법이라고도 한다.
그래프란? 정점(node)와 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말한다.
그래프를 탐색한다는 것은 하나의 정점으로 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미한다.
오늘 코플릿을 풀면서의 핵심은 DFS는 스택 또는 재귀함수로 구현하고, BFS는 큐를 이용해서 구현한다는 점에서 매우 많은 도움을 얻었다.
이것 또한 따로 Data Structure 복습하면서 블로그에 정리해봐야 할 것 같다.
그리고 BFS, DFS를 하기전에 지난 시간에 배운 기본적인 자료 구조에 대해 이해가 매우 필요하다.
모른다면 이해할 수 가 없다고 난 생각한다💧
🍒Remember
✅Math.ceil(10, 2) //11, 10.2를 올림
✅DFS(깊이우선탐색)
- 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
- 스택 또는 재귀함수로 표현
✅BFS(너비우선탐색)
- 현재 정점에 연결된 가까운 점들부터 탐색
- 큐를 이용해서 구현
✅시간 복잡도(Time Complexity)
문제를 해결하는 알고리즘에 대한 로직을 작성할 때, 시간 복잡도를 고려한다.
입력값의 증가/감소함에 따라 시간이 얼마만큼 비례하여 증가/감소하는가?
Big-O 표기법? 시간 복잡도를 표기하는 방법이다.
간단하게 3가지가 있다.
최악, 최선, 중간(평균)의 경우이다.
입력 값의 증가에 다라 시간 복잡도가 얼마나 증가하는 지 표기하는 방법이다.
- Big-O
- Big-Ω(메가)
- Big-θ(세타)
🍒More Study
✅Big-O 정리(알고리즘)
✅BFS, DFS 정리(알고리즘)
✅그래프 트리 BST 정리(자료구조)
✅해시테이블(Hash Table), 연결 리스트(Linked List) 정리(자료구조)
2021-03-08
오늘도 여전히 Coplit을 풀면서 자연스럽게 멘탈이 나가는 날이다💧
이해하기 위해 여러 장에 종이가 사용되었고, 로직은 이해가되는데? 코드로 작성을 못하겠다? 이 부분을 최대한
페어랑 같이 해결해 나아가려고 노력했다.
결과는 생각보다 좋았고, 배운 것이 더 많았던 것 같다.
아직 정리 해야 될 내용들이 너무 많은데 너무 피곤해서 정리를 못했다.(나약해...)
이번주에 Solo study 시간이나 주말에 확실하게 정리하고 넘어가야될 것 같다.