프로그래머스_순위

** 프로그래머스_순위 개인 정리 글입니다.

 

https://programmers.co.kr/learn/courses/30/lessons/49191?language=python3 

코딩테스트 연습 - 순위

문제를 읽고 바로 의문이 들었던 것은 어떻게 하면 선수의 순위를 확정할 수 있는지에 대한 의문이 먼저 들었다. 
아래 예시를 먼저 보면, 
2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.

각 선수별로 인덱스를 두고 보면 {0,0,0,0,0} 이다.
이때, {패배, ??, 패배, 패배, 승리} 에서 나머지 4개의 선수에 대한 결과값이 포함되어 있으면
한 선수의 순위를 확정지을 수 있다. 
또, 5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

 

n에 대해 각 지점을 노드라고 생각하면 그래프 전부 탐색할 필요 없이 가장 확실한 부분만 간선을 태우면 된다.

플로이드 와샬 기법을 사용하면 모든 정점에서 모든 정점으로 최단 거리를 한번만 구하면 되는데 이

경우는 최단 거리를 찾는것은 아니고 전체를 다 보지 않고 가장 확실한 부분의 간선만 태우면 되기

때문에 플로이드 와샬을 적용하는것이 문제의 의도에 적합한 알고리즘이라 생각한다. (푸는 방법은

다양하다.)

플로이드 와샬의 기법을 사용하면 O(V^3) 만큼 수행하게 된다. 여기서는 n의 3제곱이 수행된다. 

플로이드 와샬은 Dynamic Programming 방식으로 진행된다.

점화식 : distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j]) 처럼 쓰는것이 일반적이지만 여기

서는 단순히 어떤 지점을 거쳐가는지만 확인해보면 된다. 

플로이드 와샬은 아래 플로우로 실행된다. 

• 정점 i에서 정점 n을 거쳐서 정점 j로 갈 때, n을 거쳐 가는 것이 더 최단경로일 경우 업데이트 한다.
• 이렇게 거쳐갈 정점을 차례대로 모두 검사하여 업데이트 해나간다.

 

**코드 내용은 참고1블로그에 에서 코드를 참고하였습니다.

참고 :
1. https://summa-cum-laude.tistory.com/16

[프로그래머스] 순위 (Python)

2. https://ansohxxn.github.io/algorithm/floyd/ 

(C++) 플로이드 와샬 Floyd Warshall (+ 최단 경로 알고리즘 비교)