시간 제한 메모리 제한 2 초 128 MB 문제 (링크) https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 나의 풀이 import sys import math n = int(sys.stdin.readline()) # n이하의 수 중 소수를 찾아줄 배열 (에라토스테네스의 체) prime_checker = [True for _ in range(n+1)] # 소수가 아닌 0과 1에 대해 별도의 False처리 prime_checker[0:2] = False for i in range(2, int(math.sqrt(n)) + 1): if prime_checker[i]: j ..
투 포인터 알고리즘
시간 제한 메모리 제한 0.5 초 128 MB 문제 (링크) https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 나의 풀이 import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) end = 0 intervalSum = arr[0] ans = float('inf') for start in range(..
문제 (링크) https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 나의 풀이 import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) intervalSum = arr[0] # m과 비교할 start ~ end까지 더한 값들 cnt = 0 # start ~ end == m 일..
투 포인터 알고리즘은 주로 수열의 연속된 값들의 합을 다룰 때 사용되는 알고리즘이다. 여기서 두 개의 포인터란 말 그대로 시작점과 끝 점을 포인터로 잡아 해당 포인터들이 움직이면서 동작을 수행해준다. 백문이불여일견. 이미지로 한 번 살펴보자 동작 방식 우리가 배열에서 연속된 값의 합이 5가 될 때의 경우를 찾고 싶다고 가정해보자. 물론 반복문을 두 번 중첩시켜 모든 배열의 값들에 대해 완전탐색을 진행할수도 있지만, 그러한 방식은 O(n^2) 만큼의 시간이 소요된다. 배열이 커지면 커질수록 연산시간은 기하급수적으로 증가할 것이다. 따라서 사용되는 방식이 이 글에 포스팅하는 투 포인터 방식이다. 앞서 설명한 것과 마찬가지로, 투 포인터 방식에선 start와 end라는 두 개의 포인터를 정의해준다. 처음엔 두..
