17주차 (4)

13. DFS와 BFS의 차이

DFS (깊이 우선 탐색)

• 방식: 한 방향으로 가능한 한 깊게 탐색한 후, 더 이상 갈 수 없으면 이전 단계로 돌아와서 다른 방향을 탐색합니다.
• 자료구조: 주로 스택(또는 재귀 호출 스택)을 사용합니다.
• 특징:
  • 재귀적으로 구현하기 쉽습니다.
  • 메모리 사용이 상대적으로 적을 수 있지만, 경우에 따라 최악의 경우 재귀 깊이가 너무 깊어질 수 있습니다.
  • 경로 탐색 문제(예: 미로 찾기)에서 한 방향으로 깊게 탐색해 빠르게 해답을 찾을 수 있는 경우 유리합니다.

BFS (너비 우선 탐색)

• 방식: 시작 노드에서부터 인접한 모든 노드를 먼저 탐색한 후, 그 다음 레벨로 넘어갑니다.
• 자료구조: 큐를 사용하여 현재 레벨의 모든 노드를 관리합니다.
• 특징:
  • 최단 경로 문제(예: 최단 거리 찾기)에 적합합니다.
  • 모든 노드를 레벨 순으로 방문하기 때문에 메모리 사용량이 많아질 수 있습니다.

14. Array와 LinkedList의 비교

Array (배열)

• 메모리 배치: 연속된 메모리 공간에 데이터를 저장합니다.
• 접근 속도: 인덱스를 사용하여 임의 접근(Random Access)이 O(1)로 빠릅니다.
• 삽입/삭제:
  • 배열의 중간에 삽입하거나 삭제할 경우, 나머지 요소들을 이동시켜야 하므로 O(n) 시간이 소요됩니다.
• 장점:
  • 고정된 크기 내에서 매우 빠른 검색 및 접근이 가능합니다.
• 단점:
  • 크기가 고정되어 있어, 동적 크기 변경이 어렵고 삽입/삭제가 비효율적입니다.

LinkedList (연결 리스트)

• 메모리 배치: 각 노드가 데이터와 다음 노드에 대한 포인터(주소)를 가지고, 메모리상에 산발적으로 분산되어 저장됩니다.
• 접근 속도: 인덱스 기반 접근이 불가능해, 원하는 요소에 접근하기 위해 처음부터 순차 탐색해야 하므로 O(n) 시간이 소요됩니다.
• 삽입/삭제:
  • 노드의 참조(포인터)만 조정하면 되므로, 중간 삽입/삭제가 O(1) 시간에 처리될 수 있습니다(단, 위치를 찾는 시간은 별도입니다).
• 장점:
  • 크기가 동적으로 변할 수 있으며, 삽입/삭제가 용이합니다.
• 단점:
  • 순차 접근 시 속도가 느리고, 추가적인 포인터 저장 공간이 필요합니다.