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..

*투 포인터 특징 말 그대로 시작점, 끝점 두개의 위치를 지정하여 리스트를 탐색하는 방법 O(n)의 시간복잡도를 가지고있음 *투 포인터의 이동 원칙 sum > N : sum-=start; start++; sum < N : end++; sum+=end sum == N: sum+=end; cnt++ *예제 문제(백준 2018 수들의 합 5) # 백준 2018번 문제검색 링크 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. www.acmicpc.net *문제 코드 N=int(input()) start=1 en..

# 백준 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): # 큰범위 - 작은범위 계산..

*DFS (깊이 우선 정렬) 그래프 완전 탐색을 위한 구현 재귀함수, 스택 자료구조로 구현가능 시간복잡도 = O(V+E) 여기서 V=노트 수, E= 간선 수 #백준 11724 DFS예시 코드 import sys sys.setrecursionlimit(10000) input= sys.stdin.readline def dfs(v): visited[v]=True for i in graph[v]: if not visited[i]: dfs(i) N,M = map(int, input().split()) graph=[[] for _ in range(N+1)] visited=[False]*(N+1) for _ in range(M): u,v= map(int, input().split()) graph[u].append(v..

*구간 합 알고리즘이 필요한 이유 구간마다 합을 매번 계산하게 되면 계산해야하는 양이 많아지면 시간초과가 발생할 수 있다. 실제 코딩테스트에서 사용 빈도가 많이 높다 *구현 원리 합배열을 미리 만들어 놓으면 큰 구간에서 작은 구간을 빼면 두 구간 사이의 합이 나옴을 이용 ex)1번부터 3번까지의 합은 sum[3]-sum[1]임을 이용 *구현 방법 입력받은 숫자의 합배열을 생성한다 합배열에서의 특정 구간을 값을 S[j]-S[i-1]로 계산한다. *구현 코드 #예시문제 백준 11659번 import sys input =sys.stdin.readline N,M= map(int ,input().split()) #숫자의 수 N, 구간 합 출력 수 M 입력 numbers=list(map(int, input().sp..

[LV2] 두 큐 합 같게 만들기 길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다 www.programmers.co.kr 문제 해설 이번 문제는 문제에서 설명하는 것처럼 큐를 사용해서 서로의 크기가 같아질 때까지 삽입과 추출하는 반복문을 돌려서 두 큐의 합이 같아질지 판별하면 되는데 여기서 중요한 점은 판별을 할 때의 범위를 정해야 한다. 이때 이 범위는 큐의 길이의 3배만큼 돌리게 되면 모든 경우의 수를 반복해볼 수 있기 때문에 ..

[LV2] 더 맵게 문제링크 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 www.programmers.co.kr 문제 해설 이번 문제는 heapq을 사용하여 최솟값을 항상 인덱스 0번에 위치시켜 조건에 맞는 식에 대입하여 다시 heapq에 넣어준 후 비교하면 되는 문제이다. import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) # 주어지는 맵기 리스트 heapq형태로 변환 while scoville[0] < K: tmp= heapq.heappop(scoville)+heapq.heappop(s..