[Algorithm]🐿️99클럽 코테 스터디 1일차 TIL : 백준 11403 경로 찾기

썸네일

아는 개발자 분이 알고리즘 스터디를 하신다는 이야기를 듣고 계획에 없었지만 신청하여 진행하게 되었습니다.

혼자 공부할때보단 동기부여도 생기고 다른 사람들과 교류하면서 더 좋은 성과를 얻을 것 같아 시작하였는데, 한동안 쓰지 않던 블로그를 TIL 기록을 해야해서(스터디 참가비를 환급해준다고 한다 😊) 1일 차부터 성과가 보이는 것 같습니다.

오늘의 학습 키워드

- 플로이드 워셜

내용

플로이드 워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘입니다.

다익스트라와 비슷하지만, 다익스트라는 음의 가중치를 가진 경우 사용할 수 없지만 플로이드 워셜 알고리즘은 사용할 수 있다는 차이점이 있습니다.

이에 대해선 아래에서 좀 더 자세히 이야기 해보면 좋을 것 같습니다.

 

핵심 아이디어

플로이드 워셜 알고리즘의 핵심 아이디어는 

i 정점과 j정점 이 존재할 때, 경유지점 k를 고려하여 최단 거리를 업데이트 하는 것입니다.

수식으로 표현하면 다음과 같습니다.

D[i][j]=min(D[i][j],D[i][k]+D[k][j])

이를 코드로 표현하면 더 보기 쉬워지는데, 2차원 배열로 표현한 그래프를 전체순회하는 2중 반복문을 경유지점 k도 고려하도록 3중 반복문으로 감싸주면 됩니다.

 

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (distance[i][k] + distance[k][j] < distance[i][j]) {
                distance[i][j] = distance[i][k] + distance[k][j];
            }
        }
    }
}

3중 반복문이면 시간복잡도가 O(N^3)인데 사용해도 괜찮은가? 싶은 생각이 드는데, 전체 노드의 갯수가 크면 매우 느려집니다.

N의 수가 100 이하일 때 사용하는 것이 좋습니다.

 

연산 시간 예측

아래는 알고리즘 문제 풀이에 사용하는 대략적인 예측방법입니다.

제 pc의 cpu 클럭수는 3.3ghz인데 이는 초당 3,300,000,000 연산이 가능하다는 의미입니다.

 

이를 위 사례와 연결지어 생각하면 

100 ^ 3 = 1,000,000

1,000 ^ 3 = 1,000,000,000

10,000 ^ 3 = 1,000,000,000,000

으로 개인용 pc에서도 입력값이 10,000이 넘어가면 거의 300초(5분)이 걸린다고 에측할 수 있습니다.

문제 플랫폼에서 제공하는 연산리소스는 가정용 pc보다 낮을테니 100~1000 의 입력값 제한으로 보면 될 것 같습니다.

음의 가중치

위에서 이야기했던 다익스트라 알고리즘과의 차이점인 음의 가중치에 대해 좀 더 고민해보았습니다.

다익스트라 알고리즘은 그리디 알고리즘이 핵심 아이디어이며, 지금까지의 최선해에서 주어지는 정보로 다음 최선해를 계속 개선해 나가는 방식이라 다음 정보로 음의 가중치가 입력된다면 계속 결과값이 줄어들게 됩니다.

 

반면 플로이드 워셜 알고리즘의 경우 핵심 아이디어는 동적 프로그래밍으로 이전에 계산한 결과값을 바탕으로 다음 결과값을 계산하므로 이전 결과값을 변경하지 않습니다.

 

사실 말로 풀어쓰는 것보다 코드로 보면 훨씬 이해하기 쉬운데, 다익스트라는 Queue로 구현하며(다른 방법도 있지만 가장 효과적) 무한루프에 빠질 수 있지만 플로이드 워셜은 반복문으로 구현하여 무한루프에 빠지지 않습니다.

회고

알고리즘 공부를 오랫동안 쉬어서 이전에 공부했던 내용을 복습해 나가는게 스터디의 주 목적이 될 것 같습니다.

다른 레벨들의 문제들도 한번씩 보면서 복습 내용을 넓혀가면 좋을 것 같습니다.