Jang's coding blog

# 백준 11003번 링크 N개의 수 A1, A2, ..., AN과 L이 주어진다.Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net Key point 슬라이딩 윈도우 기법을 사용하여 하나씩 밀면서 비교한다 deque에 하나씩 넣어 현재 deque에 남은 숫자와 비교하여 더 작으면 보관한다 문제의 범위가 넘어가면 popleft를 사용하여 deque에서 뺀다. 문제 코드 from collections import deque N,L = map(int ,input().split()) A=list(map(int ,input().split())) mydeque= deque(..

# 백준 1543번 문제검색 링크 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net Key point 투 포인트 알고리즘을 사용한다. 앞에서부터 하나씩 target으로 잡고 조건이 성립되는지 확인한다. 문제 코드 import sys input= sys.stdin.readline N=int(input()) numbers=list(map(int, input().split())) numbers.sort() cnt=0 for i in range(N): #앞에서부터 하나씩 확인 find=numbers[i] start=0 end=N-1 while s..

# 백준 10986번 문제검색 링크 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net Key Point (A+B)%C는 ((A%C)+(B%C))%C와 동일하다 결국 이 말은 특정 구간의 나머지 연산을 더해 구한 값과 구간합의 나머지 연산의 결과는 동일하다는 것이다 합배열 (sum[j]-sum[i])%M 은 결국 sum[j]%M - sum[i]%M과 동일함으로 결국 sum[j]%M=sum[i]%M의 결과가 나오게 된다 즉 합배열간 나머지가 동일한 것의 조합을 더해주면 된다. 기본적으로 구간합이 나머지가 0인경우도 더해준다 문제 코드 import sys input=sys.stdin..

# 백준 11660번 문제검색 링크 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 www.acmicpc.net Key Point 합배열을 만드는 방법은 sum_array[i][j]= sum_array[i-1][j]+sum_array[i][j-1]-sum_array[i-1][j-1]+numbers[i][j] 이다. *그림을 그려보면 이해하기 편하다 문제의 구간의 합을 구하기 위해서는 sum_array[x2][y2]-sum_array[x1-1][y2]-sum_array[x2][y1-1]+sum_array[x1-1][y1-1]의 공식을 사용하면..

# 백준 11659번 문제검색 링크 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. www.acmicpc.net Key Point 합배열을 미리 만들어서 큰 범위 - 작은 범위를 계산하는 방식으로 문제를 해결하면 되는 문제이다 문제 코드 import sys input=sys.stdin.readline N,M=map(int ,input().split()) sum_array=[0] numbers= list(map(int, input().split())) #숫자들을 담은 리스트 생성 for i in numbers: #합배열 생성 코드 tmp=i+sum_array[-1] sum_array.append(tmp) for _ in range(M): # 큰범위 - 작은범위 계산..

# 백준 2012번 등수매기기 문제 링크 2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. www.acmicpc.net 문제해설 이 문제는 그리드 문제이며 간단하게 생각해보면 기대등수를 오름차순으로 정리하여 실제 등수를 배정하게 되면 불만도의 합은 최소가 되게된다. 입력값이 커지게 되면 시간초과가 발생함으로 sys.stdin.readline을 사용하여 시간을 줄여주는것이 필요하다. import sys input=sys.stdin.readline #시간초과 방지 n=int(input()) rank=[] #각..

# 백준 1543번 문제검색 링크 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 문제해설 이번 문제에서는 입력받는 값이 항상 영어이므로 비교하는값도 영어라는점을 이용하여 replace함수를 사용하여 겹치는 부분을 '0'으로 바꾸는 반복문을 사용하여 총 몇번 바꾸는지 출력하는 코드를 만들었다. sen=input() #전체 문자열 입력받기 tmp=input() #찾을 문자열 입력받기 cnt=0 while True: #전체 문자열에 찾을 문자열이 없을때까지 비교 if tmp not in sen: break sen=sen.replace(tmp..