본문 바로가기

📊알고리즘/BOJ101

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 2143 - 두 배열의 합 2143번: 두 배열의 합 (acmicpc.net) 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 처음에 너무 많이 삽질을 했다 a와 b의 모든 누적합을 저장하여 이를 lower_bound와 upper_bound로 중복되는 값들을 제거하면 구하는 문제이다. 부배열은 순서대로 이어지기 때문에, 1, 3, 4 나 2, 5, 7 이런 배열은 포함되지 않는다. a의 모든 경우의 누적 합들 (a[0], a[0]+a[1], a[0]+a[1.. 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.
BOJ 18869 - 멀티버스 II 18869번: 멀티버스 Ⅱ (acmicpc.net) 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 1차 시도 처음에 각 우주에서 행성 2개씩 비교한 후, 각 위치에 대응하는 비교한 값을 다 더해서 그 갯수로 균등한 우주의 쌍을 구했다. 이 방법은 행성이 4개 이상일 때는 작동하지 않아서 바로 포기했다. 접근방법 정렬 각 행성의 인덱스를 저장한 후, 행성의 크기로 Sort를 하게 되면 각 우주에서 행성들의 인덱스 순서는 똑같아진다. 만약 이 행성의 인덱스가 다르면 균등한 우주가 아니다. 여기에 예외가 있.. 2024. 4. 15.

티스토리툴바