개발미정

브론즈이지만 정답비율이 33%로 낮은 문제이다. DP가 기초단계라면 이 문제 추천한다! Top-down / bottom-up 두 가지 방법으로 접근할 수 있다. 나는 브루트포스 / bottom-up 두 가지 방법으로 풀었고, Top-down 으로 푸는 방법은 런타임 에러가 뜨는 상태이다..! 1. 브루트포스 N = int(input()) five_max = 5000//5 three_max = 5000//3 min_count = three_max for i in range(three_max,-1,-1): total = 3*i if total == N and i < min_count: min_count = i else: for j in range(0,five_max+1): total = 5*j + 3*i i..

이번 문제는 분할정복 문제이다. A^5를 구할 경우 A*A*A*A*A 보다 (A^2)^2 * A 로 구하는게 더 빠르다. 이처럼 일일이 다 계산하는 것이 아니라 계산한 값을 활용하여서 다음 값을 구하는 방법이 분할정복이다! 하지만 . . . 시간초과가 났다 ㅋ 😭 지금은 넘 졸리니까,, 나중에 다시 보는걸로...^^.. N, B = map(int, input().split()) BRD = [] for n in range(N): BRD.append(list(map(int, input().split()))) def mulList(a, b): result = 0 for i in range(len(a)): result += a[i] * b[i] return result%1000 # 행렬 a와 b의 곱셈 def ..

문자열 s와 t가 주어지고 s를 변형하여서 t를 만들 수 있는지 확인하는 문제이다. 처음에 s에서 t로 백트래킹으로 접근했는데 계속된 시간초과.. 로 구글링해서 겨우 풀었다... ㅠㅠ 쉬워보였는데 은근 안풀렸던 문제! 첫 번째 풀이 정방향 => 시간초과 def change(s): global result if len(s) ..

분할정복을 정복해보고자....* 백준에 있는 분할정복 문제 중 맨 위에 있던 문제이다! 정답률이 71%로 높은 편이었지만 분할정복 개념만 알고 응용력 0인 나에겐 다소 어려웠던 문제이다 ㅠㅠ 시간이 조금 걸렸지만 풀어보니까 분할정복을 어떻게 접근해야 하는지 감이 조금씩 오는 것 같다 ㅎㅎ 이 문제는 N으로 들어오는 값을 기준으로 NxN 배열이 같은 색이 아닌 경우 N//2 x N//2 를 반복해서 탐색하도록 구현했다. 시작점을 기준으로 N//2길이만큼 탐색하도록 하기 위해서 시작점이 되는 점들을 q에 넣어준 뒤, N//2길이만큼 탐색하도록 isColorPaper 함수를 구현했다. from collections import deque N = int(input()) # 1일때 파랑, 0일때 하양 BRD = ..

백준 bfs문제인 토마토! 1은 익은 토마토, 0은 익지 않은 토마토, -1은 비어있는 칸을 나타낸다. 4개월 전에 c++로 푼 코드와 오늘 python으로 푼 코드가 조금 다른 것 같아서 비교해보려고 한다. 1. Python코드 from collections import deque def bfs(): visited = [[0 for x in range(N)] for y in range(M)] q = deque() # BRD에서 1인 부분을 먼저 추가하기. # -1인 것의 개수 세기 Mcount = 0 for i in range(M): for j in range(N): if BRD[i][j] == 1: q.append((i,j)) elif BRD[i][j] == -1: Mcount += 1 count =..

bfs를 이용한 기본적인 문제! bfs를 완벽히 이해했다면 쉽게 풀릴문제이다. 8가지의 방향으로 이동하도록 구현하였다. T = int(input()) from collections import deque # q = [] # 방향 dx = [-2, -1, 1, 2, 2, 1, -1, -2] dy = [-1, -2, -2, -1, 1, 2, 2, 1] def bfs(): visited = [[0 for _ in range(N)] for _ in range(N)] visited[stX][stY] = 1 q = deque([(stX,stY)]) while q: newX, newY = q.popleft() if newX == enX and newY == enY: return visited[newX][newY] f..

이 문제는 큐 응용 문제이다 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C..