해결 과정 그래프 상하좌우 탐색 방법은 이전에 알고 있어서 적용 가능했다. while 문으로 다 처리했는데, 답은 잘 나오지만 시간초과가 발생했다. 문제 유형에 너비우선탐색(BFS)가 있길래, Queue를 떠올리며 시간 초과를 어떻게 없앨지 생각하다가, 이전 풀이에서는 이미 탐색한 것도 재탐색하는 비효율이 있음을 알게 됐다. 다음을 추가해서 시간초과 문제를 해결했다. ripedTomatosCount를 추가해서 전체 처리 개수 세도록 했고, while 문 내에서 for 문 돌릴 때, 이미 센 것에 대해선 처리하지 않도록 처리함. (ripedTomatos = newRipedTomatos 재할당) 나의 풀이 def solution(m, n): answer = 0 dx = [0, 1, 0, -1] dy = [-..
해결 과정 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 = ..
