Algorithm
-
[LeetCode] Verify Preorder Serialization of a Binary Tree 문제풀이Algorithm/문제풀이 2021. 8. 26. 21:15
https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/ Verify Preorder Serialization of a Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 설명 preorder된 입력 string이 주어지고 온전히 트리의 구성을 하고 있는 지 확인하는 문제이다. 문제 풀이 방법1. index 크기 검사 생각했을 때, preorder 로 탐색..
-
[LeetCode] Rectangle Area II 문제풀이Algorithm/문제풀이 2021. 8. 26. 19:12
https://leetcode.com/problems/rectangle-area-ii/ Rectangle Area II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 내용 사각형이 좌표로 주어지는 데 총 면적을 구하는 것이다. 겹치는 것 제외하고 커버하는 것만 면적 구하는 것이다. 입력은 [x1 y1 x2 y2] 로 왼쪽밑하고 오른쪽위 좌표점이 주어진다. 2개의 좌표를 알면 사각형이 어떻게 생겼는 지 알 수 있다. 문제 풀이 겹치지 않으면 가로 * 세로..
-
[프로그래머스] 더 맵게 문제 풀이Algorithm/문제풀이 2021. 8. 22. 08:18
https://programmers.co.kr/learn/courses/30/lessons/42626# 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 최소값 2개를 꺼내서 연산을 반복해서 K 이상 만들 수 있는지 푸는 문제이다. 매번 최소값이 필요하기 때문에 최소값을 빠르게 구하는 방법이 중요하다. min heap을 사용하면 금방 풀 수 있다. c++ STL에서 priority_queue 를 사용하면 금방 풀 수 있지만, 직접 구현하는 것이 의미가 있다. priority_queue를 이용해서 간..
-
[LeetCode] Valid Sudoku 문제 풀이Algorithm/문제풀이 2021. 8. 20. 22:25
https://leetcode.com/problems/valid-sudoku/ 보드판이 스도쿠를 만족하는 지 검사하는 문제이다. 스도쿠 조건에 맞춰서 다 검사하면 된다. 조건1 3x3 에서 1~9까지 숫자가 존재 조건2 Column 에서 1~9까지 숫자가 존재 조건3 Row 에서 1~9까지 숫자가 존재 class Solution { public: bool isValidSudoku(vector& board) { for (int y = 0; y < 9; y+=3) { for (int x = 0; x < 9; x+=3) { if (!isBlock(board, y, x)) { return false; } } } for (int y = 0; y < 9; ++y) { if (!isCol(board, y)) { re..
-
[LeetCode] Maximum Product of Splitted Binary Tree 문제 풀이Algorithm/문제풀이 2021. 8. 19. 23:15
모든 에지를 다 돌면서 하나씩 뺀다고 생각하면 된다. 전체 합인 total_sum을 구하면 (total_sum - 하위노드의 합) * 하위노드의 합 하나씩 방문하면서 total_sum 과 선택된 노드 total_sum-노드 노드를 탐색할 때, 하위 노드로 가면 하위 노드에 대한 sum 정보를 구해야되는데 또 다시 sum을 구하기엔 시간이 오래 걸린다. 그래서 하위 노드의 합을 저장하기 위해 기존 노드에 덮어씌웠다 class Solution { public: const int mod = 1e9+7; int maxProduct(TreeNode* root) { int total_sum = sum(root); return find(root, total_sum) % mod; } int sum(TreeNode* n..