두 포인터

문제 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 풀이 두 포인터 문제이다. 두 포인터를 이용하여 start를 포함하며 반복되는 수가 없는 수열의 경우의 수를 계산하는 방식으로 해결한다. start부터 중복되는 수가 없을 때까지 end를 늘린다. 혹은 end가 N까지 도달하여 더 이상 수열을 늘릴 수 없을 때까지 늘린다. start에서 end까지 start를 포함하여 만들 수 있는 수열의 개수는 end - start개이다. 이 개수를 answer에 추가한다. 그 다음, start를 앞으로 늘려서 1번부터 반복한다...

문제 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 정렬, 두 포인터 문제이다. 먼저 용액을 두 포인터를 위해 정렬한다. 배열에서 세 용액 중 하나를 0에서부터 N - 1까지 선택한다. 선택한 용액 뒤의 배열에서 두 포인터를 실시하여, 선택한 용액과 start, end에서의 용액의 합의 절대값이 0과 가장 가까운 용액을 답으로 한다. 시간 복잡도는 O(N * N)으로 N은 5000이하이므로 시간초과는 발생하지 않는다. 코드 #include #include #include #incl..

문제 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 풀이 두 포인터, 슬라이딩 윈도우 문제이다. 라이언의 인덱스를 따로 벡터에 저장한다. 벡터의 길이가 K보다 작은 경우 집합을 만들 수 없다. 크기가 K로 고정된 슬라이딩 윈도우 방식으로 벡터를 순회하면서 집합의 최소 크기를 탐색한다. i에서 부터 i + K - 1까지의 원소의 수는 K개이다. lion[i + K - 1] - lion[i] + 1이 lion[i]를 첫 요소로하며 크기가 K인 집합의 크기이다. 코드 #include #include #incl..

문제 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 풀이 수학, 두 포인터 문제이다. 몸무게는 0에서 시작할 수 없고, 현재 몸무게는 기억한 몸무게보다 커야 한다. 기억한 몸무게와 현재 몸무게를 두 포인터, start = 1, end = 2로 설정한다. 현재 start와 end일 때의 G를 current라고 할 때, current가 G 이하일 경우 end를 증가시켜 현재 몸무게를 더 늘려야 한다. 코드 #include #include using namespace std; int main() { ios_base::sync_..

문제 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 풀이 정렬, 두 포인터 문제이다. 입력받은 수열을 정렬한다. start와 end를 0에서부터 시작한다. start와 end에서의 수의 차이가 M이상이라면 답을 갱신한다. 차이를 더 줄이기 위해 start를 증가시킨다. 미만이라면 차이를 더 늘리기 위해 end를 증가시킨다. 코드 #include #include #include using namespace std; int nums[100000]; int main() { ios_base::s..

문제 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 브루트포스 알고리즘, 두 포인터, 슬라이딩 윈도우 문제이다. 두 포인터는 구간의 넓이가 유동적으로 변하고, 슬라이딩 윈도우는 구간의 넓이가 고정적이다. 현재 문제에서 회전 초밥은 연속으로 k개 집어야 하므로 구간이 고정적이기 때문에 슬라이딩 윈도우로 풀어야 한다. 슬라이딩 윈도우 방식에서 구간을 한칸 옮겼을 때, 모든 구간을 다시 검사하는 것 보다 변한 구간. 즉, 맨 왼쪽과 맨 오른쪽만 계산하는게 더 빠르다. ..

문제 풀이 두 포인터 문제이다. start와 end를 0에서부터 시작하여, end의 수는 수열에 추가하고, start의 수는 수열을 추가할 수 없을 때 수열에서 제거하는 방식으로 start와 end를 증가하거나 감소시킨다. 원본 수열을 nums라고 하면, nums[end]는 현재 부분 수열에 추가하려는 수이다. nums[start]는 수를 추가할 수 없을 때, 부분 수열에서 제거하는 수이다. 코드 #include #include using namespace std; int nums[200'000]; int num_count[100'001]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int N, K; cin >> N..

문제 풀이 두 포인터, 문자열 문제이다. 두포인터와 재귀 함수로 해당 문자열이 팰린드롬인지 판별한다. 현재 start와 end에서의 문자가 맞지 않다면 start + 1과 end까지와 start부터 end - 1까지 문자열을 확인하도록 함수를 재귀한다. 이미 문자가 맞지 않은 상태에서, 다시 start와 end의 문자가 맞지 않다면 회문이나 유사회문이 아니다. 코드 #include #include #include using namespace std; // 투 포인터로 양 옆에서 접근하며 팰린드롬을 체크한다. int solution(string current, int start, int end, int in_diff_count) { int diff_count = in_diff_count; while (st..

문제 풀이 이분 탐색 사용 조각을 하나 선택하고 나머지 조각의 길이가 (필요한 길이 - 선택한 조각 길이)라면 문제에 만족된다. 선택한 조각과 맞는 조각을 찾을 때 이분 탐색을 실시한다. 두 포인터 사용 양 옆에서부터 좁혀가며 검사한다. start와 end에서의 조각의 길이의 합이 필요한 길이와 같다면 문제에 만족된다. 코드 이분 탐색 사용 #include #include #include using namespace std; vector legos; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int x, n; while (cin >> x >> n) { x *= 10'000'000; for (int i = 0; i <..

문제 풀이 모든 합을 저장하여 이분 탐색으로 진행할 경우, 자기 자신이 합에서 사용되었는지 알 수 없기에 사용할 수 없다. unordered_map 사용 모든 합을 피연산자와 함께 unordered_map에 저장한다. input이 unordered_map에 있는지 확인하고, 피연산자로 자기 자신이 사용되었는지 확인한다. 두 포인터 사용 입력된 수열을 정렬하고 양 옆에서 두 포인터 알고리즘을 시작한다. 같은 수가 합에 사용되면 안 되므로 start < end일 때까지만 반복한다. 자기 자신은 합에 포함되면 안 되므로 start와 end를 조정 코드 unordered_map 사용 #include #include #include #include using namespace std; vector inputs; ..