https://www.acmicpc.net/problem/1593 투 포인터 문제라고 분류 했지만, 정확히는 슬라이딩 윈도우 문제다. 문자열 W의 순서를 바꾸어(순열) 만들 수 있는 문자열이 문자열 S에 몇 개 포함되어 있는지 카운팅하는 문제다. 가장 먼저 떠오른 방법은 W의 길이만큼 슬라이딩 윈도우를 진행하는 것이다.S의 문자열을 W의 길이만큼 잘라서(S') 정렬한 뒤 정렬된 W와 같은지 비교하는 것이다.어림도 없지. 시간 초과다. 작게 나마 시간을 줄여보려 했으나 안된다. 그래서 질문 게시판에서 힌트를 얻었고, 글자 수를 카운트 하는 아이디어를 얻었다.그러나 생각이 짧은 나머지,,, 문자열을 잘라서 각각의 문자 개수를 매번 계산했다.심지어 Counter 함수를 이용했는데 이러면 딕셔너리로 반환이 되기..
Algorithm/Two Pointer
https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 수학과 투 포인터 문제다. 성원이의 몸무게가 G 킬로그램 늘었다. 이 G킬로그램은 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다. 입력은 자연수로 들어오므로 모든 몸무게는 자연수다. 처음 생각한 방법은 어떤 수의 제곱에서 g를 뺀 수도 제곱수라는 점을 활용하는 것이다. 반복문으로 1부터 g까지 순회하면서 해당 수의 제곱에서 g를 빼고 그 수(tmp)가 제곱수 인지 확인했다. tmp가 ..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투 포인터와 누적 합 문제다. 주어진 배열에서 연속된 수들의 부분합 중에 s이상이 되는 수열 중, 가장 짧은 것의 길이를 구하는 문제다. 투 포인터를 사용하여 앞에서부터 포인터를 옮겨주며 해당 포인터들 사이의 누적 합 연산을 수행했다. 합이 s 미만이면 right 포인터를 한 칸 옮겨주어 합을 늘렸다. right 포인터가 끝에 다달았다면 반복문을 종료했다. (누적 합이 더 커질 수 ..
https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 투 포인터 문제다. 중복이 없는 수열의 시작과 끝 + 1을 투 포인터로 찾으려고 했다. 1 2 3 4 1 2 의 경우 start = 0, end = 4까지 연산을 거치고 이 때 1 / 1, 2 / 1, 2, 3 / 1, 2, 3, 4의 4가지 수열이 나온다. 2, 3 / 2, 3, 4 / 3, 4 등도 존재하지만 중복 계산을 방지하기 위해 start의 값을 포함하는 수열만을 계산했다. 방법은 금방 찾아냈..
