백준284 백준 1613 c++ "역사" -[PlusUltraCode] https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net [필자 사고] 플로이드 와샬 알고리즘을 이용하면 쉽게 해결할 수 있는 문제이다. 입력창을 보면 선후 관계 화살표로 주어 졌으므로 와샬 알고리즘을 사용후에는 후속 조취가 필요하다. 그 이유는 다음과 같다. 1->4 의 값이 자연수이고 4->1의 값이 무한대일때 1과4는 선후관계가 형성 되었따. 1->4를 보면 선후관계를 알 수 있지만 4->1을 보면 선후관계를 판별할 수 없기 때문이다. 이 .. 2024. 2. 28. 백준 1058 c++ "친구" -[PlusUltraCode] https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net [필자 사고] 플로이드 와샬 알고리즘이다. 플로이드 와샬 알고리즘의 중요한 특징이 있다. 문제에서 그래프로 주어 졌을때랑 2차원 배열로 주어 졌을때는 조금의 차이점이 있다. 먼저 그래프이다. 와샬 알고리즘 사용 후 1->4의 값이 자연수고 4->1 이 값이 무한대일 경우 1과 4의 관계가 형성 되었기 때문에 4->1의 값 또한 변경해줘야 된다. 반면에 배열로 주어졌을 경우 후속조취 없이 바로 와샬 알.. 2024. 2. 28. 백준 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. 이전 1 ··· 60 61 62 63 64 65 66 ··· 71 다음