알고리즘/공부

면접 준비 - 알고리즘, 자료구조 개념 정리

이게될까 2024. 11. 22. 20:01
728x90
728x90

자료구조와 알고리즘은 컴퓨터 과학에서 가장 핵심적인 주제 중 하나로, 데이터를 효율적으로 저장하고 처리하며 문제를 해결하는 방법을 다룹니다. 아래에 이를 체계적으로 정리했습니다.

1. 자료구조 (Data Structures)

자료구조는 데이터를 체계적으로 저장하고 관리하는 방법입니다. 자료구조는 사용 목적과 데이터의 특성에 따라 선택되며, 주요 자료구조와 그 특징은 다음과 같습니다.

선형 자료구조 (Linear Data Structures)

  1. 배열 (Array)
    • 특징: 고정된 크기의 연속된 메모리 공간에 데이터를 저장.
    • 장점: 인덱스를 이용한 빠른 접근 (O(1)).
    • 단점: 크기 고정, 삽입/삭제가 비효율적 (O(n)).
  2. 연결 리스트 (Linked List)
    • 특징: 노드(Node)가 데이터와 다음 노드의 주소를 포함.
    • 장점: 동적 크기 조정 가능, 삽입/삭제가 빠름 (O(1)).
    • 단점: 랜덤 접근 불가, 추가적인 메모리 사용.
  3. 스택 (Stack)
    • 특징: LIFO(Last In, First Out) 방식.
    • 주요 연산: push, pop, peek.
    • 사용 사례: 함수 호출 스택, 괄호 유효성 검사.
  4. 큐 (Queue)
    • 특징: FIFO(First In, First Out) 방식.
    • 주요 변형:
      • 일반 큐: 단순 FIFO.
      • 우선순위 큐: 우선순위에 따라 처리.
      • 덱 (Deque): 양쪽 삽입/삭제 가능.

비선형 자료구조 (Non-linear Data Structures)

  1. 트리 (Tree)
    • 특징: 계층적 구조로, 노드와 간선으로 구성.
    • 주요 종류:
      • 이진 트리 (Binary Tree): 노드당 자식이 최대 2개.
      • 이진 탐색 트리 (BST): 왼쪽은 작은 값, 오른쪽은 큰 값.
      • 힙 (Heap): 최소/최대 우선순위 유지.
      • AVL 트리, 레드-블랙 트리: 균형 유지.
  2. 그래프 (Graph)
    • 특징: 노드(정점)와 간선(엣지)으로 구성된 네트워크 구조.
    • 분류:
      • 방향/무방향 그래프.
      • 가중치/비가중치 그래프.
    • 표현 방법: 인접 리스트, 인접 행렬.
  3. 집합과 해시 (Set & Hashing)
    • 집합(Set): 중복 없는 데이터 저장.
    • 해시 테이블(Hash Table): 키-값 쌍으로 데이터 저장, 평균적으로 검색, 삽입이 O(1).

2. 알고리즘 (Algorithms)

알고리즘은 문제를 해결하기 위한 절차나 규칙의 집합입니다. 알고리즘은 효율성과 정확성을 기준으로 평가되며, 다음과 같은 주요 유형이 있습니다.

정렬 알고리즘 (Sorting Algorithms)

  1. 버블 정렬 (Bubble Sort): 인접한 요소를 비교하여 교환. (O(n^2))
  2. 선택 정렬 (Selection Sort): 가장 작은 요소를 선택해 정렬. (O(n^2))
  3. 삽입 정렬 (Insertion Sort): 이미 정렬된 부분에 삽입. (O(n^2))
  4. 병합 정렬 (Merge Sort): 분할 정복 기법 사용. (O(n log n))
  5. 퀵 정렬 (Quick Sort): 피벗을 기준으로 분할. (O(n log n) 평균, 최악은 O(n^2))
  6. 힙 정렬 (Heap Sort): 힙 자료구조를 이용한 정렬. (O(n log n))

탐색 알고리즘 (Searching Algorithms)

  1. 선형 탐색 (Linear Search): 순차적으로 탐색. (O(n))
  2. 이진 탐색 (Binary Search): 정렬된 배열에서 탐색. (O(log n))
  3. DFS/BFS (그래프 탐색):
    • DFS (깊이 우선 탐색): 스택 또는 재귀 사용.
    • BFS (너비 우선 탐색): 큐 사용.

분할 정복 (Divide and Conquer)

  • 문제를 작은 부분으로 분할하고, 각 부분을 해결한 뒤 합침.
  • 예: 병합 정렬, 퀵 정렬.

동적 계획법 (Dynamic Programming)

  • 하위 문제의 해를 저장해 중복 계산 방지.
  • 예: 피보나치 수열, 최단 경로 (플로이드-워셜).

탐욕 알고리즘 (Greedy Algorithm)

  • 현재 상황에서 최선의 선택을 반복.
  • 예: 크루스칼/프림 알고리즘 (최소 신장 트리), 거스름돈 문제.

백트래킹 (Backtracking)

  • 해를 찾을 때 조건을 만족하지 않으면 되돌아감.
  • 예: N-Queens 문제, 미로 찾기.

그래프 알고리즘

  1. 최단 경로:
    • 다익스트라: 단일 출발점 최단 경로 (O(E + V log V)).
    • 벨만-포드: 음수 가중치 허용.
    • 플로이드-워셜: 모든 쌍 최단 경로.
  2. 최소 신장 트리:
    • 크루스칼: 간선 정렬 기반.
    • 프림: 정점 추가 기반.

3. 시간 복잡도와 공간 복잡도

  • 시간 복잡도: 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 증가하는지 나타냄.
    • Big-O 표기법: O(1), O(log n), O(n), O(n^2), O(2^n) 등.
  • 공간 복잡도: 알고리즘이 사용하는 메모리의 양.

4. 자료구조 & 알고리즘의 선택 기준

  1. 데이터 크기와 형태: 데이터가 정렬되어 있는가? 크기가 큰가?
  2. 연산의 빈도: 삽입, 삭제, 검색 중 어떤 연산이 자주 발생하는가?
  3. 제약 조건: 메모리 사용량, 실시간 처리 요구사항 등.

