n크기의 배열 arr이 주어지고 k번째 항목까지의 합을 구하는 코드는 아래와 같이 간단히 구현할 수 있다. sum = 0 for i in range(1, k+1): sum += arr[i] print(sum) i번째 항목까지의 합을 구하는 코드는 1부터 k번째까지의 항목을 탐색하며 한 번씩 합 연산을 실시하므로 시간 복잡도가 O(N)이다. 나쁘지 않은데? 그런데 배열 길이가 106, 테스트 케이스가 103개가 된다면 어떨까. 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicp..

시간 제한 메모리 제한 2초 128MB 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림(생략)과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로(생략)가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는..

9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net IDEA 코드가 문제에 그대로 제시되어있어서 그대로 해봤다. w(11,11,11)만 해도 구하는데 몇분 걸린다. 이런 재귀호출의 경우 똑같은 매개변수로 호출된 메소드가 엄청나게 많다. 그럼 첫 호출에 어떤 값에 대한 정보를 기억해두면 두번째부터 불필요한 호출은 줄일 수 있다. 이렇게 여러번 호출될 값을 미리 저장해놓고 다음 호출에 저장된 값을 바로 출력해주는 방법을 메모이제이션 이라고 한다. 간단히 3차원 배열로 구현했다. CODE using System; clas..