목록플로이드-와샬 (6)

반갑습니다!

[백준] 1956 운동

1956번: 운동 boj.kr 풀이 도로 길이의 합이 가장 작은 사이클을 찾는 문제이다. V가 400 이하이기 때문에 플로이드-와샬 알고리즘을 사용하면 쉽게 해결할 수 있다. 코드 C++
알고리즘 문제 풀이 2020. 11. 26. 13:34
[백준] 1389 케빈 베이컨의 6단계 법칙

1389번: 케빈 베이컨의 6단계 법칙 boj.kr 풀이 N이 100 이하이므로 플로이드-와샬 알고리즘을 사용하면 쉽게 해결할 수 있다. 플로이드 와샬 알고리즘을 사용해 친구들간의 거리를 구한 뒤, 가장 작은 케빈 베이컨 수를 가진 친구의 번호를 출력하면 된다. 코드 C++ #include #include using namespace std; const int INF = 1e9; int n, m; vector adj; void floyd_warshall() { for (int k = 1; k n >> m; adj = vector(n + 1, vector(n + 1, INF)); for (int i = 1; i > a >> b; adj[a][b] = 1; adj[b][a] = 1; } floyd_warsh..
알고리즘 문제 풀이 2020. 10. 1. 01:57
[백준] 2458 키 순서

2458번: 키 순서 boj.kr 풀이 [프로그래머스] 순위 와 동일한 문제이다. 플로이드 워셜 알고리즘을 사용해서 모든 학생들 간의 관계를 알아낸다. 그리고 본인을 제외한 모든 학생들과 관계가 있는 학생들을 세주면 된다. 코드 C++ #include #include using namespace std; int n, m; vector adj; void floyd_warshall() { for (int k = 1; k > m; adj = vector(n + 1, vector(n + 1, false)); for (int i = 0; i > a >> b; adj[a][b] = true; } floyd_warshall(); int answer = 0; for (i..
알고리즘 문제 풀이 2020. 9. 30. 16:12
[프로그래머스] 배달

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 그래프의 최단 거리를 계산해서 해결하는 문제이다. 따라서 최단 경로 알고리즘을 사용하면 해결할 수 있을 것으로 보이는데, 해당 문제에서 N이 최대 50이므로 간단한 플로이드-와샬 알고리즘을 사용해서 해결했다. 이 문제에서 플로이드-와샬 알고리즘을 사용할 때 주의할 점은 a에서 b로 가는 경로가 여러 개일 수 있다는 점이다. 따라서 인접 배열을 만들 때, 해당 경로에 대한 최솟값으로 만들어줘야한다. 코드 C++ #include #include #define MAX 987654321 using namespa..
알고리즘 문제 풀이 2020. 9. 5. 14:58
[프로그래머스] 순위

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 모든 선수와의 승패를 알 수 있다면 순위가 결정될 것이다. 따라서 이 문제의 핵심은 한 선수에 대해서 승패 결과의 갯수가 n-1개이면 순위가 결정된다는 것이다. 따라서 모든 선수의 승패 결과를 만들어줘야하는데, 해당 문제에서는 선수의 수가 최대 100명이므로 플로이드-와샬 알고리즘으로 모든 경우를 구할 수 있다. 따라서 플로이드 와샬 알고리즘을 사용해서 모든 경우의 승패를 표시한 뒤, 갯수를 세어주면 해결할 수 있다. 코드 C++ #include #include using namespace std; in..
알고리즘 문제 풀이 2020. 9. 4. 14:33
이전 Prev 1 2 Next 다음