자료구조와 알고리즘을 깊이 이해하는 것은 효율적인 소프트웨어 설계와 문제 해결의 핵심입니다. 실전 문제를 풀어보면서 이 개념들을 자연스럽게 익혀 나가는 것이 중요합니다!

그럼 스택과 큐에서 데이터를 넣고, 뺄 때 어떻게 하는지 알려줘

스택과 큐에서 데이터를 넣고 빼는 방법은 각각의 자료구조의 동작 방식(LIFO, FIFO)에 따라 다릅니다. 아래에 각 자료구조에서 데이터를 삽입하고 삭제하는 과정을 설명합니다.

1. 스택 (Stack)

특징

  • LIFO (Last In, First Out): 나중에 들어온 데이터가 먼저 나감.
  • 데이터를 삽입/삭제할 수 있는 한쪽 끝(Top)만 사용.

주요 연산

  1. Push (삽입):
    • 스택의 Top 위치에 데이터를 추가.
    • 새로운 데이터가 Top이 됨.
  2. Pop (삭제):
    • Top 위치의 데이터를 제거.
    • 그 아래 있던 데이터가 새로운 Top이 됨.
  3. Peek (조회):
    • Top 위치의 데이터를 제거하지 않고 확인.

예제

# Python으로 구현
stack = []

# Push
stack.append(10)  # [10]
stack.append(20)  # [10, 20]
stack.append(30)  # [10, 20, 30]

# Pop
top_element = stack.pop()  # 30 (스택에서 제거됨), stack: [10, 20]

# Peek
current_top = stack[-1]  # 20 (스택에서 제거되지 않음)

2. 큐 (Queue)

특징

  • FIFO (First In, First Out): 먼저 들어온 데이터가 먼저 나감.
  • 데이터 삽입과 삭제가 양쪽 끝에서 일어남.
    • 삽입: 큐의 뒤쪽(Rear).
    • 삭제: 큐의 앞쪽(Front).

주요 연산

  1. Enqueue (삽입):
    • 큐의 Rear 위치에 데이터를 추가.
  2. Dequeue (삭제):
    • 큐의 Front 위치에서 데이터를 제거.
  3. Peek (조회):
    • Front 위치의 데이터를 제거하지 않고 확인.

예제

from collections import deque

# 큐 생성
queue = deque()

# Enqueue
queue.append(10)  # [10]
queue.append(20)  # [10, 20]
queue.append(30)  # [10, 20, 30]

# Dequeue
front_element = queue.popleft()  # 10 (큐에서 제거됨), queue: [20, 30]

# Peek
current_front = queue[0]  # 20 (큐에서 제거되지 않음)

3. 덱 (Deque)

큐와 스택의 장점을 결합한 구조로, 양쪽 끝에서 데이터를 삽입하고 삭제할 수 있음.

예제

from collections import deque

# 덱 생성
deque_structure = deque()

# 양쪽 삽입
deque_structure.append(10)        # 뒤쪽 삽입: [10]
deque_structure.appendleft(5)     # 앞쪽 삽입: [5, 10]

# 양쪽 삭제
rear_element = deque_structure.pop()      # 뒤쪽 삭제: 10, deque: [5]
front_element = deque_structure.popleft() # 앞쪽 삭제: 5, deque: []

스택과 큐의 차이점 요약

연산 스택 큐
삽입 위치 Top Rear
삭제 위치 Top Front
동작 방식 LIFO (Last In, First Out) FIFO (First In, First Out)

스택과 큐의 동작을 완벽히 이해하려면, 코드 구현과 함께 다양한 문제를 풀어보는 것이 효과적입니다. 😊

그럼 deque를 쓰지 stack나 que가 왜 따로 있는거야??

좋은 질문입니다! deque는 스택과 큐의 기능을 모두 지원하는 강력한 자료구조인데, 그렇다면 왜 스택과 큐가 별도로 존재할까요? 이를 이해하려면 스택, 큐, 그리고 deque의 설계 목적과 사용 사례를 살펴봐야 합니다.

1. 목적에 따른 단순성과 효율성

스택과 큐는 각각 특정 문제를 해결하기 위해 설계된 단순한 자료구조입니다.

  • 스택 (Stack):
    • LIFO(Last In, First Out) 작업만 필요할 때 사용.
    • 예: 함수 호출 스택, DFS(깊이 우선 탐색), 괄호 유효성 검사.
    • 불필요한 기능을 배제하여 효율적으로 설계되었습니다.
  • 큐 (Queue):
    • FIFO(First In, First Out) 작업만 필요할 때 사용.
    • 예: BFS(너비 우선 탐색), 작업 대기열, 프로세스 스케줄링.
    • 큐는 삽입과 삭제 위치가 고정되어 있어, 의도를 명확히 표현할 수 있습니다.
  • Deque:
    • 양쪽 삽입/삭제가 모두 가능한 범용 자료구조입니다.
    • 더 유연하지만, 특정 기능만 필요할 때는 복잡도와 메모리 사용 측면에서 비효율적일 수 있습니다.

2. 명확성과 가독성

  • 명확한 의도 전달: 스택과 큐를 사용하면 자료구조의 동작 방식을 명확히 표현할 수 있습니다.
    • 예: "이 프로그램에서는 데이터를 LIFO 방식으로 처리한다" → 스택 사용.
    • 예: "이 작업은 FIFO 방식으로 실행해야 한다" → 큐 사용.
    • deque는 모든 동작을 지원하지만, 사용자의 의도를 명확히 드러내지 못할 수 있습니다.

3. 메모리와 성능 최적화

  • 스택과 큐는 단순히 삽입/삭제 작업만 수행하기 때문에, 구현이 간단하며 더 가볍고 빠를 수 있습니다.
  • 반면, deque는 양쪽 삽입/삭제를 지원하기 위해 더 많은 기능과 추가적인 메모리를 필요로 할 수 있습니다.

4. 역사적인 이유

  • 스택과 큐는 컴퓨터 과학의 초창기부터 사용된 기본 자료구조입니다.
  • 다양한 알고리즘과 문제 해결 방식이 스택과 큐를 기반으로 설계되었습니다.
  • 반면 deque는 스택과 큐보다 범용적인 사용 사례가 늘어난 후에 생긴 자료구조입니다.

