개발미정

이번 문제는 백준의 실버1 난이도인 완전탐색 문제이다. 재귀로도 풀 수 있지만, 조합을 구해서 모든 조합의 경우의 수에 대해 문제를 해결하였다. 조합 경우의 수가 담긴 리스트를 순회하면서, 해당 인덱스의 재료들을 포함시킬 경우의 신맛과 단맛의 차이를 구하여서 최소값을 구해주었다. 정답코드 N = int(input()) ingredients = [] for n in range(N): ingredients.append(tuple(map(int, input().split()))) # [(3,8), (5,8)] min_gap = 1000000000 def combi(n): combis = [] for i in range(1

두 개의 동전이 있고, 보드가 있을 때 두 개의 동전 중 하나만 떨어지면서 그 때의 최소 count를 구하는 문제이다. 문제 접근 BFS로 접근하였고, 다음 3가지만 고려하였다. 1. 두 개의 동전이 모두 안 떨어진 경우 2. 두 개의 동전이 모두 떨어진 경우 3. 한 개의 동전만 떨어진 경우 남 -> 동 -> 북 -> 서 순으로 이동하였고, 1번 경우에는 다음 가고자 하는 위치가 벽인 경우만 고려해주었다. 2번 경우에는 count를 할 필요가 없기 때문에 pass 하였다. 3번인 경우 현재 최소 count와 현재까지의 count를 비교하여서 최소값을 구하였다. 정답 코드 from collections import deque rows, cols = map(int, input().split()) BRD =..

실버5단계의 문제이다. N개의 DNA가 주어지고, Hamming Distance가 가장 작게 나오는 DNA 서열을 구하는 문제이다. 이 문제는, 각각의 서열을 인덱스로 접근하여서 가장 많이 나온 알파벳을 추가하는 방식으로 문제를 해결했다. 처음에 문제를 끝까지 다 안읽어서 멀리까지 돌고 돌다가 왔다..ㅎㅎ "그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다." 만약 DNA 서열들의 1번 인덱스가 A 1개, T 1개, G 1개, C 1개 있다고 했을 때 A를 추가해주면 되는데, 위에 문장을 안읽고 각각 넣어보고 다른 서열들과 비교해서 Hamming Distance가 가장 작은 것을 찾는 방식으로 풀다가 포기했다..ㅎ 오늘의 교훈문제 끝까지 읽자..^~^ 해결코드 N, M = map..

실버4 난이도의 문제.. 너무 꼬아서 생각했더니 빙빙 돌다가 겨우 맞았습니다가 떴다 ㅎㅎ🤦‍♀️ 첫 번째 풀이 A, B = input().split() def dfs(a): global B, min_gap gap = 0 if len(a) > len(B): return if len(a) == len(B): for i in range(len(a)): if a[i] != B[i]: gap += 1 if min_gap > gap: min_gap = gap return alphabet = [chr(i) for i in range(97,123)] ## a ~ z # A 앞에 알파벳 추가 for i in alphabet: dfs(a+i) dfs(i+a) min_gap = 9999 dfs(A) A 문자열 앞 뒤에 알파..

입력받은 배열이 pho라고 하고, 최대값을 저장할 배열이 dp라고 하자. n이 1인 경우, 최대값은 pho[1]이다. n이 1보다 큰 경우, 다음과 같은 점화식을 따른다. dp[n] = max(dp[n-1], dp[n-2] + pho[n], dp[n-3] + pho[n-1] + pho[n]) 이게 어떻게 적용되는 건지 보자. 각각 n일때의 최대값이다. n=3보다 큰 경우 - n일때 값을 포함시키지 않은 값(dp[n-1]) - n-2일때 포함 안하고, n-1과 n일때만 포함시키는 값(dp[n-3]+pho[n-1]+pho[n]) - n-1번째 포함 안하고 n번째 포함하는 값(dp[n-2]+pho[n]) 중 최대값이 dp에 저장된다. N = int(input()) pho = [0] for n in range(..

브론즈이지만 정답비율이 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..

기존 피보나치 함수를 DP로 푸는 문제이다. Top-down 방법으로 풀기 위해서 먼저, Zero 개수를 저장하는 배열과 One 개수를 저장하는 배열을 따로 만든 뒤, 기존에 저장되어 있는 값이 없으면 재귀를 실행하고, 있으면 기존 값과 비교해서 더 작은 값으로 초기화하도록 구현하였다. T = int(input()) def fibo(n): if n > 1 and zero[n-1] == 0 and one[n-1] == 0: fibo(n-1) if n == 0: zero[n] = 1 one[n] = 0 elif n == 1: zero[n-1] = 1 one[n-1] =0 zero[n] = 0 one[n] = 1 else: zero[n] = zero[n-2] + zero[n-1] one[n] = one[n-2..

이번 문제는 분할정복 문제이다. 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 ..