https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 내 코드 import sys input = sys.stdin.readline n, k = map(int, input().split()) temp = list(map(int, input().split())) window = sum(temp[:k]) ans = window for i in range(k, n): window += temp[i] - temp[i-k] if window > a..
https://www.acmicpc.net/problem/12847 12847번: 꿀 아르바이트 월세를 내기 바로 전 날 까지 인 n (1 ≤ n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다. 그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000) www.acmicpc.net 내 코드 import sys input = sys.stdin.readline n, m = map(int, input().split()) day = list(map(int, input().split())) window = sum(day[:m]) cnt =0 ans = window for i in range(m, n): window += day..
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 내 코드 n, m = map(int, input().split()) num = list(map(int, input().split())) cnt =0 left, right =0,1 while right
https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 내 코드 시간 초과된 코드 import sys input = sys.stdin.readline s, p = map(int, input().split()) dna =list(input().strip('\n')) a,c,g,t = map(int, input().split()) window = dna[:p] cnt =0 for i in range(p, len(dna)): wind..
https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 내 코드 import sys input = sys.stdin.readline n, m = map(int, input().split()) viewer = [0] + list(map(int, input().split())) if max(viewer) == 0: print('SAD') else: window = sum(viewer[:m]) answer = window cnt =1 for i in..
슬라이딩 윈도우 알고리즘이란 1,2,3,4,5 라는 숫자 배열이 있다. 이 안에서 A[i] + A[i+1] + A[i+2]라는 형식으로 연속적인 3개의 숫자 합을 구하려고 한다. [1,2,3],4,5 / 1,[2,3,4],5 / 1,2,[3,4,5] 이런 식으로 창문이 창틀을 따라서 미끄러지듯 일정한 크기의 윈도우가 틀을 만들어 이동하는 것을 볼 수 있다. 이러한 특성으로 인해, 크기가 n인 연속된 부분 합을 구하는 경우 자주 사용된다. 투 포인터와 슬라이딩 윈도우의 차이 두 알고리즘은 모두 부분 배열의 합(prefix sum)을 구하는 데 유용하게 사용된다. 투 포인터 구간의 길이를 가변적으로 잡는다. 구간의 양쪽 끝이 되는 포인터가 두 개 필요하다.(시작, 끝) 슬라이딩 윈도우 합을 구할 부분집합의 ..
https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 내 코드 import sys input = sys.stdin.readline from collections import deque n = int(input()) graph=[list(map(int, input().split())) for _ in range(n)] for k in range(n): for i in range(n): for j in range(n): if (graph[i][k] == 1 and graph[k][..
