1. 문제 2. 접근문제를 읽어보면 특정 알고리즘을 이용하는 것이 아니라 구현 문제임을 알 수 있다. 계속 구현 문제를 풀면서 느낀 것은 구현 문제는 처음부터 잘 구현해야한다!! 그렇지 않으면 디버깅 시간이나 실수 고치는 시간이 더 드는 것 같다. 그래서 구현 문제임을 파악하고 구체적인 설계부터 시작했다. 문제에서 친절하게 각 단계마다 설명을 줘서 단계별로 함수를 나눴다.고민한 점은 내려가는 위치, 올라가는 위치를 담을 고정 위치 정보, 움직이는 벨트 정보, 인형의 정보를 겹치지 않고 어떻게 저장할까 였다. class를 너무 많이 만들면 오히려 헷갈려서 최대한 줄이면서 표현하려고 했다. 처음엔 int[] 배열로 각 벨트의 내구도를 저장하고 `Doll` 클래스로 인형의 생성카운트, 현재 위치를 저장했다. ..

1. 문제  2. 접근문제의 핵심은 먹을 수 있는 초밥 가짓수의 최댓값이다. 가짓수이다. 개수가 아니다. 먹을 수 있는 가짓수가 최댓값일 때는 언제일까?먼저, 보너스 초밥을 포함하여 k개의 초밥을 먹을 때 k+1개를 먹을 수 있어서 최대이다. 하지만 무조건 보너스 초밥을 먹어야 되는 경우가 있을 수 있다. 예를 들어 보너스 초밥을 제외한 초밥의 가짓수가 k보다 적을 때는 보너스 초밥도 먹어야 한다. 이때 가짓수는 k개이다. 두 경우를 보면 여기서 중요한 것은 보너스 초밥을 포함해서 먹느냐 말냐이다. 그리고 가짓수이니깐 같은 종류의 초밥을 먹을 떄 중복 카운팅이 일어나며 안된다.  정리하면 갱신 및 저장이 필요한 데이터는 보너스 초밥의 포함 여부, 먹은 초밥의 가짓수이다. 보너스 초밥의 포함 여부는 `bo..

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 배열을 이용하였다. 아래와 같이 주어..