일지 & 개발

문제 요약알고리즘 분류: 누적합, 문자열난이도: Medium문제내용:garbage 배열: 각 집의 쓰레기 종류 ('M', 'P', 'G')를 나타냄.travel 배열: 집 간 이동 시간 제공.각 트럭은 특정 쓰레기  ('M', 'P', 'G') 유형만 수거함.트럭은 집 0번에서 시작하며 필요한 집만 방문 가능.모든 쓰레기를 수거하는 데 필요한 최소 시간을 계산하여사이트 주소: https://leetcode.com/problems/minimum-amount-of-time-to-collect-garbage/description/ 문제풀이 이번 문제는 O(N)만큼 요구하는 문제이다. 그래서 누적합으로 풀어야한다. 누접합 관련 내용은 아래글에서 확인 해보면 된다.https://jih3508.tistory.com..

문제 요약 알고리즘 분류: 구간합, 누적합, 수학 난이도: Gold5 문제내용: N × M 보드판에서 K × K 크기인 보드로 잘라서 다시 색칠한다. 최소한의 칠해야 하는 개수를 구해라 사이트 : https://www.acmicpc.net/problem/25682 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제풀이 이번 문제는 데이터의 개수가 최대 2000 × 2000이고 제한시간이 1초라서 완전 탐색으로 하면 시간이 초과된다. 그래서 2차원 배열 구간합을 응용해야 된다. 구간합에 대한 이론은 아래의 사이트에 참조하면 된다. https://jih..

문제 요약 알고리즘 분류: 구간합, 누적합, 수학 난이도: Gold3 문제내용: N개 수와 연속적인 구간의 합이 M인 개수를 구해하 사이트 : https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제풀이 이번문제는 구간합에서 응용한 문제이다. 구간합에 대한 이론은 아래의 사이트에 참조하면 된다. https://jih3508.tistory.com/50 [알고리즘 이론] 구간합, 누적합(prefix su..

문제 요약 알고리즘 분류: 구간합, 누적합, 수학 난이도: Silver1 문제내용: 2차원 배열을 주고 (x1, y1) ~ (x2, y2)의 합을 구해 사이트 : https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제풀이 이번문제는 2차원 배열의 누적합의 기본 문제이다. 누적합, 구간합에 대한 설명은 밑에 사이트에 참조하면된다. 밑에 사이트에 2차원 배열 누적합, 구간합을 이해하고 예제 코드에서 몇개만 ..

문제 요약 알고리즘 분류: 구간합, 누적합, 수학 난이도: Silver1 문제내용: 문자열 S가 주어지고 각 테스트케이스 마다 문자와 인덱스 시작점과 끝을 준다. 문자열에서 시작점과 끝사이에 문자 몇개 있는지 출력해라 사이트 : https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 문제풀이 이번문제는 두가지 경우가 있는데 50점짜리는 각 시작점 부터해서 끝지점까지 탐색해서 해당되는 문자 몇개인지 출력..

알고리즘 분류: 구간합, 누적합, 수학 난이도: Silver3 문제내용: 전체 날짜 수 N과 연속적인 날짜의 수 K와 전체 날짜를 준다. 연속적인 K일 온도의 합중 가장 큰것을 구해라 사이트 : https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제풀이 이번 문제는 누적합, 구간합 기본 문제이다. 개념이나 이론적인 설명은 아래에 사이트에 참조 하면된다. https://jih3508.tistory.com/50 [알고리즘 이론] 구간합,..

이론 1차원 배열 누적합 누적합부터 먼저 설명하면 0번째 인덱스 부터 N 번째 인덱스까지 탐색하면서 인덱스 i일때 0번째 인덱스 부터 0번째 인덱스합을 말한다. Python array = [1, 8, 7, 4, 3, 5, 6] n = len(array) prefix_sum = [0] * n for i in range(n): for j in range(i+1): prefix_sum[i] += array[j] Java import java.util.Arrays; public class Main { public static void main(String[] args){ int[] array = {1, 8, 7, 4, 3, 5, 6}; int n = array.length; int[] prefix_sum = n..