알고리즘을 좋아하는 나

1. R1/2 + R2/2 = S (기본식)

2. R1/2 - S = -R2/2 (이항)

3. R2=2S-R1 (더 간단한 식)

1. 모든 섬을 DFS 해본다.

2. 이미 방문했다면 DFS 를 중단한다.

3. w 너비, h 높이 가 순서대로 입력되므로 잘 체크하자

4. 입력을 반대로 받고 처리하면 된다.

더 좋은 방법

1. visited 를 사용하지 않고, map 을 0 으로 만든다.

2. 0 으로 만들면 다시 배열을 초기화해줄 필요도 없다.

quick select 라는게 있어서 공부하고 사용했다.

1. quick select 함수 실행

2. pivot = partition

3. partition 에서는 pivot 을 기준으로 작은값과 큰 값을 나눈다.

4. pivot 을 정하면 그 것은 고정이 된다.

5. pivot 을 확인해서 값 출력

1. 한 바퀴 돌린다.

2. 한 바퀴 더 돌리면서는 업데이트 될 때마다, 무한대로 설정한다.

3. 그걸로 출력

다익스트라 알고리즘과 차이점

1. 음수 가중치가 있어도 작동이 된다.

2. 음수 사이클을 체크할 수 있다.

내가 작성한 코드의 worst time complexity 예상 O(V^2*E)

작동방식

1. distance 를 모두 임의의 값으로 체운다.

2. edge 에 가중치들을 넣는다.

3. vertex 만큼 forloop 을 하나 돌린다.

4. 그 안에서 연결된 edge 를 다 체크해준다.

5. cnt 가 N 이 된다는 것은 update 가 된다는 뜻 ( 음수 사이클 )

1. 입력값이 1 2 면 [1][2] = -1 [2][1] = 1

2. Floyd-Warshall 실행

3. 그대로 출력

아이디어만 있다면 간단한 문제

기존 floyd-warshall 알고리즘과 동일하게

1. i > j 를 갱신하고 싶다.

2. 어떻게 하지?

3. i > k > j 가 되는경우

끝.

i -> j 를 갈 때,

i -> k -> j 를 가는게 더 짧으면 업데이트 한다.

floyd-warshall 의 아이디어다.

O(V^3)

다음 문제때, 조금 더 자세히 살펴보면서 증명까지 가능하면 해보겠다.

이분 매칭을 2번 작동하면 된다.

글을 작성하다 날려서 더 길게 적고싶지 않다.