[Coding Test]

[백준] 1912 파이썬(python) : 연속합

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 예제 1) 10 -4 3 1 5 6 -35 12 21 -1 10 6 9 10 15 21 -14 12 33 32 연속된 몇개의 수를 더해서 최대값을 출력하는것이 문제의 요구사항이니까 현재위치에서 음수가 나왔을때 이전 인덱스까지의 dp와 더할때 0 밑으로 내려가 음수가 되는지 확인해야 한다. 더한 값이 음수가 된다면 연속된 합을 유지할 수 없다. 하지만 더했을때 음수가 아니고 그 다음 위치의 값을 더해줌으로써 ..

[백준] 9461 파이썬(python) : 파도반 수열

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 숫자가 1 1 1 2 2 3 4 5 7 9... 순서로 진행되는데 i-3번째와 i-2번째 숫자를 더해서 i번째 숫자를 만들 수 있다. 점화식을 세우면 dp[i] = dp[i-3] + dp[i-2] 가 된다. import sys t = int(sys.stdin.readline()) for _ in range(t): #1 n = int(sys.stdin.readline()) #2 dp = [0]*(101)..

[백준] 1904 파이썬(python) : 01타일 - dp기초

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net dp의 대표적인 유형인 타일 문제이다. n이 입력되었을때 타일 00과 1을 이용하여 길이 n의 타일을 만들 수 있는 경우의 수를 구하는 문제다. dp를 사용하면 시간 복잡도 O(N)으로 해결할 수 있다. 타일은 1 과 00만 사용할 수 있으므로 n = 1일때는 1 -> 1가지 n = 2일때는 00 -> 1가지 n = 3일때는 001, 100, 111 -> 3가지 n = 4일때는 0011, 0000, 1..

[백준] 9184 파이썬(python) : 신나는 함수 실행

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net import sys def w(a, b, c): if a 20: #2 return w(20, 20, 20) if dp[a][b][c]: #3 return dp[a][b][c] if a < b < c: dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) return dp[a][b][c] #4 dp[a][b][c] = w(a-1, b, c) + w(a..

[백준] 24416 파이썬(python) : 알고리즘 수업 - 피보나치 수 1

https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net import sys n = int(sys.stdin.readline()) def fibo(n): if n == 1 or n == 2: return 1 return fibo(n-1) + fibo(n-2) def fibo_dp(n): cnt = 0 #1 dp = [0]*41 #2 dp[1], dp[2] = 1, 1 #3 for i in range(3, n+1): dp[i] = dp[i-..

[백준] 1520 파이썬(python) : 내리막 길 - dp+dfs

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net dp는 목적지에서부터 뒤로 가는 패턴 (0, 0)에서 (m-1, n-1)까지 가는 방법의 수를 구하는 문제인데 (m-2, n-1)에서 (m-1, n-1)까지 1가지 방법 밖에 없으니 dp[m-2, n-1]에는 1을 추가하는 방식으로 되돌아가면서 결국 dp[0][0]에 저장되는 값이 도착지점까지의 갈 수 있는 방법이 된다. import sys m, n = map(int, sys.stdin.readline..