[Coding Test]/[백준]

[백준] 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..

[백준] 11053 파이썬(python) : 가장 긴 증가하는 부분 수열 - (★)

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net idx 1 2 3 4 5 6 dp[idx] 1 2 1 3 2 4 O(N2)알고리즘으로 푼 코드) import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) dp = [1]*1001 #1 for i in range(1..

[백준] 2156 파이썬(python) : 포도주 시식 - (★)

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net import sys n = int(sys.stdin.readline()) dp = [0]*10001 glass = [0]*10001 for i in range(1, n+1): glass[i] = int(sys.stdin.readline()) dp[1] = glass[1] #1 dp[2] = glass[1] + glass[2] #2 for i in range(3, n+1): #3 dp[i] = max..

[백준] 9019 파이썬(python) : DSLR - (★)

9019번: DSLR import sys from collections import deque t = int(sys.stdin.readline()) for _ in range(t): a, b = map(int, sys.stdin.readline().split()) q = deque() q.append((a, "")) #1 visit = [False]*10001 while q: num, path = q.popleft() visit[num] = True if num == b: #2 print(path) break num2 = (num*2)%10000 #3 if not visit[num2]: q.append((num2, path+"D")) visit[num2] = True num2 = (num-1)%10000..