5. 특정 라이브러리/언어의 최적화

  • 일부 언어에서는 스택과 큐를 별도로 최적화해 제공하며, deque보다 효율적일 수 있습니다.
  • 예:
    • Python의 리스트를 스택으로 사용할 때, append와 pop은 매우 빠릅니다.
    • deque는 양쪽 작업을 지원하기 위해 더 복잡한 내부 구현을 가집니다.

정리

스택과 큐는 단순하고 명확한 작업을 위해 설계된 자료구조로, 특정 시나리오에서 deque보다 효율적이고 사용 의도를 잘 드러냅니다.
반면, deque는 더 유연하고 범용적이지만, 항상 최선의 선택은 아닙니다.

따라서 필요한 작업에 따라 적절한 자료구조를 선택하는 것이 중요합니다! 😊

아 연결 리스트로 구현되면 deque는 앞 뒤로 가는 주소 정보를 모두 가지고 있어야 하는구나?

정확합니다! deque(double-ended queue)는 양쪽 끝에서 삽입과 삭제가 가능하기 때문에, 이를 효율적으로 구현하기 위해 이중 연결 리스트(doubly linked list)와 유사한 구조를 사용합니다. 이를 자세히 살펴보겠습니다.

1. deque의 구현 방식

deque는 양쪽에서 삽입과 삭제를 O(1) 시간 안에 처리하기 위해 보통 이중 연결 리스트로 구현됩니다.

이중 연결 리스트의 특징

  • 각 노드가 다음 노드와 이전 노드에 대한 포인터를 가짐:
    • 다음 노드(next): 노드가 연결 리스트의 뒤쪽으로 연결될 때 사용.
    • 이전 노드(prev): 노드가 연결 리스트의 앞쪽으로 연결될 때 사용.

구조

  • deque는 양쪽에서 삽입과 삭제를 빠르게 처리해야 하므로:
    • Front 포인터: 리스트의 첫 번째 노드를 가리킴.
    • Rear 포인터: 리스트의 마지막 노드를 가리킴.

장점

  • 앞뒤 양쪽에서 삽입/삭제가 모두 O(1)로 수행 가능.
  • 배열 기반 큐(일반적으로 고정 크기)와 달리, 크기가 동적으로 조정 가능.

2. 삽입과 삭제 동작

deque에서의 동작은 이중 연결 리스트의 구조 덕분에 매우 효율적입니다.

삽입 (Insertion)

  1. 앞쪽 삽입 (appendleft):
    • 새로운 노드의 next를 현재 Front로 설정.
    • 현재 Front의 prev를 새로운 노드로 설정.
    • 새로운 노드를 Front로 업데이트.
  2. 뒤쪽 삽입 (append):
    • 새로운 노드의 prev를 현재 Rear로 설정.
    • 현재 Rear의 next를 새로운 노드로 설정.
    • 새로운 노드를 Rear로 업데이트.

삭제 (Deletion)

  1. 앞쪽 삭제 (popleft):
    • Front 노드를 제거.
    • 다음 노드를 Front로 업데이트.
    • 새 Front의 prev를 None으로 설정.
  2. 뒤쪽 삭제 (pop):
    • Rear 노드를 제거.
    • 이전 노드를 Rear로 업데이트.
    • 새 Rear의 next를 None으로 설정.

3. 양방향 연결 리스트의 장점

  • 유연한 데이터 조작: 양쪽 끝에서 데이터를 삽입/삭제 가능.
  • 크기 제한 없음: 동적 메모리 할당으로 구현되어 크기 제한이 없음.
  • 효율적인 시간 복잡도:
    • 배열 기반 큐에서 앞쪽 삽입/삭제는 O(n) 시간(모든 요소를 이동) 소요.
    • 이중 연결 리스트는 O(1) 시간에 가능.

4. Python의 deque는 어떻게 구현될까?

Python의 collections.deque는 내부적으로 이중 연결 리스트 기반으로 설계되어 있습니다. 하지만 메모리 및 속도를 최적화하기 위해 추가적인 최적화가 포함되어 있을 수 있습니다.

from collections import deque

# deque 생성
dq = deque()

# 앞뒤 삽입
dq.append(10)        # 뒤쪽 삽입: [10]
dq.appendleft(5)     # 앞쪽 삽입: [5, 10]

# 앞뒤 삭제
dq.pop()             # 뒤쪽 삭제: 10, deque: [5]
dq.popleft()         # 앞쪽 삭제: 5, deque: []

5. deque vs 배열 기반 자료구조

배열 기반 큐와의 차이점

  • 배열 기반 큐는 고정 크기일 경우, 크기 초과 시 데이터 이동 또는 재할당 필요.
  • deque는 이중 연결 리스트를 사용해 삽입/삭제 시 데이터 이동이 필요 없음.

결론적으로, deque는 이중 연결 리스트와 같은 구조를 사용하여 양쪽 끝에서 효율적인 연산을 제공합니다. 이중 연결 리스트의 구조를 이해하면 deque의 효율성에 대한 이유를 자연스럽게 알 수 있습니다! 😊

그런데 이런 연결 리스트 구조는 배열처럼 5번째에 한번에 접근한다 이런 것이 불가능하지?

맞습니다! 연결 리스트(Linked List) 구조에서는 배열처럼 임의의 인덱스에 한 번에 접근하는 것이 불가능합니다. 이는 연결 리스트와 배열의 가장 큰 차이점 중 하나입니다.

왜 연결 리스트는 임의 접근이 어려운가?

연결 리스트는 데이터를 노드(Node) 라는 단위로 저장하며, 각 노드는 데이터와 다음 노드(혹은 이전 노드)에 대한 포인터를 가지고 있습니다.

  • 연결 리스트에서 특정 위치에 접근하려면 처음 노드부터 차례대로 따라가야 합니다.
  • 예를 들어, 5번째 노드에 접근하려면 첫 번째 노드부터 시작해서 4번의 이동이 필요합니다.

시간 복잡도

  • 임의 접근(Array): 배열은 메모리가 연속적으로 배치되어 있어, 인덱스만으로 한 번에 접근 가능합니다. → O(1)
  • 임의 접근(Linked List): 특정 노드를 찾으려면 헤드(Head)부터 하나씩 순회해야 합니다. → O(n)

