⚠️ 하루동안 제가 배운 것을 간단하게 정리한 글입니다.⚠️

목차

• 오늘 배운 것
  • 이진 탐색
  • 그래프
• 소감
• 세 줄 요약

✏️오늘 배운 것

이진 탐색

정렬 되어있는 요소들을 반 씩 제외하며 찾는 알고리즘 O(log n)

특징

• 반드시 정렬되어야 함
• 배열 혹은 이진 트리를 이용하여 구현 가능

이진 탐색 트리

이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여있고 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.

• 문제점: 최악의 경우 한 쪽으로 편향된 트리가 될 수 있음, 이런 경우 순차 탐색과 동일한 시간 복잡도
• 해결법: AVL 트리, 레드-블랙 트리

그래프

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조

특징

• 정점은 여러 개의 간선을 가질 수 있다.
• 크게 방향 그래프와 무방향 그래프로 나눌 수 있다.
• 간선은 가중치를 가질 수 있다.
• 사이클이 발생할 수 있다.

다양한 그래프

• 무방향 그래프 : 간선으로 이어진 정점끼리는 양방향으로 이동이 가능 ex) 양방향 통행 도로
• 방향 그래프 : 간선에 방향성이 존재하는 그래프 ex) 일방 통행
• 연결 그래프 : 모든 정점이 서로 이동 가능한 상태인 그래프
• 비연결 그래프 : 특정 정점쌍 사이에 간선이 존재하지 않는 그래프
• 완전 그래프 : 모든 정점끼리 연결된 상태인 그래프
  • 한 정점의 간선수 = 모든 정점의 수 -1
  • (모든 정점의 수 - 1) * 정점 수 = 모든 간선의 수
• 사이클 : 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분

👦소감

오늘 역시 다양한 자료구조와 알고리즘 문제를 풀었다. 그렇기 때문에 깊이 있는 자료를 만들지 못했다. 주말마다 최소 하나씩 주제를 잡아서 깊이 있는 자료구조 글을 작성 해야겠다. 예전에 알고리즘 문제를 볼 때 어떻게 풀어야할 지 막막했는데 자료구조를 알고나니 어떻게 풀어야 할 지 감이 좀 잡히기 시작한다. 꾸준하게 하는 게 답이라고 하니 5개월 뒤면 lv.3문제 정도는 풀 수 있지 않을까 기대한다. 🙏 내일 주말이라고 쉬지 않으려고 한다. 컨디션 조절은 해야 겠지만 할 공부가 많기 때문에 내일도 열심히 해야겠다.🔥

👊세 줄 요약

• 끝이 안 보이는 자료구조와 알고리즘 공부💦
• 깊이 있는 자료구조 공부의 필요성을 느낌
• 내일 주말이라고 놀 생각마라.😡