미소를뿌리는감자의 코딩

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..

1. 문제https://www.acmicpc.net/problem/1520 2. 접근 방법처음에는 2중 arr를 선언을 통해 해당 위치에서의 접근 route 개수를 구하려고 하였다.따라서, max queue를 이용해서, 구현을 하였지만, 메모리 초과가 발생하였다. 이에, max_queue를 이용하지 않고 구현을 시작해야 했다. 즉, dfs + memoization을 이용한 구현을 통해서 메모리를 더 아낄 필요성이 있었다. dp = [[-1] * m for _ in range(n)]을 통해서 기본 값이 -1인 dp를 선언해 주었다.이후, 특정 route가 dp[-1][-1]에 도달한다면, 1을 반환해 주어, 해당 목표 점에 도달이 성공하였음을 알려주었다. 따라서 i == n-1 and j == m-1 이라..