연결 리스트의 구조적 한계

1. 순차적 접근 (Sequential Access)

  • 연결 리스트는 포인터로 연결된 노드들의 집합이므로 연속적인 메모리 공간이 보장되지 않습니다.
  • 따라서 임의의 인덱스 접근(예: array[5])을 지원하지 못하고, 노드를 순차적으로 탐색해야 합니다.

2. 위치에 따른 접근 시간

  • 배열(Array):
    • 데이터가 연속된 메모리에 저장되어, 특정 인덱스의 메모리 주소를 바로 계산 가능.
    • 예: 배열의 시작 주소 + (인덱스 × 데이터 크기)로 O(1) 접근.
  • 연결 리스트(Linked List):
    • 각 노드가 포인터로 연결되어 있어, 다음 노드의 주소를 따라가야만 원하는 데이터를 찾을 수 있음.
    • 예: 5번째 노드를 찾으려면 4번의 포인터 연산이 필요.

연결 리스트의 장점

임의 접근은 어렵지만, 연결 리스트가 배열보다 유리한 점도 있습니다:

1. 동적 메모리 할당

  • 배열은 크기가 고정되어 있어 초기에 필요한 크기를 지정해야 하지만, 연결 리스트는 필요할 때마다 동적으로 메모리를 할당하므로 크기에 제한이 없습니다.

2. 효율적인 삽입/삭제

  • 배열에서 중간에 삽입/삭제를 하면 데이터를 이동해야 하므로 O(n) 시간이 걸립니다.
  • 연결 리스트는 노드의 포인터를 변경하는 것으로 삽입/삭제가 가능하므로 O(1) 시간이 소요됩니다 (삽입/삭제 위치가 주어진 경우).

해결 방법: 배열과 연결 리스트의 혼합

연결 리스트의 순차 접근 문제를 해결하기 위해 배열과 연결 리스트의 장점을 결합한 자료구조도 존재합니다:

1. Skip List

  • 연결 리스트에 중간 레벨의 포인터를 추가하여 빠르게 특정 노드를 탐색할 수 있도록 한 자료구조.
  • 탐색 속도: O(log n).

2. 해시 테이블(Hash Table)과 연결 리스트

  • 연결 리스트에 해시 테이블을 결합하여 인덱스를 빠르게 참조하는 방식.
  • 하지만 이 방법은 더 많은 메모리를 필요로 합니다.

정리

연결 리스트는 임의 접근에는 부적합하지만, 동적 크기 조정과 효율적인 삽입/삭제가 필요한 상황에서 유리합니다.
만약 빠른 인덱스 접근이 필요한 작업이라면, 배열(Array)이나 다른 자료구조를 선택하는 것이 더 적합합니다.
자료구조를 선택할 때는 작업의 우선순위(삽입, 삭제 vs 탐색) 를 기준으로 고려해야 합니다. 😊

삽입, 병합, 퀵, 힙 정렬에 대해 자세하게 기억이 나지 않는데 한번 정리해주라

정렬 알고리즘은 데이터를 순서대로 정렬하기 위해 사용됩니다. 여기에서 요청한 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬에 대해 자세히 정리해드리겠습니다.

1. 삽입 정렬 (Insertion Sort)

개념

  • 데이터를 한 번에 하나씩 가져와 이미 정렬된 부분에 삽입하며 정렬을 확장하는 방식.
  • 작은 데이터 세트에서 유리하고, 안정 정렬(Stable Sort)입니다.

작동 원리

  1. 첫 번째 원소는 이미 정렬된 상태로 간주.
  2. 두 번째 원소부터 시작하여 정렬된 부분에 알맞은 위치를 찾아 삽입.
  3. 이를 반복하여 전체 배열을 정렬.

시간 복잡도

  • 최악: O(n²) (거의 정렬되지 않은 경우)
  • 최선: O(n) (이미 정렬된 경우)
  • 평균: O(n²)

공간 복잡도

  • O(1) (제자리 정렬)

예제

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Example
print(insertion_sort([5, 3, 4, 1, 2]))
# Output: [1, 2, 3, 4, 5]

2. 병합 정렬 (Merge Sort)

개념

  • 분할 정복(Divide and Conquer) 알고리즘의 대표적인 예.
  • 배열을 절반으로 나누어 각각 정렬한 뒤, 정렬된 두 부분을 병합하여 최종 정렬.

작동 원리

  1. 배열을 절반으로 계속 나눕니다.
  2. 나눠진 부분이 크기가 1이 될 때까지 재귀적으로 호출.
  3. 두 개의 정렬된 배열을 병합하면서 정렬.

시간 복잡도

  • 항상 O(n log n)

공간 복잡도

  • O(n) (추가 배열이 필요)

예제

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Example
print(merge_sort([5, 3, 4, 1, 2]))
# Output: [1, 2, 3, 4, 5]

3. 퀵 정렬 (Quick Sort)

개념

  • 분할 정복 알고리즘의 또 다른 대표적인 예.
  • 배열에서 피벗(pivot) 을 선택하고, 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할.
  • 분할된 부분을 재귀적으로 정렬.

작동 원리

  1. 피벗을 선택합니다 (일반적으로 첫 번째 원소, 마지막 원소, 혹은 중간값).
  2. 배열을 피벗보다 작은 부분과 큰 부분으로 나눕니다.
  3. 두 부분을 재귀적으로 정렬.

시간 복잡도

  • 최악: O(n²) (피벗이 비효율적으로 선택될 경우, 예: 이미 정렬된 경우)
  • 최선/평균: O(n log n)

공간 복잡도

  • O(log n) (재귀 호출 스택)

예제

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# Example
print(quick_sort([5, 3, 4, 1, 2]))
# Output: [1, 2, 3, 4, 5]

4. 힙 정렬 (Heap Sort)

개념

  • 힙 자료구조를 활용한 정렬 알고리즘.
  • 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 구성한 뒤, 힙에서 루트 노드를 제거하며 정렬.

작동 원리

  1. 주어진 배열을 힙 구조로 변환 (Heapify).
  2. 힙의 루트(최대/최소값)를 제거하여 정렬된 배열에 추가.
  3. 힙 크기를 줄이고, 힙 속성을 유지하며 반복.

