짱아의 개발 기록장

재귀와 dp를 함께 사용하는 아주 전형적인 문제 중 하나이다! 어느정도 난이도도 있으면서 감을 잡기 좋은? 문제인 것 같다. [메인 로직] dp배열을 -1의 값으로 초기화해놓고 판다가 출발하는 좌표보다 더 많은 대나무를 가지고 있는 영역의 dp값을 가져와서 +1씩 더하는 논리로 구현했다. 가지치기를 할 수 있는 부분이 바로 dp값이 -1이 아닌 경우는 이미 이전에 방문을 해서 그 영역에서 최대 몇 일을 버틸 수 있는지 메모이제이션을 해놓은 것이기 때문에 연산을 하지 않고 return dp[x][y]을 하고 바로 넘어갈 수 있다. (-> 매우 시간 절약!) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ..

1) DP+BFS BFS와 DP를 모두 활용해서 푸는 문제였다. 약간 백준에서 욕심쟁이 판다?와 비슷한 느낌? 하지만 이 문제가 훨~~씬 쉽다. [메인 로직] 일단, dp[y][x] = dp[y-1][x] + dp[y][x-1]이라는 공식은 문제를 읽어보면 쉽게 세울 수 있다. 이것을 응용해서 특정 칸에서 다음 칸으로 이동하게 되면, 다음 칸의 dp값에 현재 칸의 dp값을 무조건 더해주었다. 지나가는 길이기 때문에 경로추가! (dp[ny][nx] += dp[y][x]) 또한!!! 이미 방문한 곳은 큐에 절대로 넣어주지 않았다... 왜냐하면 수가 배가 되기 때문에....dp값은 방문했던 곳이여도 지나가는 길에 도달한 것이기 때문에 항상 더해주었지만, 이미 방문한 점은 다시 큐에 넣어주면 안된다! 1 2 3..

도저히.. 풀이가 생각이 나지 않아 다른 블로그의 아이디어만 참고해서 가닥을 잡을 수 있었다. [메인 로직] 모든 경우의 수 중에서 가장 최악의 시간이 나올 경우를 찾는다. ex) [7, 10], n = 6이면 최악의 시간은 10분이 걸리는 심사관에게 6명 모두가 입국심사를 받는 경우가 될 것이다. 그러면 최악의 시간은 총 60분이다. Start = 1, End = 60으로 하고 이분탐색을 시작하면 된다. mid = (Start+End)/2로 잡고 mid의 시간일 때 총 검사할 수 있는 인원의 수를 구한다. 30/7+30/10 = 7은 n=6의 값보다 크기 때문에 End = mid-1로 이분탐색을 쭉 진행하면 된다. 단! 조심해야하는 부분은 n값과 같은 값이 나왔다고 해서 바로 break로 빠져나오면 오..

아주 기본적인 BFS문제이다. 방문하지 않은 컴퓨터에 방문해서 연결된 모든 컴퓨터들을 하나의 네트워크로 연결해주는 작업을 bfs로 해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include #include using namespace std; int solution(int n, vector computers) { int answer = 0; int visited[201] = {0, }; for(int j=0; j

[메인로직] 현재 시간(sec)이하의 요청 시간을 가지고 있는 작업들을 모두 최소 힙에 넣고 => 힙에 pair 형태로 저장했다. 그 중 가장 작은 작업 시간을 가지는 작업을 수행한다. 위의 로직을 모든 작업이 끝날때까지 반복하면 된다! 하지만!!!!! [[0 , 3], [4, 4], [5, 3], [4, 1]] 이 테스트케이스에서 오류가 발생했다..... 작업을 수행하면서 현재 시간을 sec += (작업의 소요시간) 으로 더해주었는데,,,,,, 위 케이스에서는 첫 번째 작업 수행 후, sec = 3이 되면 3이하의 요청시간을 가지는 작업이 하~~~나도 없기 때문에 의미없이 while문을 계속돌아서 TimeLimit이 발생한다. 따라서, 위와 같이 priority_queue에 아무것도 없을 경우에는 현재..

이것은 간단한 공식? 으로 해결할 수 있는 문제였다. [메인 로직] (행*열 = 갈색 수+노란색 수)이기 때문에 R*C를 통해 각 R, C의 값을 유추해볼 수 있다. 또한, (r-2)*(c-2) = 노란색 수 공식도 성립해야한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include using namespace std; vector solution(int brown, int yellow) { vector answer; int RC = brown+yellow; int r, c; for(int i=3; i=b){ c = a; r = b; }else{ c = b; r = a; ..

이 문제는 도저히 아이디어가 생각나지 않아 코드는 참고하지 않고 아이디어만 다른 분의 아이디어를 참고해서 풀었다. 아래가 다른 분의 아이디어이다. [메인 로직] 첫 번째 카메라는 첫 번째로 차가 빠져나가는 지점에 설치해야 합니다. 왜냐하면 이 지점에서 설치하지 않으면 첫 번째로 빠져나가는 차는 찍을 수 없기 때문입니다. 그 지점에 카메라를 설치하면 해당 지점을 지나는 차들은 모두 카메라에 찍히게 되므로 더 이상 신경 쓸 필요가 없습니다. 두 번째 카메라는 아직 카메라에 찍히지 않은 차 중에서 첫 번째로 차가 빠져나가는 지점에 설치하면 됩니다. 두 번째 지점에 카메라를 설치하면 해당 지점을 지나는 차량들은 모두 찍히게 되므로 더 이상 신경 쓸 필요가 없습니다. 이런 식으로 계속 해서 카메라를 설치하는 과정..

처음 queue를 사용해서 문제를 풀었을 때는, 시간이 faster than 13.36%가 나와서,,,, 큰일났다 싶었다. 따라서, 다른 분들의 풀이를 참고해서 큐를 사용하지 않고 그냥 dfs로도 풀어보았다. 1. runtime -> faster than 13.36%, memory -> less than 62.96% 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public: vector levelOrderBottom(TreeNode* root) { queue q; q.push(root); vector ans; stack st; while(!q.empty(..