CS

DP는 나열이 반이다. 잘 나열하는게 시작이다. 그럼 1부터 5정도까지만 나열해보자. 1 2 3 4 5 1 1+1 2 1+1+1 1+2 2+1 3 1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1 1+1+1+1+1 1+1+1+2 1+1+2+1 1+1+3 1+2+1+1 1+2+2 1+3+1 2+1+1+1 2+1+2 2+2+1 2+3 3+1+1 3+2 1개 2개 4개 7개 13개 이를 통해 알 수 있는 것은 어떤 수를 더하기로 나타낼 땐, 1,2,3을 각각 앞에 적고 +를 붙인 뒤에 오는 숫자들은 이전 수의 갯수와 동일하다는 것이다. 예를 들어 5의 경우, 1로 시작하는 경우는 1+ 뒤에 오는 모든 숫자들은 4의 경우와 똑같다. 2로 시작할때는 2+뒤에 오는 숫자들은 3의 경우와 똑같다. ..

캡틴 이다솜 문제를 고민하기에 앞서 사면체에 들어가는 대포알의 갯수를 고민해 보자. 1개, 4개, 10개, 20개... 다음은? 우선 밑면을 생각해 봤을때, 밑면에 추가되는 삼각형이 점점 커짐을 알 수 있다. n이 300,000이라고 해서 300,000까지 다 구해놓기에는 우리에게 주어진 자원은 한정적이므로, 다른 방식으로 구해보자. 결국 우리는 n보다 같거나 많은 양의 대포가 쌓여있는 사면체가 처음 등장하기까지 구해야 한다. 그러므로, 이렇게 세울 수 있다. n=int(input()) tri=[1,3] d=[1,4] idx=1 while n>d[-1]: idx+=1 tri.append(tri[idx-1]+(tri[idx-1]-tri[idx-2])+1) d.append(d[idx-1]+tri[idx]) ..

회문구조이면서 재귀구조를 가지는 팰린드롬 파티션의 갯수를 찾는 문제 예를들어 7은 7 1+5+1 2+3+2 1+1+3+1+1 3+1+3 1+1+1+1+1+1+1 은 되나, 1+2+1+2+1은 안된다. 1+2와 2+1이 재귀가 아니기 때문이다. 규칙을 찾아보자. 중간수를 기준으로 n을 나눠볼 수 있는데, 5와 6의 예시로 살펴보자. 5의 경우 6의 경우 1이 중간에 오는 경우, 1+1+1+1+1 2+1+22가 중간에 오는 경우, 없음 3이 중간에 오는 경우, 1+3+1 4가 중간에 오는 경우, 없음 5가 중간에 오는 경우 5 1이 중간에(?) 오는 경우, 1+1+1+1+1+1 2가 중간에 오는 경우, 2+2+2 1+1+2+1+1 3이 중간에(?) 오는 경우, 3+3 4가 중간에 오는 경우, 1+4+1 5가..

요약하면 n*m의 직사각형으로 이뤄진 연구소에 임의의 벽을 세개 세우고, 바이러스를 퍼뜨린다. 그리고 그 때의 안전공간(0)의 수를 출력하면 된다. 풀이: 1. dfs를 통해 벽을 세운다. 2. bfs를 통해 바이러스를 퍼뜨린다. 3. 0의 갯수를 센다. 치킨거리 문제와 다르게 실제로 벽을 세우고, 시뮬레이션을 돌려야 하기때문에 조금 더 오래 걸린다. https://0422.tistory.com/62 15686 백준 파이썬 치킨집을 m개만 남기되 집과 거리가 최소가 되도록 만드는 문제 m개 남기는 것은 dfs로, 거리 체크는 bfs로 할려고 했으나 시간초과. 이 놈의 dfs는 맨날 시간초과다. 아래는 처음 작성한 코드다. imp 0422.tistory.com 코드는 아래와 같다. import sys im..

치킨집을 m개만 남기되 집과 거리가 최소가 되도록 만드는 문제 m개 남기는 것은 dfs로, 거리 체크는 bfs로 할려고 했으나 시간초과. 이 놈의 dfs는 맨날 시간초과다. 아래는 처음 작성한 코드다. import sys input=sys.stdin.readline from collections import deque def delete(v): global ans if v==0: result=0 for x in LIST: result+=bfs(x) ans.append(result) return result else: for x in range(n): for y in range(n): if space[x][y]==2: space[x][y]=0 delete(v-1) space[x][y]=2 def bfs(t..

처음에 DFS로 시도했으나 시간초과에 부딪혔다. import sys input=sys.stdin.readline n=int(input()) m=[] for x in range(n): m.append(list(map(int,input().split()))) x=0 y=0 cnt=0 dp=[[0 for x in range(n)] for x in range(n)] dp[0][0]=1 def move(x,y,dp): if x==n-1 and y==n-1: return dp else: k=m[x][y] if x+k

import sys input=sys.stdin.readline n=int(input()) l=list(map(int,input().split())) dp=[1 for x in range(n)] for x in range(n): for y in range(x): if l[x]>l[y]: dp[x]=max(dp[x],dp[y]+1) print(max(dp)) 풀이 1. 이중 반복문으로 진행시켜주면서 이전까지의 리스트와 비교한다. 2. 현재 dp값과 이전 리스트의 dp값+1을 비교하여 큰값으로 최신화한다.

불만없제. 그건 그렇고 게시글 너무 밀려버렸다..

이전 게시글에서 BFS와 DFS에 대해 다뤘었다. 이번에는 그 응용. 첫번째는 1012번이다. 말이 어렵지 그냥 1 연속된 칸의 갯수를 구하는 문제다. (x,y)의 값만 잘 설정한 뒤에는 dfs든 bfs든 상관없이 풀이해도 된다. t=int(input()) for _ in range(t): stack=[] li=[] cnt=0 x1=[1,-1,0,0] x2=[0,0,1,-1] m,n,k=map(int, input().split()) space=[[0]*n for x in range(m)] check=[[0]*n for x in range(m)] for _ in range(k): a,b=map(int, input().split()) space[a][b]=1 li.append([a,b]) for x in r..

다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘이다. 다이나믹 프로그래밍은 다음과 같은 가정하에 사용할 수 있다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정담은 큰 문제에서도 동일하다. 즉, 수학의 점화식을 구하여 그 그 값을 저장하므로써, 이전 값들을 통해 값을 빠르게 구하는 방법이다. 그럼 우리가 해야할 것은 무엇인가? 바로 일반항 구하기. 처음 dp를 만난 것은 아마도 9095번일 것이다. 이걸 그냥 풀려고 해보니, 자연수 분할인가 싶기도 하고, 경우의 수를 구하는 문제인가 싶기도 해서 엄청 해맸다. n번항에 알맞는 규칙이 있을 거라고 생각하고 푸니까 막혀서 진행이 안됐었다.(한 3시간 넘게 고민했다.) 그렇게 구글링을 하다보니 dp에 대해 알게..