원

https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 문제 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라. 라이언인형(=1)이 K개 이상인 연속의 그룹을 찾아야하는 문제이다. 완전탐색으로 해결할 경우 N의 제한이 10^6이기 때문에 시간초과가 발생하게 된다. 따라서 투 포인터로 조건에..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 투포인터로 범위를 넓혀가는 방식으로 구현해야한다. 단, 원소 하나로 S보다 크거나 같은 조건을 충족할 수 있기 때문에 시작할 때는 두 좌표 모두 0으로 시작해야한다. #include u..

https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 먹을 수 있는 초밥의 최대 가짓수를 구하는 문제인데 이벤트에 참여하여 K개의 연속 초밥을 먹었을 때 쿠폰 번호 C초밥을 먹지 않았다면 C초밥까지 더 먹을 수 있다. 가짓수를 구하는 문제인데 계속 다른 걸 구해서 뻘짓한 문제이다. 투포인터로 한 바퀴만 돌리는 로직으로 구현해보았다. visited변수를 통해 먹는 초밥의 개수를 저장해주었고 k개 구간에 해당..

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i > v[i]; } cin >> X..

https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 문제 정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. 출력..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 에라토스테네스의 체와 투포인터를 이용해서 해결해야하는 문제이다. 소수 찾는 알고리즘은 에라토스테네스의 체가 가장 효율적이기 때문에 사용했고, 연속 되는 부분의 합을 확인해주어야하기 때문에 투포인터를 사용했다. 그리고 소수 자기 자신이 연속된 수가 될 수 있기 때문에 생각을 해야할 게 2라는 소수는 연속된 수이면서 자기 자신이기 때문에 마지막에 예외처리를 해줘야 맞는다고 뜬다 #include #include #include #include #include #include #include #include #include..

https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 투포인터를 이용해서 할 수 있는 문제이다. 1. 맨 처음에는 시작점과 끝점을 둘다 idx 0으로 둔다 (왼쪽 포인터를 st, 오른쪽 포인터를 en이라 칭하겠음) 2. 조건에 맞게 en이 N보다 작으면서 아직 K개 이하로 등장했다면 오른쪽 포인터를 오른쪽으로 옮겨준다. 이걸 while반복문으로 조건에 걸릴 때까지 늘려준다. while(en < N && visited[v[en]] < K) { v..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 바로 전에 올렸었던 문제와 거의 동일한 문제이다. 투포인터로 사용하면 O(n)으로 해결이 가능하다. #include #include #include #include #include #include #include #include #include #include #define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) ..

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 문제 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장..