시간 복잡도

  • O(n log n) (힙 구성: O(n), 재정렬: O(log n) * n)

공간 복잡도

  • O(1) (제자리 정렬)

예제

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr

# Example
print(heap_sort([5, 3, 4, 1, 2]))
# Output: [1, 2, 3, 4, 5]

정리: 비교

정렬 알고리즘 시간 복잡도
(최악)		 시간 복잡도
(평균)		 공간 복잡도 특징
삽입 정렬 O(n²) O(n²) O(1) 작은 데이터나 거의 정렬된 데이터에 적합. 안정 정렬.
병합 정렬 O(n log n) O(n log n) O(n) 안정 정렬. 추가 공간 필요. 대규모 데이터 정렬에 적합.
퀵 정렬 O(n²) O(n log n) O(log n) 불안정 정렬. 평균적으로 매우 빠름. 피벗 선택에 따라 성능 차이 큼.
힙 정렬 O(n log n) O(n log n) O(1) 불안정 정렬. 추가 메모리 필요 없음. 비교 기반 정렬 중 효율적.

위 내용을 바탕으로 각 정렬 알고리즘의 특성을 이해하고, 상황에 맞는 알고리즘을 선택해 사용하는 것이 중요합니다! 😊

힙 정렬을 보는데 힙 자료구조에 대해 기억이 잘 나지 않아 자세하게 설명해줘

힙(Heap)은 완전 이진 트리(Complete Binary Tree) 를 기반으로 한 자료구조로, 주로 최대값/최소값을 빠르게 찾거나 정렬하는 데 사용됩니다. 힙 정렬, 우선순위 큐(Priority Queue) 등의 구현에 필수적입니다. 아래에 힙 자료구조를 자세히 정리해드리겠습니다.

1. 힙(Heap)의 정의

  • 완전 이진 트리: 모든 레벨이 꽉 차 있거나, 마지막 레벨만 왼쪽부터 채워진 트리.
  • 힙 속성: 부모 노드와 자식 노드 간의 관계가 특정 규칙을 만족.
    • 최대 힙(Max Heap): 부모 노드 ≥ 자식 노드.
    • 최소 힙(Min Heap): 부모 노드 ≤ 자식 노드.

힙의 특징

  1. 완전 이진 트리이므로 배열로 표현 가능.
  2. 특정 값(최대값 또는 최소값)을 O(1) 시간에 가져올 수 있음.
  3. 삽입/삭제 시 힙 속성을 유지하기 위해 O(log n) 시간이 소요됨.

2. 힙의 종류

최대 힙 (Max Heap)

  • 부모 노드의 값이 자식 노드의 값보다 크거나 같음.
  • 루트 노드에 항상 가장 큰 값이 위치.

최소 힙 (Min Heap)

  • 부모 노드의 값이 자식 노드의 값보다 작거나 같음.
  • 루트 노드에 항상 가장 작은 값이 위치.

3. 힙의 구현

배열 기반 힙 표현

힙은 완전 이진 트리이므로 배열로 효율적으로 표현 가능합니다.

  • 인덱스 규칙:
    • 부모 노드: arr[i].
    • 왼쪽 자식: arr[2 * i + 1].
    • 오른쪽 자식: arr[2 * i + 2].
    • 부모 노드: arr[(i - 1) // 2].

힙 연산

  1. 삽입 (Insert):
    • 새 값을 힙의 마지막 위치에 추가.
    • 부모와 비교하며 위로 이동(Heapify-Up).
    • O(log n).
  2. 삭제 (Delete):
    • 루트 노드(최대값/최소값)를 제거.
    • 힙의 마지막 값을 루트로 이동.
    • 자식과 비교하며 아래로 이동(Heapify-Down).
    • O(log n).
  3. 힙 정렬 (Heap Sort):
    • 최대 힙을 구성한 뒤, 루트를 반복적으로 제거하여 정렬.

4. 힙 연산의 동작 과정

1) 삽입 (Insert)

새로운 값을 힙에 삽입한 후, 힙 속성을 유지하기 위해 부모와 값을 교환하며 위로 올라갑니다.

예제 (최대 힙 삽입):

배열: [50, 30, 40, 10, 5, 20]
삽입 값: 35

  1. 35를 마지막에 삽입: [50, 30, 40, 10, 5, 20, 35].
  2. 부모(40)와 비교 → 교환: [50, 30, 35, 10, 5, 20, 40].
  3. 루트까지 힙 속성이 유지되면 종료.

2) 삭제 (Delete)

루트 노드를 제거한 뒤, 마지막 노드를 루트로 이동하고 힙 속성을 유지합니다.

예제 (최대 힙 삭제):

배열: [50, 30, 40, 10, 5, 20].
삭제 값: 50 (루트)

  1. 루트(50)를 제거하고 마지막 노드(20)를 루트로 이동: [20, 30, 40, 10, 5].
  2. 자식(40)과 비교 → 교환: [40, 30, 20, 10, 5].
  3. 힙 속성이 유지되면 종료.

5. Python으로 힙 구현

1) 최대 힙

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def build_max_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

def heap_sort(arr):
    n = len(arr)
    build_max_heap(arr)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

# Example
arr = [5, 3, 8, 4, 1, 2]
heap_sort(arr)
print(arr)  # Output: [1, 2, 3, 4, 5, 8]

2) 최소 힙 (Python 내장 모듈 활용)

Python의 heapq 모듈은 기본적으로 최소 힙을 제공합니다.

import heapq

# 힙 생성
heap = []
heapq.heappush(heap, 10)  # [10]
heapq.heappush(heap, 5)   # [5, 10]
heapq.heappush(heap, 20)  # [5, 10, 20]

# 최소값 추출
min_value = heapq.heappop(heap)  # 5
print(min_value, heap)  # Output: 5 [10, 20]

6. 힙의 응용

  1. 우선순위 큐:
    • 작업 우선순위가 높은 데이터를 빠르게 처리.
    • 최소/최대 힙을 활용.
  2. 힙 정렬:
    • 힙 구조를 기반으로 한 정렬 알고리즘.
    • O(n log n) 성능.
  3. K번째 최소값/최대값 찾기:
    • 힙을 이용해 효율적으로 K번째 값을 찾음.

