전체 글76 [백준] 27. 텀 프로젝트 9466 해설 텀 프로젝트 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 풀이 문제를 해결하는 아이디어 자체는 꽤 간단합니다. 먼저 팀이 만들어지는 경우는 원하는 학생들끼리의 사이클이 형성되는 경우 밖에 없습니다 (본인을 선택하는 경우도 사이클이 형성된다.) 반대로 팀이 되지 않는 경우는 사이클이 형성되지 않는 경우입니다. 생각보다 규칙이 간단하기 때문에 구현만 잘 진행해 주면 됩니다. 원하는 학생을 끝까지 탐색해줘야 하기 때문에 깊이 우선 탐색으로 구현해 주면 됩니다. DFS를 진행해 주면서 아래 두 가지 경우만 처리해.. 2024. 1. 21. [백준] 26. 별자리 만들기 4386 해설 별자리 만들기 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 풀이 높은 정답 비율답게 쉽게 풀 수 있었던 문제입니다. 결국에는 최소 비용으로 별자리를 이어주면 되기 때문에 최소 간선만을 이어줘야 되며 사이클이 생기면 안 됩니다. 따라서 최소 신장 트리 알고리즘을 사용하면 되는 문제입니다. 다만 간선이 따로 주어지지 않았기 때문에 각 별자리의 좌표를 이용하여 모든 경우의 간선을 구해주면 됩니다. 먼저 크루스칼을 이용한 풀이입니다. 모든 간선을 구한 뒤 우선순위 큐에 넣어줍니다. 그다음 큐에서 간선을 하나씩.. 2024. 1. 17. [백준] 25. 세 용액 2473 해설 세 용액 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 문제 풀이 해당 문제는 이전에 용액2467 문제를 풀었기 때문에 투 포인터를 이용한 문제라는 것을 알고 있었습니다. 하지만 선택해야 되는 용액이 3개이기 때문에 약간의 응용만 해주면 됩니다. 결국은 투 포인터를 이용해야 되지만 우리는 3개의 용액을 선택해야 됩니다. 따라서 하나의 용액은 결정되었다는 가정하에 2개의 용액만 투 포인터로 구해주면 됩니다. (투 포인터 + 완전탐색) 풀이 방법은 다음과 같습니다. 용액을 정렬해 준다. f.. 2024. 1. 15. [백준] 24. Dance Dance Revolution 2342 해설 Dance Dance Revolution 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 80일 넘게 1일 1문제를 풀었던 기록이 깨지게 되었습니다. 문제의 난이도가 올라감에 따라 문제를 못 푸는 빈도가 증가하게 되었는데 이 와중에 하루에 한 문제를 꼭 풀어야 된다는 생각 때문에 문제를 쉽게 포기하고 해설을 보게 된다는 것을 느꼈습니다. 이를 방지하고자 못 푸는 문제더라도 최소 이틀의 시간 동안은 생각을 가지고 나서 해설을 보기로 결정하였습니다. 해당 문제도 이와 같은 이유로.. 2024. 1. 14. 이전 1 2 3 4 5 6 ··· 19 다음 반응형
