백준189 백준 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. 백준 5972 c++ "택배 배송" -[PlusUltraCode] https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net [필자 사고] 문제는 복잡해 보이지만 전형적인 다익스트라 알고리즘을 이용한 최단거리 문제이다 이 부분만 잘 캐치한다면 쉽게 문제를 해결할 수 있을 것이다. [소스 코드] #include #include #include #include #include #include #include using namespace std; typedef pair Node; int N, M; vector Arr; vector p.. 2024. 2. 27. 이전 1 ··· 37 38 39 40 41 42 43 ··· 48 다음