알고리즘

배열 회전

https://funveloper.tistory.com/16

문자열 index로 read는 가능한데 write는 불가능하다.

그래프

위상정렬

방향이 있는 그래프를 방향대로 나열하는 것

• 노드간의 선후관계를 나타내기 위해서 사용
  ex ) 일의 순서 스케줄링..등..
• 답이 여러가지인 경우가 있을 수 있다. -> 확정적인지 여부를 구분하기위해 쓰지는 않는다.
• 복잡도 : O(N+E)

조건

진입차수가 0인 노드가 있어야한다!
간선의 가중치 없다!

방법

1. 각 노드의 진입차수를 확인한다.
2. 진입차수가 0인 노드부터 시작(큐에 넣음)
3. 큐에 있는 노드를 뺄 때 그 노드와 연결된 노드를 큐에 넣고 진입차수를 하나씩 뺀다.

질문

• 그냥 bfs로 해도되는것 아닌가?... ㄴㄴ imo bfs의 한 종류인 듯.
• 사이클이 있는 경우 어떤 특징?
• 위상정렬에 의해 특정된 값은 무슨 특징을 가짐?

다익스트라 알고리즘

시작 노드 to 다른 노드까지의 최단거리를 계산

• 즉 한 시작점에 대해서 모든 정점까지의 최단거리를 계산하는 것
• O(E log E)

조건

• 간선 가중치 음수 불가
• 시작 노드가 있어야함

벨만포드

O(EV)

플로이드 와샬

모든 노드 to 모든 노드까지의 최단거리를 계산한다.

• 모든 노드 사이의 최단 경로를 구한다.
• 음수 가중치도 가능하다.
• 시간 복잡도 : O(n^3)

방법

1. 바로 이어진 노드끼리의 거리를 기록
2. 중간 노드를 선택
3. 중간 노드와 연결된 노드의 거리를 최소값으로 갱신
4. 2,3을 노드 개수만큼 반복
   1613 역사

크루스칼

최소신장트리
O(E log E)