알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 중간에서 만나기 방법을 사용하는 문제입니다. 배열 A, B, C, D에서 수를 한 개씩 뽑아 합이 0이 되게 만드는 문제입니다. 배열의 크기가 크기 때문에 모든 경우를 탐색하기에는 무리가 있습니다. 따라서, (A+B) / (C+D)로 나눠서 합을 구한 뒤, 둘을 합치는 방법을 사용합니다. 두 배열에 있는 수를 더하는 것이기에 합이 같은 경우가 있을 수 있습니다...

문제 링크입니다. https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 투포인터를 이용하는 문제였습니다. https://junseok.tistory.com/314 -> 이 문제에서 조건이 하나 추가된 문제입니다. 두 용액이 아닌, 3개의 용액을 선택해 값이 최소가 되는 것을 구하는 문제입니다. 두용액이였다면, 간단한 투포인터를 이용해 풀 수 있겠지만, 용액이 3개이기에 일반적인 방법으로 풀 수는 없었습니다. 가장 간단하게 생각할..

문제 링크입니다. https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 투포인터를 사용하는 문제입니다. 투포인터는 조건에 따라 양쪽 끝을 하나씩 줄여가면서 원하는 값을 찾는 방법입니다. 2개의 용액을 선택해 두 수의 차의 최솟값(절댓값)을 구하는 문제입니다. 그렇다면 크기 순으로 정렬한 뒤, 가장 큰 수와 가장 작은 수를 선택하면서 시작합니다. 그 후, 조건에 따라 자신보다 큰 수 혹은 작은 수를 선택해가면 답이 나올 것입니다. 문제 예시를 통..

문제 링크입니다. https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 투 포인터를 이용하는 문제입니다. 두 개의 용액을 선택해서 최대한 0에 가까운 값을 만드는 문제입니다. 백트래킹으로도 풀 수 있겠지만, N값이 100,000이기에 시간초과가 생깁니다. 따라서 이분탐색 중 투 포인터를 통해서 풀어야됨을 알 수 있습니다. 투 포인터는 양 끝의 범위를 잡아놓고, 조건에 따라 범위를 좁혀나가는 것을 의미합니다. 해당 문..