이상학의 개발블로그

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

교육/강의

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

학학이 2016. 4. 12. 16:20
이진 탐색 트리
  • 트리
  • 노드는 최대 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)
  • 현재 상황에서 가장 좋아 보이는 답을 선택하는 방법
  • 각 부분에서 최적을 선택하면 전체에서도 최적이 될 것이라는 가정을 전제

탐욕 알고리즘과 동적 프로그래밍의 차이점
탐욕 : 하위 문제를 풀기전에 선택. 항상 하나의 문제만을 고려
  • 동적 : 하위 문제를 풀고나서 선택. 동시에 여러 문제

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



Comments