본문 바로가기

백준286

백준 11562 c++ "백양로 브레이크" -[PlusUltraCode] https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net [필자 사고] 이 문제는 플로이드 와샬을 이용하면 쉽게 풀 수 있는 문제라고 생각했다. 이런 유형의 문제를 처음 접했다. 이 문제의 특징은 단방향 간선일 경우 Arr배열에 어떠한 값을 넣고 플로이드 와샬 알고리즘을 진행힐자기 관건인 문제이다. 곰곰히 생각하고 자료도 찾아보고 깨달은 점은 문제에서 요구하는 단방향 간선을 양방향 간선으로 바꾼다는 말은 즉 반댓 방향으로 갈려면 비용이 1증가한다와 같.. 2024. 2. 29.
백준 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.

티스토리툴바