본문 바로가기

알고리즘

 (305)
[백준] 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 📄 문제개요 주환이는 등산을 하는데 올라갈때는 높은 지점만 올라갈 수 있고, 내려올때는 낮은 지점으로만 내려올 수 있다고 한다. 집에서 출발하여 목표지점까지 갔다가, 고려대학교로 돌아올때, 주어진 가중치 계산이 있을때, 그 가중치 계산을 최대의 값을 구하여라. 🤔 문제분석 등산의 가치를 (얻은 성취감) - (소모한 체력) 본다면, 소모한 체력이 클 수록 등산의 가치가 작아진다. 따라서 최단 경로로 거리가 가장 항상 짧은 순으로 이동해야..
[프로그래머스] 2023 Kakao Blind Recruitment : 표병합 https://school.programmers.co.kr/learn/courses/30/lessons/150366# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📄 문제개요 해당 문제는 주어진 조건에따라서 명령을 수행하는 구현 문제이다. 주어진 문제의 요구사항에는 서로소 집합 자료구조를 사용하여 해결 해야한다. 표가 주어졌을때, 병합하고, 값을 변경하고, 병합을 해제하고 원하는 값을 출력한다. 🤔 문제분석 표는 최대 50, 50 임으로, (50,50) 테이블을 만든다. 특정위치의 첫번째 인덱스는 표의 값을 표현하고, 두번째 인덱스는 그룹상태를 알려주는..
[프로그래머스] 2023 Kakao Blind Recruitment : 이모티콘 할인행사 https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📄 문제개요 해당문제는 유저와 이모니콘이 주어졌을때 조건에따라서 가입한 유저와 이모티콘을 산 가격을 나누어서 우선순위를 매겨, 가장 좋은 우선순위의 값을 출력하는 문제이다. 이모티콘은 10%, 20%, 30% 40% 할인 할 수 있다. 유저는 유저가 설정한 할인율 이상만큼 할인 하면 이모티콘을 산다. 모든 이모티콘을 산가격과 유저가 설정한 이모티콘 가격의 합보다 클경우 유저는 이모티콘 플러스 서..

티스토리툴바