정리

  • 힙은 완전 이진 트리로, 특정 조건(최대값/최소값)을 효율적으로 관리합니다.
  • 삽입/삭제는 O(log n)로 빠르게 수행되며, 우선순위 큐와 정렬 등에 자주 사용됩니다.
  • Python에서는 heapq 모듈을 사용해 간단히 구현할 수 있습니다.
    힙을 잘 이해하면, 다양한 응용 분야에서 강력한 도구가 됩니다! 😊

그럼 이제 DFS, BFS에 대해 설명해줘

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프 탐색 알고리즘으로, 노드와 간선을 탐색하는 데 사용됩니다. 각 알고리즘은 특정 목적과 데이터 구조에 따라 적합하며, 아래에 두 알고리즘을 비교 및 자세히 설명하겠습니다.

1. DFS (Depth First Search, 깊이 우선 탐색)

개념

DFS는 그래프에서 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색하는 방식입니다. 즉, 현재 노드의 모든 자식을 방문한 후에 다음 노드로 이동합니다.

작동 원리

  1. 시작 노드에서 출발.
  2. 한 노드의 자식 노드를 탐색(방문)하고, 방문한 노드는 스택에 저장.
  3. 더 이상 방문할 노드가 없으면 스택에서 이전 노드를 꺼내 탐색.

시간 복잡도

  • O(V + E): V는 노드 수, E는 간선 수.

공간 복잡도

  • O(V): 재귀 호출 스택 또는 명시적 스택에 의해 메모리 사용.

DFS의 구현

  1. 재귀 방식 
    def dfs_recursive(graph, node, visited):
 visited.add(node)
 print(node, end=' ')
 for neighbor in graph[node]:
     if neighbor not in visited:
         dfs_recursive(graph, neighbor, visited)

Example

graph = {
1: [2, 3],
2: [4, 5],
3: [],
4: [],
5: []
}
visited = set()
dfs_recursive(graph, 1, visited)

Output: 1 2 4 5 3


