알고리즘(Problem Solving) 공부 블로그 알고리즘(Problem Solving) 공부 블로그

부분합

• 백준 10986번: 나머지 합

  다이나믹프로그래밍(DP) 2018. 7. 1. 19:20

  https://www.acmicpc.net/problem/10986 1. 문제수 N개 A1, A2, ..., AN이 주어진다. 이 때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 2. 알고리즘키워드 - DP, 부분합참고 - https://www.slideshare.net/Baekjoon/baekjoon-online-judge-10986 3. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #..

  Read More
• 백준 11441번 : 합 구하기

  다이나믹프로그래밍(DP) 2018. 6. 18. 14:50

  https://www.acmicpc.net/problem/11441 1. 문제 N개의 수 A1, A2, ..., AN이 입력으로 주어진다. 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 2. 알고리즘 키워드 - 부분 합최초의 입력 받은 배열은 위 처럼 10, 20, 30, 40, 50 으로 이루어 져있는 배열이다. 배열의 부분합을 만들기 위해 0 번째 배열을 추가하고 배열[i-1] + 배열[i] 부분 합을 구한다. 문제 에서 1번과 4번 배열의 합을 구하라고 나와 있다. 1번 부터 N 까지는 모두 계산이 되어 있음으로 위와 같이 답을 도출 할 수 있다. 두번 째 예제에서는 2번 부터 4 까지의 합을 계산 해야 한다.2번 의 부분합은 30 임으로 ..

  Read More
• 백준 2670번 : 연속부분최대곱

  구현(Implementation) 2018. 6. 17. 10:34

  https://www.acmicpc.net/problem/2670 1. 문제 요약 N 개의 양의 실수가 있을 때 한개 이상의 연속된 수들의 곱이 최대값을 출력하는 문제 2. 알고리즘 O(N^2) 으로 풀었다. 반복문을 선언해서 현재 원소에서 다음 원소까지 모든 곱을 구하여 가장 큰값을 반환 하도록 하였다. DP 를 사용하면은 O(N) 으로 풀수 있다고 한다. float, double 출력시 자리수 출력에 유의하자. 3. 코드 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include #include using namespace std; int main() { std::ios::sync..

  Read More