Algorithm

[백준 1806번] 부분합 (C++)

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N = S를 만족하는 en을 찾습니다. (단, st는 시작점, en는 끝..

[SW Expert Academy 13732번] 정사각형 판정 (C++)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 정사각형 판정 문제는 x의 최솟값/최댓값, y의 최솟값/최댓값을 찾아 해결할 수 있습니다. x, y의 최소/최댓값을 찾은 이후에는, 가로/세로 길이가 동일한지 확인하고, 정사각형의 내부가 막혀있는 격자로 채워져있는지 확인하면 됩니다. 아래는 전체 코드입니다. #include using namespace std; #define x first #define y second char board[30][30]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int t, i = 1; cin >> t; while(t--){ in..

[SW Expert Academy 14178번] 1차원 정원 (C++)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1치원 정원 문제는 나누기 연산으로 해결할 수 있습니다. 모든 꽃이 한 개 이상의 분무기에서 물을 받을 수 있도록 하기 위해서는 [x - D, x + D] 구간이 겹치지 않도록 물을 주면 됩니다. 1차원 정원이 [1, 2, 3, 4, 5]이고, D가 1인 경우, 첫 번째 분무기는 1번 인덱스에, 두 번째 분무기는 3이나 4번 인덱스에 두면 됩니다. 따라서 필요한 최소한의 분무기 수는 n / (D * 2 + 1)입니다. (D * 2 + 1은 분무기 하나가 물을 줄 수 있는 정원의 길이) 하지만, 만약 n이 (D * 2 + 1)로 나누어 떨어지지 않는 경우, 올..

[백준 2230번] 수 고르기

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 수 고르기 문제는 이분탐색을 이용하여 해결할 수 있습니다. 먼저, 수열의 임의의 요소 X를 선택하고 X + m보다 크거나 같은 값 중 가장 작은 값을 Y라고 하면, Y - X의 최솟값을 찾으면 됩니다. 이 값을 찾기 위해 이분탐색이 사용됩니다. lower_bound(first, last, value)는 value보다 크거나 같은 값들 중 제일 작은 값을 찾는데 사용됩니다. 아래..

[백준 3151번] 합이 0 (C++)

https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 합이 0 문제는 이분 탐색으로 해결할 수 있습니다. N이 최대 10,000이기 때문에 10000C3은 = (10000 * 9999 * 9998) / 3!입니다. 따라서, 3중 for문 이용하여 모든 경우의 수에 대해 합이 0이 되는지 확인하는 경우 시간 초과가 발생할 수 있습니다. 두 수 A, B를 선택한 후 (A + B) * -1이 몇개인 지 찾으면 됩니다. ⚠️ 10000C3이므로 주어진 코딩 실력..

[백준 2467번] 용액 (C++)

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 용액문제는 이분탐색을 이용하여 해결할 수 있습니다. 문제에서 N이 최대 100,000이므로, O(N2)의 알고리즘을 사용하는 경우, 시간초과가 발생할 수 있습니다. 문제에서 용액의 특성값이 주어지고, 두 용액을 혼합했을 때, 0에 가장 가까운 용액을 만들어내는 두 용액을 찾아야 합니다. 첫번째 용액의 특성값이 10,000일 때의 그래프는 아래와 같습니다. (X축은 두번째 용액의 특성값, Y축..

[백준 18869] 멀티버스 2 (C++)

https://www.acmicpc.net/problem/18869 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 멀티버스 2 문제의 해결 방법은 2가지가 있습니다. 정렬을 이용한 방법 먼저, 첫번째 방법은 아래와 같습니다. 문제에서는 아래와 같은 조건을 만족하면, 두 우주가 균등하다고 합니다. Ai Aj → Bi > Bj 따라서 대소 관계가 동일하면 두 우주가 균등하다고 할 수 있습니다. 먼저, 두 우주 A, B를 정렬하고, 정렬 후..

[백준 16401번] 과자 나눠주기 (C++)

https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 과자 나눠주기 문제는 Parametric Search를 이용하여 해결할 수 있습니다. Parametric Search는 최적화 문제를 결정 문제로 변환해 이분탐색을 수행하는 방법을 의미합니다. - [바킹독의 실전 알고리즘] 이분탐색 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하는 문제(최적화 문제)에서..