기초 자료 구조

Reference

• 이것이 코딩 테스트다 with 파이썬

 

스택

• 선입후출, 후입선출

https://nitinagam17.medium.com/data-structure-in-swift-stack-part-3-81fdb946b160

stack = []

stack.append(3) # 3
stack.append(5) # 3 5
stack.append(7) # 3 5 7
stack.pop() # 3 5
stack.append(4) # 3 5 4
stack.pop() # 3 5

 

큐

• 선입선출

https://medium.com/@hamidakcodes/a-simple-introduction-to-queue-data-structure-839ed00e6764

 

재귀 함수

• 자기 자신을 다시 호출하는 함수
• factorial 계산할 때

 

Graph

• 그래프는 노드(Node), 간선(Edge)
• 이 때 노드를 정점(Vertex)라고도 함

https://medium.com/geekculture/breadth-first-search-a-simple-explanation-d7c323960d35

• 두 노드가 간선으로 연결되어 있다면 '두 노드는 입접하다(adgacent)'라고 표현
• 프로그래밍에서 그래프틑 크게 2가지 방식으로 표현할 수 있음
  • 인접 행렬(adjacency matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식
  • 인접 리스트(adjacency list): 리스트로 그래프의 연결 관계를 표현하는 방식

1. 인접 행렬

• 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
• 연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성(실제 코드에서는 999999999 등의 값으로 초기화하는 경우가 많음)

2. 인접 리스트

• 모든 노드에 연결된 노드에 대한 정보를 차례로 연결하여 저장함

 

3. 인접 행렬 vs 인접 리스트

• 메모리와 속도 측면에서 살펴봄
• 메모리 측면
  • 인접 행렬은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비됨
  • 인접 리스트는 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용함
  • 그러나 이러한 속성으로 인접 리스트는 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림
  • 인접 리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문임
  • 예를 들어, 노드 1과 노드 7이 연결되었는지 확인 -> 인접 행렬 방식에서 graph[1][7]만 확인하면 됨. 반면 인접 리스트는 노드 1에 대한 인접 리스트를 앞에서부터 차례로 확인해야 함
  • 특정 노드와 연결된 모든 인접 노드를 순회해야 하는 경우 인접 리스트가 인접 행렬에 비해 메모리 공간의 낭비가 적음

DFS

• 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 특정 경로로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘
• DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같음
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 함
  2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 (방문 처리: 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있음)
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
• DFS는 스택을 이용하는 알고리즘, 구현은 재귀 함수를 이용하면 쉬움

 

BFS

• 너비 우선 탐색 : 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘
• '최단 경로'를 찾아주며 필요한 준비물은 큐(Queue) 임
• 가까운 노드부터 탐색하는 알고리즘
• BFS 구현은 선입선출 방식인 큐 자료구조를 이용함
• 동작 방식은 다음과 같음
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 함
  2. 해당 노드(큐에서 꺼낸 노드)에 연결된 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 함
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복함

DFS vs BFS

• DFS => 동작원리: 스택 / 구현방법: 재귀함수
• BFS => 동작원리: 큐 / 구현방법: 큐 자료구조 이용