백준154 백준 10159 c++ "저울" -[PlusUltraCode] https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net [필자 사고 ] 전형적인 플로이드 와샬을 이용하면 쉽게 해결할 수 있는 문제이다. 다만 알고리즘을 적용만 하면 답이 나오는 것이 아닌 이 문제의 특이한점은 순위가 결정 됬냐 안됬냐 하는 점이다. 만약 1->4 의 값이 자연수이고 4->1의 값은 무한대라고 했을 때 1과 4의 관계는 순위가 정해졌다고 말할 수 있따. 다만 플로이드 와샬 알고리즘을 적용하면 저런 형태로 나온다.. 2024. 2. 28. 백준 2458 c++ "키 순서" -[PlusUltraCode] https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net [필자 사고] 대표적인 순서 알고리즘 -> 플로이드 와샬 알고리즘을 써야 되는 문제이다. 플로이드 와샬 알고리즘의 개념이 부족하면 문제를 해결하기 쉽지 않았을 것이다. 간단하게 설명하자면 플로이드 와샬 알고리즘의 특징은 어떤 경로가 존재한다면 최단거리를 배열에 값에 저장해 놓는 알고리즘이다. 이 문제의 특징은 키 순서이다. 플로이드 와샬 알고리즘을 사용하면 1->4로 갈경우는 자연수로 되어 있지만 .. 2024. 2. 28. 백준 1956 c++ "운동" -[PlusUltraCode] https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net [필자 사고] 처음에는 다익스트라 BFS 벨만포드까지 생각을 해봤다. 정작 이 문제의 해결해야 하는 플로이드 와샬알고리즘은 떠오르지 않았다. 자료를 찾아보니 플로이드 와샬 알고리즘을 사용한 후 사이클이 있는지 없는지 판단하는 법은 Arr[i][k]와 Arr[k][i] 값 둘이 있을 경우 사이클이 생성된것을 알 수 있다. 이 문제를 통해 플로이드 와샬에 개념을 확실.. 2024. 2. 27. 백준 1719 c++ "택배" -[PlusUltraCode] https://www.acmicpc.net/problem/1719 [필자 사고] 다익스트라 혹은 폴로이드 워셜을 이용하여 푸는 문제이다. 필자는 다익스트라를 이용하여 문제를 해결 하였다. 다른 문제와 달리 이 문제의 핵심 포인트는 지나간 경로중 가장 첫번째 경로를 저장해야 된다. 필자는 Union과 find를 이용하여 집합을 이용해 풀었다. 먼저 parent배열에 부모노드를 저장해 주었다. 다익스트라 알고리즘이 끝난 후 parent 배열을 Union 해주어 쉽게 처음 시작한 노드를 찾을 수 있었다. [소스 코드] #include #include #include #include #include #include #include using namespace std; typedef pair Node; vecto.. 2024. 2. 27. 이전 1 ··· 28 29 30 31 32 33 34 ··· 39 다음