본문 바로가기

알고리즘51

BOJ 2473 - 세 용액 2473번: 세 용액 (acmicpc.net) 2473번: 세 용액첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상www.acmicpc.net 접근 방법용액 문제와 비슷하게 해결 가능한 투 포인터 문제이다.세 용액의 합이 0에 가장 가까운 용액들을 고르는 문제이기 때문에 처음엔 두 개의 용액을 모두 더 한 배열을 이용하여, 나머지 용액을 투포인터로 선정하는 방법을 사용했다.  struct st{ int a; // 용액A int b; // 용액B int sum; // 용액A + 용액B}위 구.. 2024. 4. 23.
BOJ 1644 - 소수의 연속합 1644번: 소수의 연속합 (acmicpc.net) 접근 방법 투 포인터와 소수판별 알고리즘이 혼합된 문제이다. 소수 판별을 하기 위해 에라스토테네스의 체를 이용하여 소수를 배열에 저장한다. 해당 소수 배열을 투포인트를 돌면서 각 연속적인 수들의 합이 N이 될 때, 경우의 수를 + 1한다. 코드 #include #include #include using namespace std; #define MAX 4000001 #define ll long long bool chk[MAX+3]; vector arr; ll n, s; void func() { chk[1] = true; for (int i = 2; i < MAX; i++) { if(!chk[i]) arr.push_back(i); for (int j = i.. 2024. 4. 23.
BOJ 1806 - 부분합 1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 접근 방법 연속된 수들 중 합이 S 이상인 것들의 길이가 최소인 것을 구하는 문제이다. 전형적인 투포인터 유형의 문제로 쉽게 해결 할 수 있다. 문제에서 주의할 점이 S이상 이기 때문에 이 또한 고려해야 한다. 또한, 수의 범위가 꽤 크기 때문에 자료형 선정 시도 고려해야 한다. #include #include #include using namespace std; #define MAX 100001 #de.. 2024. 4. 23.
BOJ 2230 - 수 고르기 2230번: 수 고르기 (acmicpc.net) 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 접근 방법 이분 탐색으로 이 문제를 해결하려고 했다. 두 수를 고르는 것이기 때문에 하나(i)를 for을 돌면서 각 수 위에서부터 끝까지(i+1~n) 수를 이분탐색을 하면서 돌면된다고 생각. 이분탐색의 경우, 하나를 모두 돌면서 진행되므로 O(N*logN)이 수행되지만, 이를 투포인터를 이용할 경우, 모든 수를 한 번씩만 돌기 때문에 O(N)에 수행이 가능하다. 따라서, 투포인터가 더 빠른 실행.. 2024. 4. 22.
BOJ 3151 - 합이 0 3151번: 합이 0 (acmicpc.net) 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 접근 방법 3개의 수의 합이 0이 되는 조합을 모두 찾는 문제이다. 2문제를 미리 다 더한 후, 마지막 하나를 이분탐색으로 구하는 문제이다. 이 문제를 처음할 때 실수한 부분이 중복되는 값을 고려하지 않은것이다. 만약, 8 -10 5 5 5 5 5 5 5 다음 케이스가 올 경우, 5를 모두 개별 취급을 해야하므로 21이 되어야 한다. 그러나, 이분탐색의 경우 중복을 처리하는게 쉽지 않기 때문에 lower_bound와 up.. 2024. 4. 17.
BOJ 14921 - 용액 합성하기 14921번: 용액 합성하기 (acmicpc.net) 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 접근방법 용액을 무조건 두 개씩 섞어서 0에 가깝게 만드는 문제이다. 전형적인 투포인터 문제다. 포인터를 두 개만들고(a, b), a는 0부터, b는 끝부터 내려온다. 만약, 두 포인터의 용액의 합이 0보다 작으면 용액의 합을 더 크게해야하기 때문에 a++. 반대로, 용액의 합이 작으면 용액의 값을 줄여야 하기 때문에 b--를 한다. 그리고 매번 용액의 합이 0에 최대한 가까운 합을.. 2024. 4. 16.

티스토리툴바