프로그래밍

https://leetcode.com/problems/battleships-in-a-board/

[풀이] BFS

1XN 또는 NX1 모양의 배를 찾는 문제. 

문제의 조건에 배는 인접하지 않고

valid한 map만 주어진다고 했으므로

BFS를 돌면서 찾은 그룹의 개수가 답이다.

https://github.com/has2/Algorithm/blob/master/leetcode/419.%20Battleships%20in%20a%20Board.cpp

https://leetcode.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/

[풀이] Greedy

문제해석이 어려운 문제.

결론적으로 어떤 VPS를 A,B 두 VPS로 나누는 문제. 이 때 depth(A,B)가 최소가 되도록 나누어야 한다.

처음엔 당연히 연속되는 괄호들로 나눠야 한다고 생각했는데

예제를 보니 ()(())() 와 같이 나눠도 된다.

depth를 가장 작게 하려면 겹치는 괄호를 최소한으로 만들어야 한다.그러려면 stack에 여는 괄호를 넣을 때 0,1,0,1 이런식으로 차례대로 넣어주면 된다.닫는 괄호는 여는 괄호와 같은 그룹에 들어가야 하므로 top과 같은 값으로 설정해주면 된다.

https://leetcode.com/problems/sort-integers-by-the-power-value/

[풀이] DP

홀수인경우 kx3 + 1 , 짝수인경우 k/2를 해서 1이 될때까지 만드는 문제

최대 1000개의 값들을 계산해야 하기 때문에 시간복잡도 예상이 안되서 

DP로 풀었는데 완전탐색 해도 풀린다고 한다.

dp 배열을 처음에 4000 크기정도만 해줘도 될거라고 생각했는데 계속 런타임 에러가 나서

500000까지 바꿔주었다. 1000 이하의 k 값을 1로 만드는 과정에서 k가 상당히 커질수도 있는 것 같다.

https://github.com/has2/Algorithm/blob/master/leetcode/1387.cpp

https://leetcode.com/problems/count-good-nodes-in-binary-tree/

[풀이]

1. 재귀를 이용해서 이진트리의 모든 노드들을 순회한다.

2. 파라미터 v는 현재 node의 부모 node들의 value 중에 가장 큰 value를 의미한다.

3. 현재 노드의 value가 v보다 크면 return 값에 1을 더해 주어 결과값에 추가될 수 있도록 한다.

4. root는 무조건 추가되어야 하므로 main에서 -100000을 v에 넣어준다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

	int search(TreeNode* node, int v) {

		if (node == nullptr) return 0;
 
		int ret = 0;
		int cur_max = v;
		if (node->val >= v) {
			cur_max = node->val;
			ret++;
		}
		ret += search(node->left,  cur_max);
		ret += search(node->right, cur_max);

		return ret;
	}

	int goodNodes(TreeNode* root) {
		return search(root, -100000);
	}
};

https://github.com/has2/Algorithm/blob/master/leetcode/1448.cpp

https://leetcode.com/problems/subrectangle-queries/

#include <vector>
#include <algorithm>
using namespace std;
class SubrectangleQueries {
public:
	vector<vector<int>> rec;
	SubrectangleQueries(vector<vector<int>>& rectangle) {
		rec = rectangle;
	}

	void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
		for (int i = row1; i <= row2; i++) {
			fill(rec[i].begin()+col1, rec[i].begin()+col2+1, newValue);
		}
	}

	int getValue(int row, int col) {
		return rec[row][col];
	}
};