본문 바로가기

알고리즘/백준

 (263)
[백준] 1092번 : 배 1092번: 배 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 📄 문제개요 항구에 크레인이 있고, 최대 박스를 들 수 있는 크레인이 주어지고, 모든 크레인이 동시에 박스를 옮기는데 걸리는 시간은 1분이다. 박스와 크레인이 주어졌을때, 옮길 수 있는 최소 시간을 구하여라. 🤔 문제분석 크레인과 박스를 내림차순 으로 정렬한다. 박스를 순회하면서, 크레인이 박스를 제거시킨다. 박스를 제거시킬때 크레인은 자기가 옮길 수 있는 최대의 무게를 그순간 옮겨야한다. O(M^2*N)으로 문제를 해결한다. 📝..
[백준] 1285번 : 동전 뒤집기 1285번: 동전 뒤집기 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 📄 문제개요 동전의 테이블이 주어졌을때, 행과 열을 선택하여 동전을 뒤집어서 뒷면이 가장 적게 나오는 개수를 구하는 문제이다. 🤔 문제분석 해당 문제는 완전탐색 + 비트마스킹으로 문제를 해결해야한다. 초기 접근 : 모든행을 뒤집어 보는경우와, 모든열을 뒤집어보는 경우중에서 뒷면이 더 작게 나오는 개수를 카운팅하여 출력한다. 위의 접근으로는 모든 경우를 탐색하지 못함으로, 문제를 해결 할 수 없다. 모든 행에대하여, 뒤집는경우와 뒤집지..
[백준] 3109번 : 빵집 3109번: 빵집 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 📄 문제개요 가스 배관을 설치 할 수 있는 경우의 수를 탐색하는 문제이다. 가장 오른쪽열에서 출발해서, 가장 왼쪽열로 도착 할 수 있는 경우의 수를 구해야한다. 가스배관 설치시에 겹처서 설치 되는 경우는 경우의 수에서 제외한다. 🤔 문제분석 그리디 문제로, 0번째 행에서 출발한다면, 오른쪽 위, 오른쪽, 오른쪽 아래 순으로 무조건 탐색해야한다. R-1 번째 행에서 출발한다면, 오른쪽 아래, 오른쪽, 오른쪽 위 순으로 무조건 탐색해야한다. 깊이우선 탐색으로 우선..
[백준] 23843번 : 콘센트 23843번: 콘센트 23843번: 콘센트 광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한 www.acmicpc.net 📄 문제개요 전자 기기를 충전하려고 할때, 사용가능한 콘센트의 개수는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한번에 하나의 콘센트에서만 충전 가능하고, 충전에 필요한 시간은 2^k 형태이다. 광재의 빠른 퇴근을 위해 모든 전자기기를 충전하기 위한 최소 시간을 구하여라. 🤔 문제분석 충전시간이 가장 오래걸리는 전자기기부터 콘센트에 꽂는다. 충전시간이 다 끝나면 해당 전자기기를 빼고, 다음의 전자기기를 넣는다. 전자기기가 빠지는경우는, 현재 전..
[백준] 11000번 : 강의실배정 11000번: 강의실 배정 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 📄 문제개요 강의 시간표가 존재한다. ( 시작시간, 끝나는시간) 여러개의 시간표가 주어졌을때, 강의실을 최소화 하는 개수를 구하는 문제이다. 수업이 겹치는 강의는 강의실을 다른 강의실에서 강의를 해야한다. 🤔 문제분석 강의 시간표를 순회하면서, 우선순위 큐를 사용하여 문제에 접근합니다. 끝나는 시간을 기준으로 큐에 삽입한다. 끝나는 시간으로 한 이유 (?) 다음 리터럴에서 시작시간과 끝나는 시간을 단 한번만 확인하면 된다. 📝 의사코드 현재 강의실이 없다면 강의실을 만든다. 강의 시간..
[백준] 1700번 : 멀티텝 스케줄링 1700번: 멀티탭 스케줄링 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 📄 문제개요 전기 기구가 있고, 멀티탭의 플러그 개수가 정해져 있을때, 모든 전기기구를 주어진 순서에따라서 멀티탭 플러그에 꼽아서 사용해야하는데, 뽑았다가 빼야하는 최소 개수를 구하여라. 🤔 문제분석 그리디 문제로 여러가지를 처음에 생각해보았고, 아이디어가 떠올리지 않아서, 정답을 찾아보았습니다. 전기기구를 뽑을때 출연빈도가 낮아야 하는 전기기구를 뽑아야한다. 가장 출연빈도가 높은 순으로 뽑는다. 현재 연결해야하는 전기기구부터, 연결..
[백준] 16681번 : 등산 16681번: 등산 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 📄 문제개요 주환이는 등산을 하는데 올라갈때는 높은 지점만 올라갈 수 있고, 내려올때는 낮은 지점으로만 내려올 수 있다고 한다. 집에서 출발하여 목표지점까지 갔다가, 고려대학교로 돌아올때, 주어진 가중치 계산이 있을때, 그 가중치 계산을 최대의 값을 구하여라. 🤔 문제분석 등산의 가치를 (얻은 성취감) - (소모한 체력) 본다면, 소모한 체력이 클 수록 등산의 가치가 작아진다. 따라서 최단 경로로 거리가 가장 항상 짧은 순으로 이동해야..
[백준] 11066번 : 파일 합치기 11066번: 파일 합치기 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 📄 문제개요 두개의 파일을 합칠때 필요한 비용이 주어질때, 한개의 파일을 완성하는데 필요한 비용의 총 합을 계산하여라. 최소비용으로 계산하는 프로그램을 작성하여라. 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고 라는 조건으로 우선순위 큐로 풀 수 없다. 🤔 문제분석 우선순위 큐 해당문제는 우선순위 큐로 문제를 해결 할 수 있습니다. 최소비용을 갖으려면 항상 작은값을 합쳐야합니다. 따라서 우선순위큐로 항상 작은값 2개를 선택..

티스토리툴바