[Certi 세미나] 알고리즘 기초 - 그래프 구현과 순환

📌 그래프의 정의

정점과 간선으로 이루어진 비선형 자료구조

 

 

📌 그래프 용어

• 정점(Vertice) : 노드라고도 한다. 정점에는 데이터가 저장된다.
• 간선(edge) : 링크라고도 한다. 정점간의 관계를 나타낸다.
• 인접 정점 : 간선에 의해 연결된 정점. (갈 수 있는 점)
• 단순 경로 : 경로에 중복되는 정점과 간선이 없는 경로

📌 방법

2차원 배열로 간선을 표현하는 방식

: 두 정점 사이에 간선이 있는지를 한번에 찾을 수 있다.

: 구현이 간단하다는 장점이 있지만, 공간 복잡도가 제곱으로 공간 성능이 안 좋다. 시간 복잡도도 좋지 않다.

리스트로 간선을 표현하는 방식

: 두 정점 사이에 간선이 있는지를 일일이 확인해야 한다.

: 각 노드마다 리스트가 하나씩 있다.

: 구현이 다소 복잡하다는 단점이 있지만, 공간 성능이 좋다. 시간 복잡도도 좋다.

 

📌 깊이 우선 탐색 (DFS : Depth First Search)

핵심 아이디어 : 현재 분기(Branch)를 끝까지 깊게 가본 다음에, 다음 분기로 이동

 

1. 시작 정점을 방문한다.
2. 정점을 방문했음을 표시한다.
3. 방문하지 않은 인접한 정점이 없다면, 종료하고 돌아간다.
4. 방문하지 않은 인접한 정점에 대해 2번을 수행한다.

✅ 특징

• Keyword : 재귀호출(Recursion), 스택(Stack)
• BFS에 비해 직관적이고, 구현이 간단하다.
• 모든 정점을 탐색해야 할 때 쓰기 좋다.
• 방문 확인을 위한 정점 배열이 필요하다는 것을 기억할 것.

[방문 했거나 안 했거나 밖에 없다.] - 2가지

-방문 했는지 안 했는지 알 수 있는 변수를 하나 만들어라.

 

 

📌 너비 우선 탐색(BFS : Breadth-First Search)

핵심 아이디어 : 인접한 가까운 정점을 모두 방문한 뒤에 먼 정점을 순회한다.

1. 시작 정점을 방문한다.
2. 방문하지 않은 인접한 정점들을 큐에다 넣는다.
3. 큐에서 정점을 하나 꺼내서 방문한다.
4. 2번을 반복한다.

✅ 특징

• Keyword : 반복 수행(iterative), 큐(Queue)
• DFS에 비해 구현이 다소 복잡하다.
• 가중치 없는 그래프에서 목표 노드 사이의 최단 거리를 알고 싶을 때 BFS를 사용
• 방문 확인을 위한 정점 배열이 필요하다는 것을 기억할 것
• 이것에서 Dijkstra, Prim 알고리즘과 유사

[방문할 거, 방문 한 거, 방문 안 한 곳] - 3가지

나로부터 가까운 놈부터 들어간다.

 

📌 최단 경로 문제(Shortest Path)

가장 짧은 경로에서 두 꼭지점을 찾는 문제로 그래프의 형태와 문제의 특징에 따라 최적의 알고리즘이 달라짐

• 비가중치 그래프 - BFS(너비 우선 탐색)
• 양의 가중치만 가지는 그래프 : 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 문제 → 다익스트라(Dijkstra) 알고리즘

그리디 알고리즘이랑 다이나믹 프로그램이 먹힌다.

 

📌 문제 해결 기법

문제를 해결하기 위한 알고리즘의 설계 기법을 정리하여, 그 중 많이 알려진 유명한 알고리즘 전략을 소개한다.

• 분할 정복법 : 정복할 수 있을 때까지, 문제를 분할하라
• -이진 탐색, 합병 정렬
• 그리디 알고리즘(탐욕법) : 매 순간 가장 탐스러운 답을 선택한다.
• 백트래킹 : 모든 경로를 다 찾아보자
• -BFS, DFS
• 동적 계획법 : 한 단계 작은 규모의 최적 값으로 현재의 최적 값을 계산한다.
• -다익스트라 알고리즘