programmer life guidance 101

Kadane Algorithm 카데인 알고리즘 [6, -1, 5, -3, 9] 와 같은 수열이 있다고 하자. 이 때 각 수들을 더했을 때 가장 큰 수가 나오는 연속된 부분합을 찾는 알고리즘을 카데인 알고리즘 이라고 한다. 풀이의 핵심 순서는 이러하다. 수열의 각 요소를 하나씩 더하기 더한 값을 변수에 저장 더한 값이 마지막에 저장해놓은 변수보다 크다면 변수를 대입 자바 코드로 보자 int nums = {6, -1, 5, -3, 8}; int getMaximumSubArray(int[] nums) { if (nums.length == 1) { return nums[0]; } int maxNum = Integer.MAX_VALUE; int sum = 0; // 1. 배열 요소를 하나씩 탐색하면서 값을 넣어본..

www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 2731 1034 676 35.900% 문제 고객이 두 종류의 피자 A와 B를 취급하는 피자가게에서 피자를 주문하고자 한다. 과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자조각으로 나누어져 있다. 각 조각에 쓰여진 숫자는 피자조각의 크기를 나타낸다. 고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 ..

www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 0.5 초 128 MB 22578 10974 7243 49.620% 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에..