반응형 투 포인터3 BOJ 16637 : 괄호 추가하기 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/16637 첫 번째 예시를 보자. 연산자는 + * - * 로 총 4개이다. 순서대로 1, 2, 3, 4번째 연산자로 정의하자. 먼저 괄호 안에는 연산자가 하나만 들어있어야 하므로, 1번 연산자에 괄호를 만들면, 2번 연산자는 괄호가 불가능하다. → (3 + 8) * 7 - 9 * 2 따라서 DFS로 아래의 경우의 수가 되도록 만든다. 0 0 0 0 → 괄호가 없는 경우 0 0 0 1 → 4번 연산자에만 괄호를 만든 경우 0 0 1 0 0 1 0 0 0 1 0 1 → 2번, 4번 연산자에 괄호를 만든 경우 1 0 0 0 1 0 0 1 1 0 1 0 1 2 3 .. 2021. 4. 5. BOJ 1644 : 소수의 연속합 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1644 N이 4,000,000으로 매우 크므로, 매번 소수를 판단하는 것은 비효율적이다. 따라서, 소수의 판단은 에라토스테네스의 체를 이용한다. int N; int prime[4000000 + 50000]; int primeSet[4000000 + 50000]; int pcnt; void eratos() { prime[1] = 1; for (int i = 2; i * i 2021. 4. 2. BOJ 2467, 2470 : 두 용액 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2467 www.acmicpc.net/problem/2470 BOJ 2467은 입력이 정렬이 되어서 들어오는 차이가 있다. 그 외 풀이는 BOJ 2470과 같다. B형에서 어떤 조건을 만족하는 값을 찾으려면 대부분 정렬을 한 후, 이분 탐색으로 찾는다. 이분 탐색 외에도 답을 찾는 테크닉 중 하나가 투 포인터 알고리즘이다. 포인터(index) 2개를 이용하여 효율적으로 원하는 답을 찾는다. 두 용액 문제는 모든 배열의 값 2개 중 합이 0에 가까운 값 2개를 찾는다. 용액이 모두 양수라면 가장 작은 두 값이, 모두 음수라면 가장 큰 두 값이 답이 된다. 문제는 양수와 음수가 있는 경우이다. 이 경우는 가장 작은 값과 가장 큰 값을 더해보.. 2021. 3. 29. 이전 1 다음 반응형