2. **스택 방식**
```python
def dfs_stack(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            stack.extend(graph[node])  # 자식을 추가

2. BFS (Breadth First Search, 너비 우선 탐색)

개념

BFS는 그래프에서 특정 노드와 가까운 노드부터 탐색합니다. 즉, 현재 노드의 모든 이웃 노드를 탐색한 후에 다음 레벨로 이동합니다.

작동 원리

  1. 시작 노드에서 출발.
  2. 현재 노드와 연결된 모든 노드를 큐에 삽입.
  3. 큐에서 노드를 꺼내면서 탐색.

시간 복잡도

  • O(V + E): V는 노드 수, E는 간선 수.

공간 복잡도

  • O(V): 큐에 의해 메모리 사용.

BFS의 구현

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            queue.extend(graph[node])  # 자식을 추가

# Example
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [],
    4: [],
    5: []
}
bfs(graph, 1)
# Output: 1 2 3 4 5

3. DFS와 BFS의 차이점

특징 DFS BFS
탐색 방식 깊이 우선, 한 경로를 끝까지 탐색. 너비 우선, 가까운 노드부터 탐색.
구현 방식 재귀(스택), 스택 자료구조 사용. 큐 자료구조 사용.
사용 사례 경로 찾기, 게임 맵 탐색. 최단 경로 탐색, 가까운 노드 탐색.
시간 복잡도 O(V + E) O(V + E)
공간 복잡도 O(V) (스택 사용) O(V) (큐 사용)

4. DFS와 BFS의 응용 사례

DFS 응용 사례

  1. 경로 찾기(Path Finding):
    • 그래프에서 시작점에서 목표점까지의 경로를 찾을 때 유용.
  2. 사이클 탐지:
    • 무방향 그래프나 방향 그래프에서 사이클이 존재하는지 확인.
  3. 게임 및 퍼즐 탐색:
    • 미로 탐색, 체스 나이트 이동, 퍼즐 탐색 등.

BFS 응용 사례

  1. 최단 경로 찾기(Shortest Path):
    • 가중치가 없는 그래프에서 두 노드 간 최단 경로 탐색.
  2. 웹 크롤링(Web Crawling):
    • 인터넷에서 연결된 페이지를 탐색.
  3. 사회적 거리 계산:
    • 그래프 형태의 데이터에서 연결된 노드 간 거리 계산.

5. DFS와 BFS 선택 기준

  • 최단 경로가 필요할 때: BFS (가중치가 없는 경우).
  • 전체 그래프 탐색 또는 특정 패턴 찾기: DFS.
  • 노드의 수가 많고 간선이 적은 경우: DFS.
  • 노드와 간선이 많아 메모리가 중요한 경우: BFS (큐 크기를 조정 가능).

DFS와 BFS는 그래프 탐색의 기본으로, 문제의 성격에 따라 적절히 선택해야 합니다. 위의 구현 예제를 통해 직접 연습해보면 이해를 더 깊게 할 수 있습니다! 😊

그럼 그래프 알고리즘을 좀 더 자세히 설명하면서 최단 경로와 최소 신장 트리에 대해 설명해줘

그래프 알고리즘은 그래프의 구조를 탐색하거나 최적화 문제를 해결하는 데 사용됩니다. 아래에서는 최단 경로와 최소 신장 트리 문제를 중심으로 주요 알고리즘을 설명하겠습니다.

1. 최단 경로 (Shortest Path)

그래프에서 두 노드 간의 가장 짧은 경로를 찾는 문제입니다.

1.1. 다익스트라 알고리즘 (Dijkstra's Algorithm)

  • 개념:
    • 가중치가 있는 그래프에서 단일 출발점에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘.
    • 음수 가중치가 없는 경우에만 사용 가능.
  • 작동 원리:
    1. 시작 노드의 거리를 0으로 설정하고, 다른 모든 노드는 ∞로 초기화.
    2. 방문하지 않은 노드 중 현재 최단 거리를 가진 노드를 선택.
    3. 선택한 노드의 이웃 노드로 가는 거리를 계산하고, 최단 거리 테이블을 갱신.
    4. 모든 노드를 방문할 때까지 반복.
  • 시간 복잡도:
    • O((V + E) log V) (우선순위 큐 사용 시).
  • 예제 코드: 
    import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]  # (거리, 노드)

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# Example
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 6},
    'C': {'A': 4, 'B': 2, 'D': 3},
    'D': {'B': 6, 'C': 3}
}
print(dijkstra(graph, 'A'))
# Output: {'A': 0, 'B': 1, 'C': 3, 'D': 6}
    1.2. 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
    • 개념:
      • 가중치가 있는 그래프에서 단일 출발점에서 다른 모든 노드까지의 최단 경로를 찾음.
      • 음수 가중치를 허용.
      • 음수 사이클을 감지할 수 있음.
    • 작동 원리:
      1. 모든 간선을 V-1번 반복하며 거리 값을 갱신.
      2. V번째 반복에서 갱신이 발생하면 음수 사이클 존재.
    • 시간 복잡도:
      • O(VE).
    • 예제 코드:
def bellman_ford(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight

    # 음수 사이클 체크
    for node in graph:
        for neighbor, weight in graph[node].items():
            if distances[node] + weight < distances[neighbor]:
                raise ValueError("Graph contains a negative-weight cycle")

    return distances

1.3. 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

  • 개념:
    • 모든 쌍 최단 경로를 찾는 알고리즘.
    • 동적 계획법을 사용하여 그래프의 모든 노드 쌍 간의 최단 경로를 계산.
    • 음수 가중치는 허용하지만, 음수 사이클은 허용하지 않음.
  • 작동 원리:
    1. 모든 노드 쌍의 초기 거리를 인접 행렬로 표현.
    2. 각 노드를 중간 노드로 고려하며 거리 값을 갱신.
  • 시간 복잡도:
    • O(V³).
  • 예제 코드:
def floyd_warshall(graph):
    nodes = list(graph.keys())
    dist = {node: {node2: float('inf') for node2 in nodes} for node in nodes}
    for node in nodes:
        dist[node][node] = 0
        for neighbor, weight in graph[node].items():
            dist[node][neighbor] = weight

    for k in nodes:
        for i in nodes:
            for j in nodes:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

2. 최소 신장 트리 (Minimum Spanning Tree, MST)

최소 신장 트리는 그래프의 모든 노드를 연결하는 간선 집합 중, 가중치의 합이 최소인 트리를 찾는 문제입니다. 그래프가 연결되어 있어야 합니다.

2.1. 크루스칼 알고리즘 (Kruskal's Algorithm)

  • 개념:
    • 간선을 가중치 기준으로 정렬한 뒤, 가장 작은 간선부터 선택하여 트리를 구성.
    • 사이클이 발생하지 않도록 확인.
  • 작동 원리:
    1. 모든 간선을 가중치 기준으로 정렬.
    2. 작은 간선부터 추가하며 사이클이 발생하지 않으면 선택.
    3. 선택한 간선이 (V-1)개가 되면 종료.
  • 시간 복잡도:
    • O(E log E) (간선 정렬 시간).
  • 예제 코드:
def kruskal(edges, num_nodes):
    edges.sort(key=lambda x: x[2])  # (노드1, 노드2, 가중치) 기준 정렬
    parent = list(range(num_nodes))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x != root_y:
            parent[root_y] = root_x

    mst = []
    for u, v, weight in edges:
        if find(u) != find(v):
            union(u, v)
            mst.append((u, v, weight))

    return mst

2.2. 프림 알고리즘 (Prim's Algorithm)

  • 개념:
    • 한 노드에서 출발하여 인접한 노드 중 가중치가 가장 작은 간선을 선택.
    • 선택된 노드의 인접 노드를 추가하며 트리를 확장.
  • 작동 원리:
    1. 임의의 노드를 시작점으로 선택.
    2. 방문하지 않은 노드와 방문한 노드를 연결하는 최소 가중치 간선을 선택.
    3. 모든 노드를 방문할 때까지 반복.
  • 시간 복잡도:
    • O(V²) (인접 행렬 사용).
    • O(E log V) (우선순위 큐 사용).
  • 예제 코드: 
    import heapq

def prim(graph, start):
    mst = []
    visited = set()
    min_heap = [(0, start, None)]  # (가중치, 현재 노드, 이전 노드)

    while min_heap:
        weight, current, prev = heapq.heappop(min_heap)
        if current in visited:
            continue
        visited.add(current)
        if prev is not None:
            mst.append((prev, current, weight))

        for neighbor, w in graph[current].items():
            if neighbor not in visited:
                heapq.heappush(min_heap, (w, neighbor, current))

    return mst

3. 최단 경로 vs 최소 신장 트리

특징 최단 경로 최소 신장 트리 
목적 두 노드 간의 최단 거리 그래프를 연결하는 최소 가중치 트리
결과 경로 트리
음수 가중치 벨만-포드, 플로이드-워셜 가능 음수 가중치는 문제 없음
대표 알고리즘 다익스트라, 벨만-포드, 플로이드-워셜 크루스칼, 프림

이 알고리즘들을 이해하고 구현하면 그래프와 관련된 많은 문제를 해결할 수 있습니다. 😊  

 

그럼 이제 비선형 자료구조인 트리와 그래프에 대해 자세하게 설명해줘

비선형 자료구조인 트리(Tree)와 그래프(Graph)는 계층적 및 네트워크형 데이터를 표현하고 처리하는 데 사용됩니다. 이들은 다양한 알고리즘과 응용에서 핵심적인 역할을 하며, 각각의 특징과 활용 방식이 다릅니다. 아래에 이를 체계적으로 정리하겠습니다.

1. 트리 (Tree)

1.1. 개념

  • 트리는 노드(Node)와 간선(Edge)으로 구성된 계층적 자료구조입니다.
  • 하나의 루트(Root) 노드에서 시작하여 사이클이 없는 방향성 그래프(DAG, Directed Acyclic Graph)입니다.

1.2. 트리의 특징

  1. 루트 노드: 트리의 시작점.
  2. 부모/자식 관계: 각 노드는 부모와 자식을 가질 수 있음.
  3. 간선(Edge): 노드 간의 연결.
  4. 깊이(Depth): 루트에서 특정 노드까지의 경로 길이.
  5. 높이(Height): 트리에서 가장 깊은 경로의 길이.
  6. 단말 노드(Leaf): 자식이 없는 노드.

1.3. 트리의 종류

  1. 일반 트리 (General Tree):
    • 각 노드가 여러 자식을 가질 수 있음.
  2. 이진 트리 (Binary Tree):
    • 각 노드가 최대 두 개의 자식을 가질 수 있음.
  3. 이진 탐색 트리 (BST, Binary Search Tree):
    • 왼쪽 자식: 부모보다 작은 값.
    • 오른쪽 자식: 부모보다 큰 값.
  4. 균형 이진 트리 (Balanced Binary Tree):
    • AVL 트리, 레드-블랙 트리와 같이 균형을 유지하는 이진 탐색 트리.
  5. 힙 트리 (Heap):
    • 최대 힙(Max Heap) 또는 최소 힙(Min Heap).
  6. 이진 힙 트리:
    • 완전 이진 트리 형태를 가지며, 힙 속성을 만족.
  7. 트라이(Trie):
    • 문자열 검색에 사용되는 특수 트리.

1.4. 트리의 순회

트리는 순회를 통해 데이터를 방문합니다.

1) 깊이 우선 탐색 (DFS)

  • 전위 순회 (Preorder): 부모 → 왼쪽 자식 → 오른쪽 자식.
  • 중위 순회 (Inorder): 왼쪽 자식 → 부모 → 오른쪽 자식.
  • 후위 순회 (Postorder): 왼쪽 자식 → 오른쪽 자식 → 부모.
# 전위 순회
def preorder(node):
    if node:
        print(node.data, end=' ')
        preorder(node.left)
        preorder(node.right)

2) 너비 우선 탐색 (BFS)

  • 큐(Queue)를 이용하여 트리의 레벨 순서대로 방문.
from collections import deque

def bfs(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.data, end=' ')
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

1.5. 트리의 응용

  1. 이진 탐색:
    • 정렬된 데이터를 빠르게 탐색.
  2. 우선순위 큐:
    • 힙 자료구조를 이용.
  3. 문자열 검색:
    • 트라이(Trie)를 사용.
  4. 파일 시스템:
    • 디렉토리 구조 표현.

2. 그래프 (Graph)

2.1. 개념

  • 그래프는 노드(Node) 와 간선(Edge) 의 집합으로 이루어진 자료구조.
  • 네트워크와 연결 관계를 표현.

2.2. 그래프의 특징

  1. 노드(Vertex): 데이터를 저장.
  2. 간선(Edge): 노드 간의 연결을 나타냄.
  3. 방향성:
    • 방향 그래프 (Directed Graph): 간선에 방향이 있음.
    • 무방향 그래프 (Undirected Graph): 간선에 방향이 없음.
  4. 가중치:
    • 간선에 값(가중치)이 부여된 그래프.
  5. 밀도:
    • 희소 그래프 (Sparse Graph): 간선이 적은 그래프.
    • 밀집 그래프 (Dense Graph): 간선이 많은 그래프.

2.3. 그래프의 표현

  1. 인접 행렬 (Adjacency Matrix):
    • 2D 배열로 노드 간의 연결을 저장.
    • 간선 존재: 1, 없음: 0.
    • 공간 복잡도: O(V²).
  2. 인접 리스트 (Adjacency List):
    • 각 노드에 연결된 노드들의 리스트를 저장.
    • 공간 복잡도: O(V + E).
  3. 간선 리스트 (Edge List):
    • 간선 자체를 리스트로 표현. (e.g., [(u, v), (v, w)])

2.4. 그래프 탐색

  1. DFS (Depth First Search):
    • 스택을 사용해 깊이 우선 탐색.
    • 구현: 재귀 또는 명시적 스택.
  2. BFS (Breadth First Search):
    • 큐를 사용해 너비 우선 탐색.

2.5. 그래프 알고리즘

1) 최단 경로 알고리즘

  • 다익스트라 알고리즘: 단일 출발점 최단 경로, 음수 가중치 불가능.
  • 벨만-포드 알고리즘: 음수 가중치 허용.
  • 플로이드-워셜 알고리즘: 모든 쌍 최단 경로.

2) 최소 신장 트리 알고리즘

  • 크루스칼 알고리즘: 간선을 정렬하여 MST를 생성.
  • 프림 알고리즘: 노드를 중심으로 MST를 확장.

3) 위상 정렬 (Topological Sort)

  • 방향 그래프에서 사이클이 없는 경우 노드의 순서를 정렬.

2.6. 그래프의 응용

  1. 소셜 네트워크 분석:
    • 연결 강도, 추천 알고리즘.
  2. 경로 탐색:
    • 네비게이션, 지도 서비스.
  3. 인터넷 라우팅:
    • 네트워크 라우팅 프로토콜.
  4. 스케줄링:
    • 작업 간의 우선순위 관계 표현.

트리와 그래프의 차이점

특징 트리 그래프
구조 계층적 구조 (사이클 없음) 네트워크 구조 (사이클 존재 가능)
루트 루트 노드가 존재 루트 노드 없음
방향성 방향 그래프 방향/무방향 그래프 모두 가능
연결성 항상 연결 그래프 연결/비연결 그래프 모두 가능

트리와 그래프는 데이터 구조와 알고리즘에서 핵심적인 요소입니다. 각각의 자료구조를 활용하여 문제를 해결하려면 데이터의 관계와 요구 사항을 명확히 분석해야 합니다. 😊

728x90
저작자표시 비영리

'알고리즘 > 공부' 카테고리의 다른 글

코드 챌린지 7일차 - 동적 계획법  (0) 2024.07.16
코드 챌린지 4일차 - 재귀와 정렬  (0) 2024.07.11
코드 챌린지 3일차 - 문자열, 분할 정복과 백트래킹  (0) 2024.07.10
코드 챌린지 2일차 - 유클리드 호제법, 소수 판별법  (0) 2024.07.09
알고리즘 코드 챌린지 1일차 - 시간 복잡도  (0) 2024.07.08

'알고리즘/공부'의 다른글

  • 현재글면접 준비 - 알고리즘, 자료구조 개념 정리

관련글

티스토리툴바