[티아카데미] 알고리즘 기초 2

이진 탐색 트리

• 트리
• 노드는 최대 2개의 자식
• 부모가 왼쪽 자식보다 크고 오른쪽보다 작다

그래프 

• V정점과 E간섭으로 이루어짐
• 정점은 독립된 개체로 동그라미로 표현
• directed graph : 방향성이 있다
• un directed graph : 방향성이 없다.

인접(Adjacency) : 두 정점이 서로 연결되어 있는 경우. 도착점을 기준으로 설명한다.

차수(Degree)

• 정점으로 나가고 들어오는 간선의 수
• 진출차수, 진입차수
• 차수는 진출과 진입의 합
• 무방향성 그래프는 진출, 집입 차수가 없다. 그냥 차수만 존재

경로(Path)

• 정점 u로부터 정점 v까지 도달가능 하기 위해 거치는 정점의 순서를 나열한 것.
• 경로의 길이 : 경로에 있는 간선의 수
• 경로가 존재할 때 거치는 간선 +1 이 경로의 길이(시작,끝 제외)

단순경로(Simple Path) : 경로에 존재하는 정점이 모두 다른 경우

순환과 단일순환(Cycle and Simple Cycle)

• 순환 : 시작점과 도착점이 같을 때
• 단일 순화 : 순환에서 경로에 존재하는 정점이 모두 다른 경우

비순환 그래프(Acyclic Graph) : 순환이 없는 그래프

연결 그래프(Connected Graph) : 정점의 모든 쌍이 경로를 가지는 무방향성 그래프

연결 요소(Connected Components) : 무방향성 그래프에서 정점들이 최대한 연결되어 있는 하위 그래프. 모든게 연결됨

강한 연결(Strongly Connected) : 방향성 그래프에서 정점의 각 쌍이 서로 도달 가능한 경우.

강한 연결 요소(Strongly Connected Components) : 방향성 그래프에서 최대한 많은 정점을 강하게 연결한 하위 그래프

무방향성 그래프와 방향성 그래프의 변환

• 무방향 -> 방향 바꾸고 방향-> 무방향. 이 경우 그래프는 변경되지 않는다.
• 방향 -> 무방향 바꾸고 무방향 -> 방향. 이 경우는 그래프가 변경 될 수 있기 때문에 조심

완전 그래프(Complete Graph)

• 무방향성 그래프에서 모든 정점의 쌍이 서로 인접한 경우

간선의 개수 구할때 새로운 정점이 생기면 이전 정점의 개수 만큼 더 필요하다는 가정으로 시작

V	E 추가	E합
1	0	0
2	1	1
3	2	1+2
4	3	1+2+3

1 ~ (n-1), if v>1

포레스트(Forest): 순환하지 않는 무방향성 그래프

트리(Tree)

• 포레스트가 연결되어 있는 경우.
• 연결된 비순환 무방향성 그래프
• 두 정점은 단일 단순 경로로 연결됨
• 간선을 제거하면 그래프는 더 이상 연결되지 않는다
• 간선 하나를 추가하면 그래프는 순환을 가진다

인접행렬 표현

1. 행렬 리스트 만들어서 표현 (링크드 리스트). n 시간복잡도. 간선의 수가 적을 때 사용. 공간 적게 차지
2. 행렬 매트릭스 표를 만들어서 표현(2차원 배열). 1 시간 복잡도. 간선의 수가 많을 때 사용. 공간을 많이 차지

   

가중 그래프(Weighted Graph) : 간선이 숫자로 표현되는 값을 가지는 그래프

트리 탐색

• 넓이 우선(Breadth-first search)
• 깊이 우선(Depth-first search)

넓이 우선 탐색

• 시작점에서 도달 가능한 모든 간선을 탐색하는 과정
• 시작점으로 부터 거리를 하나씩 늘리면서 정점을 발견
• 시작점으로 부터의 거리 : u.d = 3
• 바로 직전 정점(predecessor vertex) : u.파이 = t (u로 오기전 바로 이전 경로를 t라 한다.)
  • 바로 이전 경로만 가지고 있으면 계속 찾아갈 수 있다.

넓이 우선 탐색 정점의 색

• 초기화한 정점 : 흰색
• 발견된 정점 : 회색
• 완료된 정점 : 검은색. 모든 인접한 정점을 조사한 경우

넓이 우선 탐색 수행시간

• 초기화 시간 : theta(V)
• 그래프 탐색 시간 : bigO(V+E)
  • 정점은 최대 한 번만 조사
  • 간선은 최대 두 번 조사(x->y, y->x)
• 따라서 전체 수행시간 : bigO(V+E), 최대 최악 경우는 bigO(V^2)

깊이 우선 탐색

• 타임스탬프
• 스택 사용

다익스트라 알고리즘

• 정점 u에서 v까지의 최단 경로
• 경로 중 경로의 값이 가장 작은 경로
• single source - single destination
• 간선이 음수를 가지면 안됨 

음수 간선

• 문제 상황 : 사이클 발생시 합이 음수인 경우. 사이클을 계속 돌수록 경로가 작아진다.

Bellman-Ford

• 음수 가능
• 자기 자신을 다시 정점으로 삼는 RELAX는 제외한다.

최단 경로의 하위 경로는 최단 경로이다

완화(Relaxation)

• 현재 경로 값보다 더 적은 겨오가 존재하면 값을 변경

플로이드-와샬 알고리즘

탐욕 알고리즘(Greedy Algorithm)

• 현재 상황에서 가장 좋아 보이는 답을 선택하는 방법
• 각 부분에서 최적을 선택하면 전체에서도 최적이 될 것이라는 가정을 전제

탐욕 알고리즘과 동적 프로그래밍의 차이점

탐욕 : 하위 문제를 풀기전에 선택. 항상 하나의 문제만을 고려

• 동적 : 하위 문제를 풀고나서 선택. 동시에 여러 문제

최소 신장 트리

• 그래프에 포함되어 있는 모든 정점을 포함하는 트리