정렬 (54) 썸네일형 리스트형 백준 2230번 [수 고르기](C++) -yes6686- 티스토리 백준 문제 풀이: 2230 (수 고르기)문제 링크: https://www.acmicpc.net/problem/2230문제 설명:정수로 이루어진 N개의 수열에서 두 수를 골라 그 차이가 M 이상이면서 가장 작은 차이를 찾는 문제입니다. N은 최대 100,000이므로 O(n2) 풀이로는 해결이 불가능하며, 효율적인 정렬 기반 이분 탐색 혹은 투 포인터 알고리즘이 요구됩니다.문제 해결 코드// ✅ 투 포인터 풀이#include #include using namespace std;int arr[100001];int main() { int n, m; cin >> n >> m; for (int i = 0; i > arr[i]; } sort(arr, arr + n); int minDi.. 백준 3151번 [합이 0](C++) -yes6686- 티스토리 백준 문제 풀이: 3151 (합이 0)문제 링크: https://www.acmicpc.net/problem/3151문제 설명:정보올림피아드 캠프에서 학생 n명의 실력이 주어진다. 이 중 서로 다른 3명을 뽑았을 때, 실력의 합이 0이 되는 조합의 개수를 구하는 문제이다. 중복 없이 3명을 선택해야 하며, 정렬된 상태를 활용하여 효율적으로 계산할 수 있어야 한다.핵심 알고리즘: 정렬 + 이분 탐색을 활용한 투포인터 기반 조합 탐색. O(n2 log n)문제 해결 코드// 정렬 + 이분 탐색으로 3개의 합이 0인 경우의 수 계산#include #include #include using namespace std;vector v;int main() { ios::sync_with_stdio(false); .. 백준 2457번 [공주님의 정원](C++) -yes6686- 티스토리 백준 문제 풀이: 2457 (공주님의 정원)문제 링크: https://www.acmicpc.net/problem/2457문제 설명:공주님의 정원을 3월 1일부터 11월 30일까지 꽃이 한 송이 이상 피어 있게 하려면, 어떤 꽃들을 선택해야 하는지 찾는 문제입니다. 각 꽃은 피는 날짜와 지는 날짜가 주어지며, 최소한의 꽃을 선택해 정원을 끊김 없이 채워야 합니다.그리디 알고리즘을 적용하여 구간을 선택하는 문제이며, 가장 긴 구간을 덮는 방식으로 다음 구간을 선택해야 합니다.문제 해결 코드// 공주님의 정원 (그리디 구간 선택)#include #include #include using namespace std;pair arr[100001];queue, int>> q;int marr[13]; // 월별 일수.. 백준 1744번 [수 묶기](C++) -yes6686- 티스토리 백준 문제 풀이: 1744 (수 묶기)문제 링크: https://www.acmicpc.net/problem/1744문제 설명:양수와 음수, 0이 섞여 있는 수열에서 적절한 숫자들을 묶어 곱하거나 더해 전체 합을 최대로 만드는 문제입니다.묶을 수 있는 숫자는 두 개씩만 가능하며, 묶지 않아도 됩니다. 특히 1은 곱하기보다 더하기가 유리하고, 음수는 음수끼리 곱해서 양수로 만드는 것이 유리하며, 0은 남은 음수 하나를 무효화하는 데 사용될 수 있습니다.문제 해결 코드// 수 묶기 (그리디 + 정렬 + 덱 활용)#include #include #include using namespace std;deque d;int arr[51];int main() { ios::sync_with_stdio(false); .. 백준 11000번 [강의실 배정](C++) -yes6686- 티스토리 백준 문제 풀이: 11000 (강의실 배정)문제 링크: https://www.acmicpc.net/problem/11000문제 설명:강의 N개가 시작 시간과 종료 시간이 주어질 때, 겹치지 않게 모든 강의를 배치하려면 최소 몇 개의 강의실이 필요한지를 구하는 문제입니다. 한 강의실에서 한 번에 한 강의만 진행할 수 있고, 강의는 시작 시간과 종료 시간이 각각 주어집니다.이 문제는 그리디 + 우선순위 큐(min-heap)를 이용한 간단하지만 중요한 스케줄링 알고리즘 문제입니다.문제 해결 코드// 강의실 배정 (우선순위 큐 이용한 스케줄링)#include #include #include using namespace std;pair arr[200001];priority_queue, greater> pq;int.. 백준 2170번 [선 긋기](C++) -yes6686- 티스토리 백준 문제 풀이: 2170 (선 긋기)문제 링크: https://www.acmicpc.net/problem/2170문제 설명:좌표 평면 위에 n개의 선분이 주어집니다. 각각의 선분은 x축 위에서 시작점과 끝점을 가지며, 이 선분들이 겹치는 경우 중복을 제거한 실제 총 선 길이를 구하는 문제입니다.이 문제는 선분을 시작점을 기준으로 정렬한 뒤, 현재 선분이 이전 선분과 겹치는지를 판단하여 겹치지 않으면 누적 길이를 더하고, 겹치면 끝점을 갱신하는 방식으로 해결할 수 있습니다.문제 해결 코드// 선 긋기 (정렬 후 누적합)#include #include using namespace std;pair arr[1000001];int main() { ios::sync_with_stdio(false); c.. 백준 7571번 [점 모으기](C++) -yes6686- 티스토리 백준 문제 풀이: 7571 (점 모으기)문제 링크: https://www.acmicpc.net/problem/7571문제 설명:2차원 격자 평면 위에 m개의 점이 주어질 때, 이 점들을 한 위치로 옮기는 데 필요한 최소 이동 거리의 합을 구하는 문제입니다. 각 점은 상하좌우 방향으로만 움직일 수 있으며, 한 점을 다른 점의 위치로 옮길 수 있습니다.최소 이동 거리의 합을 구하기 위해서는 모든 점을 특정 위치로 이동시킬 때 거리 합이 최소가 되는 좌표를 찾아야 합니다. 이 좌표는 각각 x좌표와 y좌표의 **중앙값(median)**을 기준으로 결정됩니다.문제 해결 코드// 7571번: 점 모으기// 모든 점을 median 좌표로 이동시키는 것이 최적해#include #include #include using.. 백준 12760번 [최후의 승자는 누구?](C++) -yes6686- 티스토리 백준 문제 풀이: 12760 (최후의 승자는 누구?)문제 링크: https://www.acmicpc.net/problem/12760문제 설명:n명의 참가자가 m개의 카드를 가지고 있다. 각 참가자는 자신이 가진 카드 중에서 높은 값이 많을수록 유리하다. 모든 카드 위치(j번째 카드)에서 최고값을 가진 참가자에게 1점을 부여한다. 모든 위치에 대해 점수를 합산한 뒤, 가장 높은 점수를 가진 참가자가 최후의 승자가 된다. 동점자가 있다면 모두 출력한다.문제 해결 코드// 12760번: 최후의 승자는 누구?// 각 열마다 최대값을 가진 사람에게 점수를 부여하고, 최고 점수를 받은 사람(들)을 출력#include #include using namespace std;int arr[101][101]; // .. 이전 1 2 3 4 ··· 7 다음