1. 문제  2. 접근문제를 요약하면 고속도로 길이 D까지 최단으로 이동하는 거리 구하기이다. 일직선인 고속도로가 주어지고 중간 중간 지름길이 주어진다. 각 지름길의 결과가 이후의 거리에 영향을 주기 때문에 누적할 수 있는 DP를 이용하기로 했다.  3. 풀이1. 지름길의 End값을 갱신`dp[end] = Min(dp[end], dp[statr] + cost)` 라는 점화식을 이용해서 지름길을 오름차순 정렬 후에 더 빨리 갈 수 있는 방법을 갱신하고자 했다. 이때 dp[i]는 i목적까지 가는 거리이다. 하지만 놓쳤던 것은 모든 dp값은 바로 직전의 값에 영향을 받는다는 것이었다. dp[i-1] +1의 값도 고려해서 이동한 거리 중 최소값을 구해야한다. 그래서 최종 점화식은 아래와 같다. 처음 dp[i]값..

거울의 반사되는 조건과 기존에 자주 풀던 최단 경로가 아닌 도달할 수 있을 때 '거울의 최소 수'를 구하는 문제라서 더욱 어렵게 느껴졌다.문제를 읽고 구현을 BFS로 할지, DFS로 할지 고민했는데 BFS로 하게될 경우 거울의 개수를 어떻게 관리하고, 그에 따른 visited 배열을 관리하는 것이 어려울 것 같아서 바로 DFS로 노선을 틀었다. 최소 거울의 개수를 구하면 되니깐 거울을 1개 이용했을 때 반대편 문제 도달하는지 확인하고, 도달 못하는 경우 거울의 수를 늘려서 다시 2개, 3개,, N개가 될 때까지 DFS를 반복했다. 그러니 당연하게도 시간초과가 났다.  이 문제는 BFS로 풀어야되는 문제였다. 다른 사람의 BFS 풀이를 보면서 내가 잘못 접근한 부분을 찾아봤다. 1. 거울의 개수를 어떻게 ..

1. 문제  2. 풀이 방법문제를 이해하기 위해 예제로 주어진 트리를 그려봤다. 루트가 주어지기에 자연스럽게 계층 구조가 형성된다. 서브트리의 개수는 곧 자기와 자식들의 정점 수를 모두 합친 수였다. 시간복잡도를 따져봤을 때 정점의 개수는 십만이고, 쿼리의 개수도 십만이기에 O(N)이나 O(logN)으로 풀어야할 것 같았다.어떻게하면 한 번의 쿼리 때 logN의 시간복잡도를 가질 수 있을까 고민해보다가 그냥 한 번 전체탐색을 돌려서 모든 정점의 서브트리의 개수를 구한 후 쿼리에 맞춰 답을 출력해주면 될 것 같았다. 서브트리를 구하는 방법은 재귀적으로 자식 노드들을 방문하면서 개수를 구하면 될 것 같아서 바로 코드로 옮겨봤다.우선 트리를 형성하기 위해 ArrayList 배열을 이용하였다. 아래와 같이 주어..

클래스내에 있는 함수를 테스트하기로 했다. 이때 고민된 것은 테스트 함수를 실행할 때마다 클래스 인스턴스를 만드는 것이었다.테스트 하려는 클래스는 생성자될 때 파싱해야 할 노드를 인자로 받는다. 그러면 매 테스트마다 다른 노드를 인자로 클래스를 만들어야 했다 이때 `fixture`를 사용하면 중복 코드를 줄이고 원하는 객체를 제공할 수 있다. 'pytest.fixture' 데코레이터를 작성하면 매 테스트 함수 호출 때마다 데코레이터를 붙인 함수를 실행한다. 이때 DB와 같은 클래스를 정의하거나 사전 준비 코드를 작성하면 테스트 함수마다 작성해야하는 코드 중복을 줄일 수 있다. @pytest.fixturedef call_parser(elem_manager): # CallParser 인스턴스를 생성하는..

1. 문제https://www.acmicpc.net/problem/15990 2. 접근문제가 너무 DP스러워서 바로 경우의 수들을 차례차례 써봤다. 처음에는 잘 안보였는데 연속해서 사용하면 안된다 조건에 집중해서 계속 생각해봤다. 1이 마지막에 나오면 그 후엔 2와 3만 올 수 있고 그러면 n-2와 n-3에서 정보를 가져와야 할텐데.. 또 마지막에 나오는 수를 저장하기 위해 2차원 배열을 사용해볼까! 하다가 점화식이 떠올랐다 나온 점화식은 아래와 같다dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % MODdp[i][2] = (dp[i-2][1] + dp[i-2][3]) % MODdp[i][3] = (dp[i-3][1] + dp[i-3][2]) % MOD-> result : dp[i][..