해결 과정 DP 문제 하나 더 풀어보려고 본 문제. 문제는 이해가 갔으나 이걸 어떻게 DP 테이블로 풀지 감이 안와서 다른 링크를 참고했다. 먼저 그림을 그려 이해한 뒤, 코드는 보지 않고 스스로 풀어봤다. 처음에 행과 열을 바꿔서 초기화해서 런타임 에러가 났는데, 이 부분 조심. dp 테이블에 첫 행과 첫 열을 하나씩 더 두고, 0으로 초기화 해둔다. 이중 for문을 돌면서, 현재 위치의 a와 b가 같으면, dp[i-1][j-1]의 값에 + 1을 해서 넣고 다르면, dp[i-1][j] 와 dp[i][j-1] 중 더 큰 값을 넣는다. 나의 풀이 def solution(a, b): dp = [[0]*(len(b)+1) for _ in range(len(a)+1)] for i in range(1, len(a..
해결 과정 말 그대로 구현 문제. 어려운 부분은 없었다. 모든 케이스를 모두 탐색하면 된다. 나의 풀이 from itertools import combinations def cityChickenDistance(candidate): dist = 0 for h in house: minDist = [] for c in candidate: dis = abs(h[0]-c[0]) + abs(h[1]-c[1]) minDist.append(dis) dist += min(minDist) return dist def solution(N, M): answer = -1 markets = [] # markets = [(0, 1), (1, 2)] global house house = [] for i in range(N): for..
해결 과정 찐 수학 문제임 ㅋ 수학 문제 하나 풀어볼까 해서 푸는데, 오랜만에 고등 수학 다시 보고 옴 ㅋㅋ 등차수열의 합 오랜만~ 일단 이동 횟수의 최솟값을 찾으라는데, 규칙을 찾았음. 이동 횟수를 최소로 하는 경우 거리 k 이동 횟수 r 1 1 1 1+2+1 4 3 1+2+3+2+1 9 5 1+2+3+4+3+2+1 16 7 이런 식으로 최소가 되도록 하는 규칙을 찾으며 공식을 도출함. y-x를 거리 k 라고 했을 때, 이동 횟수의 최솟값을 r이라고 하자. r ==2√k - 1 다만, 이것은 r이 정수가 나올 때만 유효하고, 정수가 나오지 않을 때는 따로 생각해봐야 함. 1 2 3 4 여기서 2는 1.xxx 3은 2.xxx 가 나왔는데, 이를 보고 올림을 하면 되겠다고 생각함. 4 5 6 7 8 9 이..
해결 과정 처음엔 소괄호 대괄호 스택 따로 있어야 하나 했는데 아님. 하나로 해야 함. if else 조건 잘못 줘서 한 번 틀렸다가, 예외 케이스가 있다는 것을 인지하고 변경함. 일반적인 stack 풀이. 나의 풀이 def solution(str): stack = [] answer = "yes" for s in str: if s == "(": stack.append(s) elif s == "[": stack.append(s) elif s == ")": if stack and stack[-1] == "(": stack.pop() else: answer = "no" break elif s == "]": if stack and stack[-1] == "[": stack.pop() else: answer = ..
해결 과정 처음 봤을 때 정확하게 이해 못했다가, 각 잡고 천천히 이해해봤다. dp[N][K] ➡️ N번째 물건까지 쓰고, 수용 가능한 무게 K라고 할 때의 최대 가치. 나의 풀이 # knapsack 알고리즘 def solution(n, k, objects): dp = [[0] * (k+1) for i in range(n+1)] objs = [[0, 0]] + objects for i in range(1, n + 1): for j in range(1, k + 1): if j >= objs[i][0]: dp[i][j] = max(objs[i][1] + dp[i-1][j-objs[i][0]], dp[i-1][j]) else: dp[i][j] = dp[i-1][j] return dp[n][k] n, k = m..
