짱아의 개발 기록장

아주 기본적인 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(..

맨 처음 예전에 이 문제를 풀었을 때에는 큐로 풀어야 한다는 생각을 정말 1도 못했다가... 오랜만에 문제를 다시 푸니까 여지 없이 큐로 풀어야겠다는 생각이 바로 들었다! [메인 로직] 큐에 해당 트럭의 무게를 계속 넣어주는데, 만약 다리에 있는 트럭들의 무게의 합이 버틸 수 있는 무게를 넘어서게 되면 트럭을 넣어주지 않고 -1의 의미 없는 값을 넣어주어서 큐가 비어있지 않도록 해주었다. 그리고 최종적으로 트럭을 가리키는 idx가 truck_weights벡터의 크기를 넘어서면 break하도록 했다. 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 35 36 37 38 #include #i..

예전에 백준에서 비슷한 문제였던 전화번호 목록?을 풀었던 기억이 있어서 비교적 쉽게 접근할 수 있었다. [메인 아이디어] 일단, 문자열 배열을 정렬하면 어떤식으로 정렬이 되는 지를 알아야 하는게 우선이다! 문자열 배열 ["flower", "flow", "flo", "fl", "snack", "sna", "s"]를 정렬하면, ["fl", "flo", "flow", "flower", "s", "sna", "snack"] 과 같이 정렬이 된다. 즉, 접두사가 일치하는 문자열 끼리 정렬이 되고 그 후에 알파벳 순서로 정렬된다. 위의 특성을 잘 활용하면 문제를 빠르게 풀 수 있다. 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..

정말 간단한 dfs로 트리의 높이를 구하는 문제였다. 머리를 깨워주기 위해..ㅎㅎ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: int height = 1; void countMaxHeight(TreeNode* node, int h){ if(node==NULL){ height = max(height, h); return; } countMaxHeight(node->left, h+1); countMaxHeight(node->right, h+1); } int maxDepth(TreeNode* root) { if(root==NULL) return 0; countMaxHeight(root->left, 1); ..