[데브코스] TIL - 6일차

오늘 공부한 내용 💻

• 자료구조 & 알고리즘 - BFS, DFS
• [실습] 여행경로
• 자료구조 & 알고리즘 - 그리디(Greedy)
• [실습] 큰 수 만들기
  
  

어려웠던 내용 🤢

너비 우선 탐색(BFS)

• 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 확인하는 알고리즘이다.

• 너비 우선 탐색의 특징

  • Queue를 이용하여 구현 가능하다.
  • 시작 지점에서 가까운 정점부터 탐색한다.
  • 정점의 수가 V, 간선의 수가 E라고 하면 시간 복잡도는 O(V+E)이다.

깊이 우선 탐색(DFS)

• 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘이다.

• 깊이 우선 탐색의 특징

  • Stack을 이용하여 구현 가능하다.
  • 시작 정점에서 깊은 요소부터 찾는다.
  • 정점의 수가 V, 간선의 수가 E라고 하면 시간 복잡도는 O(V+E)이다.

그리디(Greedy)

• 매 선택에서 가장 그 순간 가정 최선인 답을 선택하는 알고리즘이다.

• 최적해를 보장하지 않는다

• 그리디의 특징

  • 보통 최적해를 구하는 알고리즘 보다 빠르다.
  • 크루스칼 / 다익스트라 알고리즘에 사용된다.
  • 직관적인 문제풀이에 적합하다.
    
    

더 공부할 내용 📃

• BFS/DFS문제 더 풀어보기
• 트리, 트라이 과제 PR하기
• [실습] 여행경로 해결하기 (ㅜㅜ!)
  
  

느낀점 👀

> '네버엔딩 자료구조 ...'

오 늘 도 자료구조&알고리즘 수업 !
첫 과제를 제출하느라 좀 많이 헤매서 오늘은 공부에 시간을 많이 쏟지 못했다 ...
그래도 과제 PR도 날려보고 깃헙에 점점 익숙해지는 것 같아서 뿌듯하다 !

BFS/DFS는 코딩테스느 공부를 하면서도 항상 이해를 못한 채 안고가던 부분인데 이번 기회에 확실하게 하고 가고싶다. 제발ㅠ... 제발 좀 ...
코테를 파이썬으로 준비했어서 그런지 실제 코테에서 큐같은 자료구조를 직접 구현해서 써야 한다고 생각하니 좀 막막하기도 하지만 ...
막막하면 니가 머 어쩔건데 ...? 아자아자 화이팅 ( •̀ ω •́ )✧

참고 사이트 🙄

• https://programmers.co.kr/