본문 바로가기

Algorithm/Greedy

 (40)
(C++) - 백준(BOJ) 1080번 : 행렬 www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net greedy문제였습니다. 풀이방법 1. 왼쪽 상단부터 a가 b와 다르다면 a의 해당 위치에 연산함수를 실행합니다. 이렇게 b와 같도록 결정하게 되면 다시 살펴볼 필요가 없습니다. 실행과 함께 ans변수를 ++해줍니다. 2. 행렬 크기만큼 loop를 돌며 만약 a와 b가 서로 다르면 만들 수 없으므로 -1을 출력합니다. Code #include using namespace std; int a[51][51],b[51][51],n..
(C++) - 백준(BOJ) 1946번 : 신입 사원 www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 매 테스트 케이스마다 n개의 서류심사, 면접심사 성적 순위를 pair로 한 data를 vector에 입력합니다. 2. 그 후 서류심사 성적 순위를 기준으로 오름차순으로 정렬합니다. 이렇게 되면 0번째 지원자를 제외한 나머지 인원들은 무조건 성적이 0번째보다 더 낮으므로 두번째 면접점수만 비교하면 됩니다. i번째 지원자의 면접성적이 i-1번째 지원자의 ..
(C++) - 백준(BOJ) 1049번 : 기타줄 www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 패키지로 구입할 때의 최소 금액과 낱개로 구입할 때의 최소 금액을 각자 저장합니다. 2. 구입 방식을 3가지로 나누어 각자 방식에 따라 금액을 구합니다. 2-1. n개 이상으로 줄을 패키지로 구입할 때 2-2. n개 만큼 줄을 낱개로 살 때 2-3. n개 미만으로 최대한 패키지로 산 후 나머지를 낱개로 살 때 3. 이들 중 최소값을 출력합니다. Code #include..
(C++) - 프로그래머스(고득점 kit - Greedy) : 단속카메라 programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 회의실 배정 문제와 같은 방식의 문제였습니다. 풀이방법 1. 고속도로에서 나가는 지점이 빠른 순으로 routes를 정렬해줍니다. 2. 고속도로의 전체 길이를 빠르게 탐색하기 위해서는 나가는 지점만 비교하는 것입니다. O(n)으로 routes의 원소를 나가는 지점만 비교해 지나가는 자동차의 수 가장 많이 겹치는 지점마다 answer변수를 더합니다. 어떤 자동차를 골랐을 때 그 자동차가 나가는 지점이 가장 빠르다면 그 지점보다 작은 지점에서 출발하는 모든 자동차를 단속할 수 있습니다...
(C++) - 프로그래머스(고득점 kit - Greedy) : 섬 연결하기 programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 크루스칼 문제였습니다. 풀이방법 1. 간선을 가중치의 오름차순으로 정렬합니다. 2. 사이클이 생기지 않는다면 n-1개의 간선을 union해준 후 뽑아줍니다. Code #include #include #include #include using namespace std; int parent[100001]; int find(int a){ if(a == parent[a]) return a; return a = find(parent[a]); } int unionParent(int a..
(C++) - 백준(BOJ) 1715번 : 카드 정렬하기 www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net min heap을 사용해 푼 문제였습니다. 풀이방법 1. 카드 묶음을 입력 받고 minHeap에 push해줍니다. 2. 카드 두장을 뽑고 답 변수 ans에 더해준 다음 합쳐진 카드를 다시 minHeap에 push합니다. Code #include using namespace std; int n, card; int main(){ int ans = 0; cin >> n; priority_queue mi..
(C++) - 백준(BOJ) 2217번 : 로프 www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 귀류법으로 greedy로 푸는 것이 합당한지 검증합니다. 귀류법이란 세운 명제에 반하는 명제를 세운 후 해당 명제가 거짓임을 보여 결론적으로 기존 명제가 참임을 증명하는 방법입니다. 먼저 가정을 세웁니다. 가정 : 들어올릴 수 있는 중량이 최대인 로프를 선택하면 최대 중량을 들어올릴 수 있다. 반하는 가정 : 들어올릴 수 있는 중량이 최소인 로프를 선택하면 최대 ..
(C++) - 백준(BOJ) 1700번 : 멀티탭 스케줄링 답 www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net greedy문제였습니다. 풀이방법 플러그를 꽂는 방법을 생각해야 합니다. 1. 전기용품 이름이 현재 멀티탭에 꽂혀있는 경우 : 뺄 필요가 없습니다. 2. 전기용품 이름이 현재 멀티탭에 꽂혀있지 않은 경우 : 빈 멀티탭에 꽂아줍니다. 3. 멀티탭이 모두 차서 빼야되는 경우 : 앞으로 사용되지 않는 용품이거나 가장 나중에 사용되는 용품인 경우 이 제품을 빼줘야합니다. 따라서 모든 multiTap 구멍을 찾아서 꽂혀..

티스토리툴바