누적합

오늘 기업 코테를 보았다. 누적합에 대해 2문제씩이나 출제가 되었다. 문제를 다 풀긴 했지만 효율성에서 어떻게 될지 모르겠다. 오늘 코테 풀이에 아쉬움이 남아서 누적합에 대해 다시 돌아보는 시간을 가져보자. 코테의 첫 번째 누적 합의 문제는 연속된 k개의 값들의 합 중에서 가장 큰 값을 출력하는 문제였다. 나는 해당 문제를 슬라이딩 윈도우 알고리즘으로 해결하였다. 슬라이딩 윈도우 알고리즘(Sliding Window Algorihtm)은 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 유용한 알고리즘이다. 예르 들어 정수로 이루어진 배열 {1, 4, 2, 5, 1}에서 길이가 2인 서브 배열의 합계가 가장 큰 서브 배열을 구할 때, 해당 알고리즘을 이용해서 해결한다. 슬라이딩 윈도우는 크기가..

2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 피자 A와 피자 B에서 나올 수 있는 피자 조각의 합 경우의 수를 각각의 딕셔너리에 저장한다. 하나의 피자에서 나올 수 있는 모든 경우의 수를 탐색한다. 하나의 피자에 존재하는 조각의 개수가 1000개 이하이므로 반복문 2개를 중첩하여 모든 경우의 수를 탐색하여도 시간 초과가 발생하지 않는다. 출력 딕셔너리_A [문제에서 요구하는 피자 사이즈] + 딕셔너리_B [문제에서 요구하는 피자 사이즈] + 딕셔너리_A [A에 있는 값] + 딕셔너리_B..