일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 위상정렬
- 세그먼트 트리
- 완전탐색
- CS
- 플로이드-와샬
- 문자열
- 백준
- 에라토스테네스의 체
- dfs
- 유니온 파인드
- 시뮬레이션
- 수학
- 스택
- 투 포인터
- JUnit 5
- 그리디
- java
- Effective Java
- BFS
- Network
- 이분탐색
- mst
- 프로그래머스
- 동적계획법
- Kotlin
- 백트래킹
- 구현
- 후니의 쉽게 쓴 시스코 네트워킹
- swea
- 알고리즘
목록플로이드-와샬 (6)
반갑습니다!
1956번: 운동 boj.kr 풀이 도로 길이의 합이 가장 작은 사이클을 찾는 문제이다. V가 400 이하이기 때문에 플로이드-와샬 알고리즘을 사용하면 쉽게 해결할 수 있다. 코드 C++
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..
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..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 그래프의 최단 거리를 계산해서 해결하는 문제이다. 따라서 최단 경로 알고리즘을 사용하면 해결할 수 있을 것으로 보이는데, 해당 문제에서 N이 최대 50이므로 간단한 플로이드-와샬 알고리즘을 사용해서 해결했다. 이 문제에서 플로이드-와샬 알고리즘을 사용할 때 주의할 점은 a에서 b로 가는 경로가 여러 개일 수 있다는 점이다. 따라서 인접 배열을 만들 때, 해당 경로에 대한 최솟값으로 만들어줘야한다. 코드 C++ #include #include #define MAX 987654321 using namespa..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 모든 선수와의 승패를 알 수 있다면 순위가 결정될 것이다. 따라서 이 문제의 핵심은 한 선수에 대해서 승패 결과의 갯수가 n-1개이면 순위가 결정된다는 것이다. 따라서 모든 선수의 승패 결과를 만들어줘야하는데, 해당 문제에서는 선수의 수가 최대 100명이므로 플로이드-와샬 알고리즘으로 모든 경우를 구할 수 있다. 따라서 플로이드 와샬 알고리즘을 사용해서 모든 경우의 승패를 표시한 뒤, 갯수를 세어주면 해결할 수 있다. 코드 C++ #include #include using namespace std; in..