[TIL] Day5

사실 하루 지나서 작성하는 중이지만 어제는 너무 아무것도 하고싶지 않은 날이었기에
다음날 작성중이다. 사실 Day6임

어제 = 망한날

어제은 굉장히 잘된일이 없는 날이었다. cs스터디 발표도 망했고, 과제도 잘 풀리지 않았고,
알고리즘 공부도 거의 처음 하다보니 이해하기 힘들었다...
그렇지만 과제도 내일까지고 발표도 다음번에 잘하면 되니까 으쌰으쌰 힘내보도록 하자!!
라고 생각하며 그냥 잠을 청했다.

학습한 내용

• 트리 - 방향 그래프의 일종 하나의 루트에서 하위로 뻗어나가는 구조

  • 이진트리 - 각 정점이 최대 2개의 자식을 가지는 트리 (탐색에 많이 사용)
    완전 이진 트리 - 마지막 레벨을 제외하고 모든 정점이 채워져 있음
    포화 이진 트리 - 마지막 레벨까지 모든 정점이 채워져 있음
    편향 트리 - 한 방향으로만 정점이 이어짐

• 힙 - 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해
  요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다.

• 트라이 - 문자 자동완성을 구현 할 때 사용
  문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

• 비교식 정렬

  • 버블 정렬 - 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘
    O(n^2) n-1번 순회
  • 선택정렬 - 가장 우선순위가 높은 요소를 교환
    O(n^2)
  • 삽입 정렬 - 선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 방식
    O(n^2)
    

• 분산식 정렬

  • 분할 정복을 사용한다.
    • 문제를 작은 2개의 문제로 분리 더이상 분리가 불가능 할 때 처리한 뒤 합치는 전략
  • 합병 정렬
    • 최선과 최악이 같은 안정적인 정렬 알고리즘
  • 퀵 정렬
    • 최악의 경우가 존재하는 불안정 정렬

• 선형탐색 - 순차적으로 찾아가는 방식 선형시간 소요

• 이진탐색 - 요소들이 정렬되어있고 요소를 반씩 줄여가며 탐색

  • 반드시 정렬되어있어야함
  • 배열 혹은 이진 트리를 이용하여 구현
  • O(log)n 의 시간 소요

• 너비 우선 탐색(BFS)

  • 같은 깊이에 해당하는 정점부터 탐색
  • queue를 이용하여 구현 가능
  • 시작점부터 가까운 정점부터 탐색
  • V가 정점의 수 , E가 간선의 수 일 때 O(V +E)

• 깊이 우선 탐색(DFS)

  • 최대한 깊은 정점부터 탐색하는 알고리즘
  • Stack 이용하여 구현
  • 시작정점에서 깊은것 부터
  • V가 정점의 수 , E가 간선의 수 일 때 O(V +E)

마치며

알고리즘을 공부 하면서 프로그래머스에서 연습도 해보았는데 문제에 어떤 알고리즘을
넣어서 사용하면 좋은가를 빠르게 판단하는것이 가장 힘든 부분인것 같다. 
실제로 구현하는 부분도 아직 처음이라 많이 헤매고있지만 열심히 풀다보면 실력이 늘겠지...