STL

16 Apr 2023 • Algorithm

Sequence container

  • erase
  • insert$($iter, value$)$
  • push$($pop$)$_back$($front$)$
  • begin$($end$)$
  • empty // vector에는 resize 존재 // clear로 element 다 날릴 수 있음.

    array

    vector

    deque

    list

  • list는 sort 방법이 특이하다. 
    1
2

    list<int> lst.sort(comp);
//다른 것들은 algorithm의 sort(begin, end, cmp) 사용.
More …

Shortest Path Algorithm

01 Apr 2023 • Algorithm

Floyd algorithm

모든 정점간의 최단 거리를 계산하는 알고리즘이다.
음수인 cycle이 존재하면 안 된다.
3단 for문을 통해 구현 할 수 있다.
이때 가장 바깥쪽 for문에 중간의 vertex를 둔다.
경로를 나타내기 위해선 next table을 이용한다. 최단거리 table을 초기화 할 때, nxt[from][to] = to로 초기화 한다.
k를 거쳐 가는 것이 더 효과적일 때에만 nxt[from][to] = nxt[from][k]
base case 1. dist[from][to]가 INF이거나 0인 경우 : 연결 돼있지 않음.
base case 2. from == to

Dijkstra algorithm

어떤 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘.
음수인 edge가 존재해선 안 된다.
priority queue를 활용하면 더 효과적으로 구현 할 수 있다.
weighted graph를 adj list인 vector<pair<int,int>> p{weight, idx}로 나타낸다.
shortest distance table로 정점으로 부터의 거리를 저장한다.
이 table을 array로 할지 priority queue로 할지에 따라 시간복잡도가 달라진다.
경로를 나타내기 위해선 table이 갱신 될 때, 어디를 거쳐가면 되는지 기록해 둠.
priority queue에 들어가기 전에 dist가 확정이 된다. pq엔 vertex에 연결된 edge들이 들어간다.

1

pre_table. 시작점에서 나에게로 올 때 직전에 어디에 방문했는가?
More …