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

배열

• 백준 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
• 백준 2578번 : 빙고

  배열(Array) 2018. 6. 17. 13:15

  https://www.acmicpc.net/problem/2578 1. 문제 요약 5x5 칸의 빙고의 계수가 3개가 되면 횟수를 출력하는 문제 2. 알고리즘 입력 받은 수가 있다면 0 으로 초기화 한다. 1개의 빙고가 완성 된것을 의미한다. 가로 방향 빙고 검사 코드를 추가 한다. 1234567891011for(int i=0; i

  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
• 프로그래머스 Level1: 나누어 떨어지는 숫자 배열

  정렬(Sort) 2018. 6. 14. 17:47

  https://programmers.co.kr/learn/courses/30/lessons/12910 1. 문제 요약 입력되는 정수와 나눗셈 값으로 나누어 지는 값을 array 배열에 넣어 반환 하는 문제 2. 알고리즘 배열을 정렬 한다. 나누어서 나머지가 0 인 수만 array 에 담는다. 3. 코드 12345678910111213141516171819202122#include #include #include using namespace std; vector solution(vector arr, int divisor) { vector answer; sort(arr.begin(), arr.end()); const int size = arr.size(); for(int i=0; i

  Read More