본문 바로가기

전체 글381

백준 17182 c++ "우주 탐사선" -[PlusUltraCode] https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net [필자 사고] 이 문제는 플로이드와샬 알고리즘을 이용해야 된다. 이 문제의 특이한 점은 플로이드 와샬만 이용하는게 아닌 어떤 경로로 가야지 최소 비용으로 모든 지역을 탐사할 수 있는지 배울 수 있는 문제이다. 필자는 DFS알고리즘을 이용하여 최소 비용으로 모든 지역을 탐사하는 방식을 택했다. DFS알고리즘의 매력이라고 말할거 같으면 이미 방문한곳이 쓰잘대기 없는 곳이라면 다시 방문 안한상태로.. 2024. 2. 29.
백준 2610 c++ "회의준비" -[PlusUltraCode] https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 줄에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net [필자 사고] 이 문제는 기본은 플로이드 와샬 알고리즘을 사용하여 푸는 문제이다. 다른 문제와 달리 이문제의 특징은 같은 그룹으로 묶어줘야 한다는 것이다. 유니온 파인드가 떠올랐고 바로 실행에 옮겼다. 유니온 파인드를 사용할 때 주의할 점은 parent로 index접근이 아닌 항상 find로 index접근을 해야 된다는 점이다. 또한 이 문제의 조심할 포인트는 모든 인간과의 거리의 합의 최소가아.. 2024. 2. 29.
백준 2617 c++ "구슬 찾기" -[PlusUltraCode] https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net [필자 사고] 풀이 과정이 다양한 문제이다. BFS 다익스트라 플로이드워셜 DFS 등 여려가지고 존재하고 필자는 플로이드와샬알고리즘을 사용하여 문제를 해결했다. 이 문제의 특이한 점은 중앙값에 있다. 중간값을 구하는 공식은 (N+1)/2를 통해 구할수 있고 플로이드 와샬 알고리즘을 적용했을 때 1번 경로에서 도달할 수 있는 경로가 중앙값보다 같거나 많으면 중앙값이 될 수 없는 원.. 2024. 2. 29.
백준 1507 c++ "궁금한 민호" -[PlusUltraCode] https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net [필자 사고] 플로이드 와샬 알고리즘이 이미 적용된 상태로 입력값으로 들어온 문제다. 이 문제를 해결하려면 3가지 정도를 이해해야 된다. 1. s->e 가는 경로보다 s->k + k->e 경로의 합이 더 작을경우 문제가 생긴다. 그 이유는 이미 문제에서 입력값이 플로이드 와샬이 적용된 최단 거리만 주어지는데 저 식이 성립한다면 최단거리가 더 존재한다는 의미이다. 문제 자체가 모순이 되기 때문에.. 2024. 2. 29.

티스토리툴바