자료구조&알고리즘 용어 정리

💪🏽 들어가며...

오늘의 포스트는 간단하게 자료구조와 알고리즘의 용어에 대해 정리하는 글입니다.
말 그대로 용어에 대한 정리이기 때문에 해당 내용을 자세하게 공부하고 싶으신 분들은 따로 구글링하는 과정이 필요할 것입니다!😉

🎰 스택

• 후입선출(LIFO)
  • 늦게 들어갈수록 빨리 나오는 구조
• 삽입, 삭제 연산의 시간 복잡도는 O(1)

💘 큐

• 선입선출(FIFO)
  • 먼저 들어갈수록 먼저 나오는 구조
• 삽입, 삭제 연산의 시간 복잡도는 O(1)

🗃 덱

• 배열과 동일하게 앞/뒤에서 삽입, 삭제가 모두 가능한 구조
• 배열과는 달리 삽입, 삭제 연산의 시간 복잡도는 O(1)

🌳 이진 트리

• 이진 트리
  • 트리에서 자식의 수를 최대 2개로 제한
• 이진 탐색 트리
  • 이진트리에서 부모의 왼쪽 방향의 있는 노드들은 전부 부모보다 값이 작고, 우측 방향에 있는 노드들은 전부 부모보다 값이 큰 트리
• 완전 이진 트리
  • 이진 트리의 모든 값이 왼쪽에서 순서대로 차 있는 트리
  • heap 자료 구조는 완전 이진 탐색 트리의 특별한 경우

#️⃣ 해시

• 해시 함수
  • 임의의 데이터를 받아, 해당 데이터를 고정된 길이의 특정 값으로 반환하는 함수
• 해시 함수를 이용하면 삽입, 삭제, 검색의 시간 복잡도는 O(1)

🔫 DP(동적계획법)

• 큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 먼저 해결하고, 이를 이용해 비교적 간단한 문제를 해결하는 방법
• 항상 점화식을 기반으로 하며 재귀함수나 반복문을 이용해서 구현 가능

📈 그래프

• 노드와 노드 간을 연결하는 간선으로 구성된 자료구조
• 트리는 사이클이 존재하지 않아도 되는 반면, 그래프는 사이클 존재 가능
  • 트리보다 큰 범위에 속하는 것이 그래프

🧭 BFS/DFS

• BFS
  • 깊이 우선 탐색
    • 최대한 깊게 탐색 후, 더 이상 도달할 수 없는 상황에 이전으로 돌아감
  • 재귀함수 와 스택 을 이용해서 구현
• DFS
  • 너비 우선 탐색
    • 하나의 노드 방문 후, 인접 노드 중 방문한 적이 없는 노드를 순차적으로 방문하는 노드
  • 큐 를 사용하여 구현

⏰ 다익스트라/플로이드 워셜

• 그래프 내에서 최단 거리를 구하는 알고리즘
• 다익스트라
  • 특정 시작점에서 다른 모든 정점으로 가는 최단거리를 구하는 알고리즘
  • K까지의 거리 = A까지 거리 + A 부터 K까지의 거리
• 플로이드 워셜
  • 모든 지점에 대해 최단거리를 구하는 상황(모든 점을 시작점이라 간주)
  • dist[i][j] = dist[i][k] + dist[k][j]