CS/백준 풀이

요약하면 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에 대해 알게..

마침 스택을 보고 와서인지 문제를 보자마자 스택이 떠올랐다. 1. 스택이 비었다면 입력값을 추가한다. 2. 입력값과 스택의 마지막값이 같다면, 스택에 입력값을 추가한다. 3. 또한 스택의 마지막값이 )이고, 입력값이 (일때도 추가한다. 4. 스택에 남아있는 것이 없다면 YES, 남아있다면 NO를 출력하게 한다. n=int(input()) for _ in range(n): stack=[] inp=list(input()) for x in inp: if not stack: stack.append(x) else: pop=stack.pop() if pop==x or (pop==")" and x=="("): stack.append(pop) stack.append(x) if not stack: print("YES")..

사실 이 문제는 퀵정렬, 합병정렬이 아니다. 근데 왜 이런 태그를 붙여놨느냐? 내가 메모리 제한을 못보고 합병정렬로 풀었기 때문이다. 합병정렬 합병 정렬은 배열(리스트)을 크기가 1이 될 때까지 자르고, 정렬을 하며 붙여나가는 알고리즘이다. 합병정렬은 다음과 같이 구현된다. 1. 배열을 반으로 나눈다.(길이가 1이 될때까지) 2. 양 옆의 배열을 비교하며, 합병한다. 합병정렬은 어떻게 자료가 정렬되어 있던 상관없이 시간복잡도가 O(nlogn)이다. 대신 제자리 정렬이 안되고, 임시 배열이 필요하다는 단점이 있다. 하지만 연결리스트로 작성하면, 제자리 정렬도 가능하다고 한다. 아래는 합병정렬 알고리즘이다. def msort(l): if len(l)==1: return l else: mid=len(l)//2..

이녀석을 처음 만난 것은 1654번이다. 나는 평범하게 이 녀석의 모든 경우를 계산해서 해결하려고 했다. k,n=map(int,input().split()) a=[] res=[] for _ in range(k): a.append(int(input())) for y in range(1, min(a)+1): cnt=0 for x in a: cnt=cnt+x//y if(cnt>=n): res.append(y) print(max(res)) 결과는 시간초과. 그래서 찾다가 알게된 이진탐색. 아래는 개념이다. 이진탐색(Binary Search) 데이터가 정렬되어 있는 배열에서 특정 값을 찾아내는 알고리즘이다. 배열 중간의 값을 골리 찾는 값과 비교하고, 중간 값이 찾는 값보다 작으면 최소값을 중간값 +1로 바꾼다...