https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 일단 dp[i]의 값을 i를 제곱수들의 합으로 표현할 때 최소 개수로 정한다. 그렇게 되면 dp[i]의 값은 dp[1] + dp[i-1] dp[2] + dp[i-2] dp[3] + dp[i-3] . . . 위 값들 중 가장 작은 값이 된다. 처음엔 위 방식으로 이중 반복문을 돌려서 답을 구했으나 시간 초과가 발생했다. 시간을 더 줄일 수 있는 알고리즘을 사용..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속된 몇 개의 정수를 골라 합이 가장 큰 값을 구해야한다. 일단 가장 간단한 알고리즘을 생각해보면 이중 반복문으로 모든 연속된 부분 수열의 합을 구하는 것이다. 물론 이 방법으로 구현하게 되면 시간 초과가 발생한다. 조금 더 시간을 단축하는 알고리즘을 사용해야한다. 일단 기본적으로 dp[i]에 입력받은 수열의 인덱스 0부터 i까지의 부분 수열의 합을 저장한다. 이렇게 구하다가 어느 조건을 만족하면 인덱스의..

알고리즘 문제 풀이의 첫 번째 단계는 아마 모두 입출력 문제로 시작할 것이다. 그 중 조금 까다로워지는 부분이 "별 찍기 문제"이다. 출력 별 모습을 보여주고 해당하는 코드를 짜는 부분은 사실 조금 까다로울 뿐이지 어렵지는 않다. 그래도 이러한 문제를 풀 때마다 일관성을 유지하는 것이 좋을 것 같아서 나만의 별 찍기 문제 풀이 방법을 만들어보려고 한다. 일단 별 찍기 문제에 사용되는 기본적인 파이썬 문법을 정리해보려 한다. 1. 문자열 곱셈, 덧셈 파이썬에서는 문자열과 정수의 곱셈과 문자열끼리의 덧셈이 가능하다. 문자열과 정수의 곱셈은 정수의 개수만큼 문자열이 늘어난다. star = "*" print(star*5) 출력 ***** 공백 혹은 별을 연속해서 출력할 경우 곱셈을 사용해서 쉽게 구현할 수 있다..