Dev_Diary

https://www.acmicpc.net/problem/11842차원 부분합 문제입니다.2차원 부분합 리스트의 값 subsum[i][j] 는 nums[0][0] ~ nums[i][j] 의 모든 수를 더한 값과 같습니다.그리고 nums[i][j] ~ nums[k][l] 까지의 합을 구하는 방법은 전체에서 부분을 빼고 겹치는 부분을 더해주는 방식으로 진행되는데 구체적으로는subsum[k][l] (전체)- subsum[k][j-1] (세로방향의 부분)- subsum[i-1][l] (가로 방향의 부분)+ subsum[i-1][j-1] (세로방향의 부분과 가로방향의 부분이 겹치는 부분) 입니다. 해당 방법을 사용해 이번 문제를 풀 수 있습니다. 우선 주어진 이익들로 부분합 리스트를 완성한 뒤 모든 겹치게 될 꼭..

https://www.acmicpc.net/problem/2143부분합 문제입니다. 단순히 부분합 리스트를 만들고 부분합 / 부분합 쌍을 찾으면 간단히 생각해도 최악의 경우 1000개의 데이터에서 4중 반복문을 돌아야 하기 때문에 다른 방법을 찾아야 합니다. 우선 각 부분합 리스트에서 2중 반복문을 통해 모든 부 배열 합을 기록해줍니다. 데이터 기록을 할 때 딕셔너리와 리스트 중 선택할 수 있는데, 딕셔너리는 일반적으로 시간을 위해 공간을 포기한 경우로 해당 문제에서 딕셔너리에 모든 부 배열 합을 기록하면 메모리초과가 발생합니다. 그러므로 리스트에 기록하도록 합니다. 기록 중 이분 탐색을 통한 빠른 검색을 위해 정렬을 해주어야 하는데, 이분탐색을 활용한 정렬인 bisect.insort 함수를 사용할 수 ..

https://www.acmicpc.net/problem/3673우선 리스트를 부분합 리스트로 치환해줍니다. 연산 시 걸리는 시간을 줄이기 위함입니다.그 뒤에 'd 로 나누어 떨어진다' 의 부분을 쉽게 풀어 볼 생각을 해야합니다.조건에서 데이터의 크기는 최대 50000 개인데 해당 데이터를 2중 반복문으로 순회하면 시간 초과가 발생하기 때문입니다. 결론적으로, 어떠한 두 수 A, B의 차가 d 로 나누어 떨어지려면 A 를 d 로 나눈 나머지와 B 를 d 로 나눈 나머지가 같으면 됩니다. A = ad + q, B = bd + p 라고 가정하겠습니다.A - B = d(a-b) + (q - p) 입니다.A - B 가 d 로 나누어 떨어지려면 모든 인수가 d 로 나누어떨어지면 됩니다.d(a-b) 는 이미 d 의..