미소를뿌리는감자의 코딩

1. 문제https://www.acmicpc.net/problem/13549 2. 접근 방법BFS로 문제를 접근하였다. 이를 위해서 deque를 이용하였다.queue에서 먼저 pop이 된 것이 동생의 위치를 나타낸다면, 그것이 가장 빠르게 동생에게 접근하는 경우라고 판단하였다. 또한 memoization을 이용해 주어, 해당 위치에 접근했을 때의 cnt를 list에 저장해 주었다. 만약 cnt가 더 작다면, 해당 memoization을 갱신해주고, 해당 위치에서 방문 가능한 경우들 x-1, x+1, 2*x에 대해서 위치를 deque에 넣어주었다. 하지만, 순서가 중요했다. 우선순위가 있는 접근들을 먼저 queue에 넣어주어야 했다.우선순위는 2*x, x-1, x+1이다. 2*x의 경우 직관적으로 우선순위..

1. 문제https://www.acmicpc.net/problem/1600 2. 접근 방법처음에 i, j 로 visited list를 만드는 것을 생각하였다가, k의 값이 유동적일 것이라 힘들 것 같다는 생각을 하였었다.하지만 3차원 리스트가 존재했기 때문에, 이를 이용하면 되었다. 코드 풀이 중에서 처음 시도는 import queue를 하는 것이었다. 하지만, 시간 초과와 런타임 에러가 지속되었고 다른 코드를 확인하다가  from collections import deque를 적용한 코드를 확인하게 되었다. 이에 queue -> deque로 import를 바꾸었고, 통과할 수 있었다. 과연, 둘의 차이가 무엇일까? import queuequeue.Queue()로 사용이 된다. 이는 멀티스레딩 환경에서의..

1. 문제https://www.acmicpc.net/problem/9655 2. 접근 방법[0,0] 을 Idx로 가지는 리스트를 선언하여 시작하였다.만약 sk가 n번째 돌을 가져갔다면 cy은 n+1 or. n+3 번째 돌을 가져갈 수 있다고 생각하여 이를 이용하여 코드를 작성해 주었다.위 코드대로 작성하게 되면 시간초과가 나므로,   if dp[n][name] > 0: return이 부분을 추가하여 중복된 계산을 피하고자 하였다. 3. 코드def get_winner(n, name): if n > x: return if dp[n][name] > 0: return dp[n][name] += 1 if name == 0: get_win..

1. 문제https://www.acmicpc.net/problem/1463 2. 접근 방법dfs와 memoization을 이용하여 해결하면 된다고 생각하였다. 기존의 memoization과 다른 점이 있다면, 3으로 나눈 것과 2로 나눈 것과 1을 뺀 것 중에 재귀적으로 답을 구한 후, 가장 작은 값을 dp에 저장해 주는 과정이다. 3. 코드import sysdef dfs(n): if dp[n] != 0: return dp[n] ans = [sys.maxsize] * 3 if n % 3 == 0: ans[0] = 1 + dfs(n//3) if n % 2 == 0: ans[1] = 1 + dfs(n//2) ans[2] = 1 + dfs(n-1..