본문 바로가기
728x90

연속합

[백준알고리즘] 1912번: 연속합 -C++ [백준알고리즘] 1912번: 연속합 -C++ 1912번: 연속합 (acmicpc.net) 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 주어진 수열에서 연속된 부분 수열을 뽑아냈을 때 가장 연속합이 큰 값을 구하면 된다. 예전에 파이썬으로 많이 풀었던 문제다. 그래서 그런가 이번에도 뭔가 아이디어가 쉽게 떠올랐다. 많이 인상 깊게 푼 문제였나 보다. [백준알고리즘] 1912번: 연속합 -Python (tistory.com) [백준알고리즘] 1912번: 연속합 -Python [백준알고리즘] 1912번: 연속합 -Pyth.. 더보기
[백준알고리즘] 2143번: 두 배열의 합 -Python [백준알고리즘] 2143번: 두 배열의 합 -Python https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다. www.acmicpc.net 이제 이런 문제는 간단한 것 같다... 나중에 또 시간이 지나서 풀려하면 어렵겠지만.. 문제에서 요구하는 것은 두 개의 배열 A, B에서.. 더보기
[백준알고리즘] 2632번: 피자판매 -Python [백준알고리즘] 2632번: 피자판매 -Python https://www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 ( 3≤m, n≤1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기 www.acmicpc.net 두 가지 방법으로 문제를 풀었다. 첫 번째 방법은 기존에 이런 유형의 문제를 풀기 위.. 더보기
[백준알고리즘] 1644번: 소수의 연속합 -Python [백준알고리즘] 1644번: 소수의 연속합 -Python https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 www.acmicpc.net 연속합 형태의 문제와 똑같이 풀어주나 소수를 구하는 과정이 추가된다. 다른 .. 더보기
[백준알고리즘] 1806번: 부분합 -Python [백준알고리즘] 1806번: 부분합 -Python https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net 이번 문제는 저번에 풀었던 2003번 수들의 합 문제와 유사했다. 다만, 여기서는 주어진.. 더보기
[백준알고리즘] 2003번: 수들의 합 2 -Python [백준알고리즘] 2003번: 수들의 합 2 -Python https://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 임을 나중에 보고 Python으로 포기하기도 했었다.. 결국 Python으로도 통과하긴 했다. 연속합을 직접 구해준 방법 더블 포인터를 사용해 값을 찾아간 방법 1번 방법 처음에는 1부터 I까지의 합에서 1부터 J까지의 합을 빼서 J부터 K까지의 값.. 더보기
[백준알고리즘] 1912번: 연속합 -Python [백준알고리즘] 1912번: 연속합 -Python https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2019-08-20 첫 번째 풀이 이번 문제는 LCS에서처럼 뻘짓을 하지 않아서 좀 빨리 풀렸다!!ㅎㅎ 주어진 수열에서 연속하는 부분 수열들 중 최대 합을 구하면 된다. 이번에는 단순히 max만 비교해서 유지했기 때문에 풀면서 딱히 배열을 사용하지 않았다. 풀면서 max_val이라는 전체에서 여태까지 구한 최대합을 나타내는 변수와 tmax라는 max_val을.. 더보기
728x90

티스토리툴바