본문 바로가기
320x100

PS84

[CLASS 3]백준 1780번, 1931번 1780번 : 종이의 개수 저번에 본 [CLASS 3]백준 2630번 - 색종이 만들기 와 상당히 유사한 문제이다. 재귀를 통해 색종이를 계속 9등분하면서 해당 색종이 안에 같은 수만 있는지 확인해주면 된다. 저번엔 푸는데 힘들었지만 이번엔 쉽게 풀었다! 내 코드(느림): from sys import stdin input = stdin.readline n = int(input()) mat = [list(map(int,input().split())) for _ in range(n)] # 카운터 리스트. 각각 -1, 0, 1 인 종이의 개수와 대응 counts = [0,0,0] dX = [0,1,2] dY = [0,1,2] def find(startX,startY,n): num = mat[startY][st.. 2021. 2. 4.
[CLASS 3]백준 1260번, 1541번 1260번 : DFS와 BFS BFS와 DFS를 구현할 수 있느냐? 를 묻는 문제이다. 쉽게 풀 수 있을 터..인데.. 내 코드(시간 초과): import sys from collections import deque input = sys.stdin.readline n,m,root = map(int,input().split()) nodes = [[] for _ in range(n+1)] for _ in range(m): i,j = map(int,input().split()) nodes[i].append(j) nodes[j].append(i) for i in range(len(nodes)): nodes[i].sort() def dfs(start,n): visited = [False] * (n+1) stack.. 2021. 2. 3.
[CLASS 3]백준 1012번 - 유기농 배추 1012번 : 유기농 배추 배추흰지렁이를 놓는다는 컨셉을 가지고 있는 아주~ 기초적인 그래프 탐색 문제이다. BFS, DFS중 어느 것을 써도 쉽게 풀 수 있다. 쉽게 풀 수 있을 터였으나.. 이렇듯 많은 시행착오가 있었다. 먼저 BFS로 시작해 보았다. 내 코드(시간 초과): import sys from collections import deque input = sys.stdin.readline def findArea(M,N,K): farm = [[False]*M for _ in range(N)] for _ in range(K): X,Y = map(int,input().split()) farm[Y][X] = True areaCount = 0 queue = deque() dx = [-1,1,0,0] dy.. 2021. 2. 2.
[CLASS 3]백준 11726번, 11727번 - 2xn 타일링 11726번 : 2xn 타일링 아주 기초적인 DP문제이다. 이런 문제들을 풀때는 DP라는 것을 깨달은 뒤 부터 P(n) 과 P(n-1)혹은 P(n-k)와의 관계를 잘 생각해 보는 것이 좋은 것 같다. P(n)을 구하기 위해 P(n) 이전 값들을 살펴보자. P(n)은 P(n-1)에서 오른쪽 끝에 세로로 막대기를 하나 추가하는 경우 혹은 P(N-2) + 가로 막대기 2개를 놓은 경우와 같다. 조잡한 그림으로 보면 이렇게 설명된다. 결국 점화식은 P(n) = P(n-1) + P(n-2) 일 뿐이다. 그리고 이는 피보나치 수열과 같다. Wow! 내 코드: n = int(input()) dp = [0,1,3] + [0] * (n - 2) for i in range(3,n+1): dp[i] = dp[i-1] + d.. 2021. 2. 2.

티스토리툴바