본문 바로가기

백준287

백준 1766 c++ "문제집" -[PlusUltraCode] https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net [필자 사고] 이 문제의 핵심은 위상정렬 알고리즘을 알고 있냐 모르고 있냐 이다. 위상정렬 알고리즘은 쉽게 말해 이 노드와 저 노드가 레벨차이에 따라 정렬해 놓는 알고리즘이다. 또한 이 문제에서 위상정렬에서 사용하는 큐를 보통의 큐가 아닌 우선순위 큐를 사용하여 N이 낮은값부터 출력할 수 있도록 유도했다. [소스 코드] #include #include #include.. 2024. 2. 29.
백준 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.

티스토리툴바