본문 바로가기

분류 전체보기142

파이썬) 백준 알고리즘 | 1912번 : 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net dp를 이용하면 쉽게 풀 수 있는 문제입니다. 연속되는 수열의 최대 합이기 때문에 처음부터 더하다가 중간에 큰 수가 나오면 이전까지 더한 것을 버리면 됩니다. n = int(input()) seq = list(map(int, input().split(' '))) dp = seq for i in range(1, n): dp[i] = max(dp[i-1]+dp[i], dp[i]) print(max(dp)) 2022. 6. 30.
파이썬) 백준 알고리즘 | 11726번 : 2×n 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net dp문제입니다. 경우의 수를 계산하다보면 규칙성이 보이는데 이 문제에서는 앞에 두 개의 항을 더하는 것이 규칙입니다. n = int(input()) dp = [0] * (n) if n == 1: print(1) else: dp[0] = 1 dp[1] = 2 for i in range(2, n): dp[i] = dp[i-1] + dp[i-2] print(dp[n-1] % 10007) 2022. 6. 30.
파이썬) 백준 알고리즘 | 16120번 : PPAP https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net pseudo code A를 처리하는게 핵심입니다. stack = deque() for i=1 to {len sentence} do stack.append(sentence[i]) if sentence[i] == A then A주변의 문자열을 조사해서 PPAP인지 확인한다 if PPAP then stack에 있는 PPAP에서 P만 남긴다 else break if stack == 'P': print("PPAP") else: pirnt('NP') *제가 .. 2022. 6. 30.
파이썬) 백준 알고리즘 | 2670번 : 연속부분최대곱 https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 백준 2670 '연속부분최대곱' 문제입니다. 처음에 그냥 곱하는 모든 경우의 수를 구했었는데 시간초과가 떠서 리스트에 곱해서 저장을 하였습니다. 예를 들어 입력으로 1,2,3,4,5 이렇게 들어온다면 리스트에는 1,1,2,6,24,120 이런 식으로 들어가게 만들고 인덱스를 이용해서 j번째를 i번째로 나눠준다면 i+1부터j까지의 곱이 됩니다. 그런데 중간에 0이 들어가게 된다면 0이후.. 2022. 6. 28.

티스토리툴바