프로그래밍

https://www.acmicpc.net/problem/17609

[난이도] Silver1
[유형] 재귀

[풀이]
sol(int l,int r,bool use)
l : 좌측 index,
r :오른쪽 index,
use : 문자 1개를 제거하는 연산을 사용할 수 있는 상태인지

위의 재귀함수를 만들어서,
s[l]!=s[r]인 상태가 왔을 때, 제거하는 연산 (use)를 사용해준 뒤 재귀호출을 한번 더 해준 뒤
그 결과를 출력해주면 됩니다.

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
string s;
int tc;
int sol(int l,int r,bool use){
    while(l<=r){
        if(s[l]==s[r]) {
            l++,r--;
            continue;
        }
        if(!use) return 2;
        int ret=2;
        if(s[l+1]==s[r]) {
            ret=sol(l+1,r,0);
            if(ret!=2) return 1;
        }
        if(s[l]==s[r-1]) {
            ret=sol(l,r-1,0); 
            if(ret!=2) return 1;
        }
        return ret;
    }
    return 0;
}
int main(){
    cin >> tc;
    while(tc--){
        cin >> s;
        printf("%d\n",sol(0,s.size()-1,1));
    } 
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/17609.cpp

https://www.acmicpc.net/problem/10993

[난이도] Gold4
[유형] 재귀

[풀이]
2차원 배열을 선언한 뒤, 재귀함수로 큰 삼각형부터 그려준다.
공백은 ' '으로 표시해야하며, 더이상 *가 없다면 다음 라인으로 넘어가야
오답을 피할 수 있다.

#include <algorithm>
#include <cstdio>
using namespace std;
bool map[2500][2500];
int N,eg[11];
void prt(int n,int sy,int sx){ 
    if(n==0) return;
    int h=eg[n],w=(h-1)*2+1,d=1,ey,ex=sx+w-1;
    if(n%2==0) {
        ey=sy+h-1;
    }else{
        d=-1;
        ey=sy-h+1;
    }
    for(int i=sx;i<=ex;i++) map[sy][i] = 1;
    int k=1;
    for(int y=sy+d;y!=ey+d;y+=d,k++){
        map[y][sx+k] = map[y][ex-k] = 1;
    }
    prt(n-1,(sy+ey)/2,sx+h/2+1);
}
int main(){
    scanf("%d",&N);
    eg[1]=1;
    for(int i=2;i<=N;i++) eg[i]=eg[i-1]*2+1;
    int k=0,d=1;
    if(N%2) prt(N,eg[N]-1,0);
    else {
        k=eg[N]-1,d=-1;
        prt(N,0,0);
    }
 
    for(int i=0;i<eg[N];i++){
        for(int j=0;j<eg[N]+k;j++) printf("%c",map[i][j] ? '*':' ');  
        k+=d;
        if(i<eg[N]-1) puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/10993.cpp

https://www.acmicpc.net/problem/13325

[난이도] Gold4
[유형] 재귀

[풀이]
재귀함수를 이용해 left와 right 자식의 높이를 비교해서 낮은 쪽이 높은 쪽과 같아지도록 수정한다.

#include <cstdio>
int k,last,a[1<<21];
long long ans;
int sol(int n){
    if((1<<k)-1 <= n && n < last) return 0;
    int l = sol(n*2+1),r = sol(n*2+2);
    if(a[n*2+1]+l<a[n*2+2]+r) a[n*2+1] = a[n*2+2]+r-l;
    else a[n*2+2] = a[n*2+1]+l-r;
    ans += a[n*2+2]+a[n*2+1];
    return l+a[n*2+1];
}
int main(){
    scanf("%d",&k);
    last = (1<<(k+1))-1;
    for(int i=1;i<last;i++) scanf("%d",&a[i]);
    sol(0);
    printf("%lld",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/13325.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://programmers.co.kr/learn/courses/30/lessons/60058

[풀이] 재귀,구현,Stack

문제에 써있는 대로 구현하면 된다.

1. 균형잡힌 괄호 문자열 찾기 int getBalance(string& s)

  여는 괄호와 닫는 괄호의 갯수가 같아지는 순간의 index를 반환

2. 올바른 문자열 체크 bool isRight(string& s)

  stack을 이용하였다. 여는 괄호의 경우 무조건 push, 닫는 괄호인 경우에

  stack이 비어있으면 올바른 괄호 문자열이 아니므로 false 리턴

위의 두 함수를 이용해서 재귀적으로 solution 함수를 채워주면 된다.

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
string p = "()";
int getBalance(string& s) {
	int ret = 0;
	int l=0, r=0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '(') l++;
		else r++;
		if (l == r) {
			ret = i+1;
			break;
		}
	}
	return ret;
}
 
bool isRight(string& s) {
	stack<int> st;
 
	for (int i = 0; i < s.size(); i++) {
		char c = s[i];
		if (c == '(') {
			st.push(c);
		}
		else {
			if (st.empty()) {
				return false;
			}
			else {
				st.pop();
			}
		}
 
	}
	return true;
}
string rev(string& s) {
	string ret = "";
	for (int i = 1;i<s.size()-1;i++) {
		ret.push_back(s[i] == ')' ? '(' : ')');
	}
	return ret;
}
 
string solution(string p) {
	
	if (p == "") return p;
	string ret;
 
	int sz = getBalance(p);
	string w = p.substr(0, sz);
	string u = p.substr(sz, p.size() - sz);
 
	string k = solution(u);
	if (isRight(w)) {
		ret = w + k;
	}
	else {
		ret = "("+k+")";
		ret += rev(w);
	}
	return ret;
}

https://github.com/has2/Algorithm/blob/master/programmers/level2/%EA%B4%84%ED%98%B8%20%EB%B3%80%ED%99%98.cpp