알고리즘

문제 10219번: Meats On The Grill 각 테스트 케이스마다 각 고기덩이를 뒤집은 후의 불판의 상태를 H줄에 걸쳐서 출력한다. 각 줄에는 W개의 문자가 있어야 하며, 입력에서 주어진 각 고기 덩이가 뒤집힌 채로 있어야 한다. 이를 www.acmicpc.net 풀이 애드 혹, 해 구성하기 처음에는 BFS에 구현을 더한 문제로 접근했지만, 간단한 문제였다. 주어진 불판 자체를 뒤집으면 고기가 겹치지도 않고, 전체가 뒤집힌다. 코드 #include using namespace std; char m[11][11]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int T; cin >> T; while (T--) ..

문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 우선 순위 큐 모든 수를 vector에 넣으면 메모리 초과가 발생한다. 수를 입력받으면서 바로 처리해줘야 한다. 오름차순 우선순위 큐를 만든다. 우선순위 큐는 입력받으면 바로 정렬되므로 top에는 큐에서 가장 낮은 값이 위치하게 된다. 즉, 우선순위 큐의 size를 N으로 제한한 상태에서 i번째 수까지 입력받으면, top에는 i번째 수 중에서 N번째로 큰 수가 위치하게 된다. 코드 #include #include using namespace std; prio..

문제 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 풀이 구현, 브루트포스 알고리즘 1부터 10000까지의 수, n이 셀프 넘버인지 검사한다. 1부터 n 사이의 수 i에 대해서 (n - i)가 n의 생성자인지 검사한다. (n - i)의 각 자리수의 합을 구한다. (n - i) + ((n - i)의 각 자기수의 합) == n 이라면 (n - i)는 n의 생성자이므로 셀프 넘버가 아니다. 위의 방법으로 셀프 넘버를 찾는다. 코드 #include using nam..

문제

문제 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 풀이 그리디, 정렬 구멍이 정렬되어 들어오지 않으므로 정렬이 필수이다. // 정렬 필수 sort(hole.begin(), hole.end()); 구멍 start에서 테이프를 붙였을 때, 막을 수 있는 구멍의 거리는 start + L - 1까지이다. 이 거리보다 먼 구멍은 막을 수 없으므로, 새로운 테이프를 사용해야 한다. start + L - 1에서 다음 구멍 까지는 테이프를 붙이지 않아도 되므로, 다음 구멍이 start가 되어 다시 sta..

문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 그리디, 우선순위 큐 [백준][C++] 2170: 선 긋기 문제 풀이 정렬, 스위핑 문제이다. 현재 긋고 있는 선의 시작을 start, 끝을 end라고 하자. 선을 긋고 있을 때, 어떤 상황에서 다음 선을 한번에 그을 수 있을까? 만약 다음으로 그을 선의 시작이 end kantatatam.tistory.com 위의 문제가 생각나는 문제이다. A강의와 B강의가 서로 같은 강의실을 사용하려면 A강의가 B강의의 시작하는 시간보다 빨리 끝나야 한다. 오름차순 우선순위 큐를 만든다. priority_queue..

문제 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 그리디, 자료 구조, 우선순위 큐 2가지 방법으로 문제를 풀 수 있다. 1. 가방을 오름차순으로 정렬하고, 현재 가방에 넣을 수 있는 가격이 최대인 보석을 찾는 방법 보석과 가방을 오름차순으로 정렬한다. 용량이 적은 가방부터 현재 가방에 들어갈 수 있는 보석을 모두 우선순위 큐에 넣는다. 그렇게 되면, 우선순위 큐의 top에는 현재 가방에 들어갈 수 있으면서 가격이 최대인 보석이 위치하게 된..

문제 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 풀이 그리디 n이 5로 나누어 떨어진다면 5원으로 거스름돈을 채울 수 있다. 5로 나누어 떨어지지 않는다면 2원과 같이 채워야 한다. 1원이 아니라 2원이기 때문에, 5로 나눈 나머지를 2원으로 맞춰서 낼 수 없다. 예를 들어 1원 혹은 3원이 남았다면 2원으로 채울 수 없다. n이 5로 나누어 떨어지지 않는다면, n이 5로 나누어 떨어지거나 n이 0 이하가 될 때까지 2씩 차감한다. n이 0미만이 된다면, 거슬러 줄 수 없는 경우이다. 코드 #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin..

문제 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 그리디, 정렬 수열의 음수와 양수를 나눠서 생각한다. 음수의 경우 가장 작은 수를 둘씩 묶어야 하고, 양수의 경우 가장 큰 수를 둘씩 묶어야 한다. 추가적으로, 0이 입력된 경우도 생각해야 한다. 음수의 경우, 가장 작은 수를 둘씩 묶어야 한다. 음수의 개수가 홀수인 경우 0이 입력되었다면, 음수 중 가장 큰 음수(절댓값이 가장 작은)는 0과 묶인다. 0이 입력되지 안않다면, 음수 중 가장 큰 음수(절댓값이 가장 작은)를 정답에 더한다. 양수의 경우..

문제 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 그리디 가장 큰 자리수로 많이 입력된 알파벳이 9가 되어야 하고, 다음으로 적게 입력된 알파벳이 8이 되어야 한다. 이런 순서로 알파벳을 숫자로 변환한다. GCF가 입력되면 알파벳이 하나의 숫자라고 생각하면, GCF = G * 100 + C * 10 + F로 표현할 수 있다. ACDEB가 입력되면 ACDEB = A * 10000 + C * 1000 + D * 100 + E * 10 + B로 표현할 수 있다. 여기서 각 알파벳의 계수를 보면 다음과..