Patrick's Devlog

1. 누적합누적합은 앞에서부터 차례대로 누적된 합을 구하고 이를 이용해 구간 합을 구할 수 있다.2. 문제크기가 N인 정수 배열 arr가 존재할 때 다음과 같은 연산을 M번 수행해야하는 문제가 존재한다. - 구간 l, r(l l부터 r까지를 구하기 위해, 반복문을 통해 단순히 구하게 된다면 시간 복잡도는 O(NM)이 나오게 된다. 여기서, 누적합 아이디어로 변경해보자.sum[i] = arr[1] +... + arr[i], sum[0] = 0으로 정의하고, l부터 r까지의 합은 sum[r] - sum[l - 1]과 동일하다.sum[r] = arr[1] + ... + arr[r], sum[l - 1] = arr[1] + ... + arr[l-1] 으로 정의되므로, 따라서 sum[r] - sum[l - 1]은..

1. 개요https://www.acmicpc.net/problem/75761-1. 설명철수의 토마토 농장에는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자 칸에 하나씩 넣어 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게된다. 하나의 토마토에 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선에 있는 토마토들에게는 영향을 주지 못하고, 토마토 혼자 저절로 익는 경우는 없다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고싶어 한다...

1. 개요https://acmicpc.net/problem/36871-1. 설명 성냥개비로 위와 같은 숫자를 만드려고한다. 성냥개비의 개수가 주어졌을 때, 성냥 개비를 모두 사용해 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성한다.1-2. 제한 사항- 첫 줄에 테스트 케이스 개수가 주어지며, 최대 100개- 각 테스트 케이스는 한줄로 이루어져 있고, 성냥개비 개수 n이 주어짐- n 은 2 이상 100 이하의 자연수- 각 테스트 케이스에 대해 입력으로 주어진 성냥 개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 출력2. 구현2-1. 풀이큰 수는 자릿수가 많을수록 커지므로, 1과 7을 이용하여 만든다. 1은 2개, 7은 3개로 다른 숫자들은 4개 이상이므로 1과 7을 이용하면 된다..