블로그 방문을 환영합니다.

이거 이상으로 좋은 알고리즘이 안떠오른다.....

여기서 주의해야할 점은 매우 빈번히 연산되는 visited를 set으로 해야한다는 점이다.

파이썬 내부적으로 list가 set보다 iteration에서는 빠르지만

탐색(in함수)에서는 set이 훨씬 빠르다.

def compute_gcd(num1, num2):
    if num1%num2 == 0:
        return num2
    return compute_gcd(num2, num1 % num2)

def fillingprime(N):	#에라토네스의 체~N
    raw = set([x for x in range(N+1)])
    raw -= set(range(0,2))
    for i in range(2, int(max(raw)**0.5)+1):
        raw -= set(range(i*2, max(raw)+1, i))
    return list(raw)​

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
}


vector<long long> prime;

void fillingPrime(long long N) {
	vector<int> raw(N + 1);

	for (int i = 2; i < N; i++) {
		raw[i] = i;
	}
	for (long long i = 2; i*i < N; i++) {	//에라토네스의 체
		if (raw[i] == 0)	continue;
		for (int j = i + i; j < N; j += i) {
			raw[j] = 0;
		}
	}
	for (int i = 2; i < N; i++) {
		if (raw[i] != 0)
			prime.push_back(raw[i]);
	}
}
vector<long long> split(string& s, char delimiter) {
	vector<long long> int_tokens;
	string token;
	istringstream tokenStream(s);
	while (getline(tokenStream, token, delimiter)) {
		stringstream ss(token);	//each element, string to int
		long long n;
		ss >> n;
		int_tokens.push_back(n);
	}
	return int_tokens;
}

#include <iostream>
#include <algorithm>
#include <string>
#define null 0

using namespace std;


class node {
private:
	char x;
	node* left;
	node* right;
public:
	node(char data = ' ', node* _left = null, node* _right = null) {
		if (data == '.') {
			data = null;
		}
		else {
			x = data;
		}
		left = _left;
		right = _right;
	}
	void print() {
		cout << this->x;
		return;
	}
	node* getleft() {
		return this->left;
	}
	node* getright() {
		return this->right;
	}
	void setleft(node* data) {
		this->left = data;
		return;
	}
	void setright(node* data) {
		this->right = data;
		return;
	}
	void preorder(node* current) {
		if (current == null) return;
		else {
			cout << current->x;
			preorder(current->getleft());
			preorder(current->getright());
		}
	}
	node* find(node* current, char data) {
		if (current == null) return null;
		else {
			if (current->x == data)	return current;
			else {
				if (find(current->left, data) == null) {
					find(current->right, data) == null;
				}
			}
		}
	}
};

int main() {
	node t = node();
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		char root, lc, rc;
		cin >> root >> lc >> rc;
		if (root == 'A') {
			node lt = node(lc);
			node rt = node(rc);
			t = node(root, &lt, &rt);
		}
		else {
			node* temp = new node;
			temp = t.find(&t, root);
			node templ = node(lc);
			temp->setleft(&templ);
			node tempr = node(rc);
			temp->setright(&tempr);
		}
	}
	t.preorder(&t);
	cout << endl;
	return 0;
}

이 코드가 오류가 난다.

백준 1991을 풀다가 발견한 에러인데

생성자에 조건문 같이 제어문을 사용하면 에러가 발생하는 것 같다

마지막에 setleft를 통해서 값을 설정하려고 할때 this를 지정하는 것이 temp값으로 고정되어야하는데

다른 값으로 튀는 경우가 있었다.

왜 인지는 구글링해도 모르겠다.

문제 입력값의 크기가 큰 것을 보고 눈치채야 했었다.

처음 짠 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> deciTobi(long long num) {
	vector<int> reverse_result;
	vector<int> result;
	while (num > 0) {
		reverse_result.push_back(num % 2);
		num /= 2;
	}
	for (long long i = reverse_result.size()-1; i >= 0 ; i--) {
		result.push_back(reverse_result[i]);
	}
	return result;
}

int main() {
	long long k, sumresult = 0;
	cin >> k;
	long long end = pow(2, k);
	for (int i = 1; i < end; i++) {
		sumresult += i;
	}
	vector<int> result = deciTobi(sumresult);

	for (int i = 0; i < result.size(); i++) {
		cout << result[i];
	}
}

자신있게 풀었고 제출했더니 틀렸단다.

왜지? 하고 계속 쳐다봤는데 숫자 100을 입력하니 메모리 초과가 뜬다.

그때 깨달았다.

이건 10진수를 2진수로 바꾸는 문제가 아닌 것이라는 걸....

기왕 만든 코드로 1부터 10까지 돌려봤다.

규칙성이 나왔다.

k = 1 -> 1

k= 2 -> 110

k=3 -> 11100

k=4 -> 1111000

k=5 -> 111110000

규칙성이 보이는가?

답은 아래와 같다.

#include <iostream>

using namespace std;


int main() {
	int k;
	cin >> k;
	for (int i = 0; i < k; i++) {
		cout << 1;
	}
	for (int i = 0; i < k - 1; i++) {
		cout << 0;
	}
	cin >> k;
	return 0;
}

규칙성 찾기 문제였다.

다음에는 꼭 손으로 풀어보고 코딩해야겠다...

#include <iostream>
#include <math.h>

using namespace std;

bool is_num(char a) {
	if (a == '0' || a == '1' || a == '2' || a == '3' || a == '4' || a == '5' || a == '6' || a == '7' || a == '8' || a == '9')
		return true;
	else
		return false;
}

int main() {
	long long  temp = 0, result = 0;
	int length, jump = 1;
	cin >> length;
	char* word = new char[length+1];
	cin >> word;
	
	for (int i = length; i >= 0; i--) {
		if (is_num(word[i])) {
			temp += (word[i] - '0') * jump;
			jump *= 10;
		}
		if (i == 0 || !is_num(word[i])) {
			result += temp;
			temp = 0;
			jump = 1;
		}
	}
	cout << result;

	return 0;
}

에라토스테네스의 채를 이해하면 금방 풀 수 있다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
bool cache[123456 * 2 + 1];
int main() {
	vector<int> inputs;
	int a;
	while (true) { //input
		cin >> a;
		if (a == 0 || a > 123456) break;
		inputs.push_back(a);
	}

	for (int i = 2; i < 123456 * 2; i++)
		cache[i] = true;
	for (int i = 2; i < sqrt(123456 * 2); i++) {
		if (cache[i]) {
			for (int j = i + i; j <= 123456 * 2; j += i) {
				cache[j] = false;
			}
		}
	}

	for (int i = 0; i < inputs.size(); i++) {
		int count = 0;
		for (int j = inputs[i]+1; j <= inputs[i]*2; j++) {
			if (cache[j]) {
				count++;
			}
		}
		cout << count << endl;
	}
}

입력 한개는 index

다른 입력으로 작은 걸 찾는 그리디 문제

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int testcase;
	cin >> testcase;
	if (testcase < 1 || testcase>20) {
		exit(0);
	}
	int *result = new int[testcase+1];

	for (int i = 0; i < testcase; i++) {
		int pnum;
		cin >> pnum;
		if (pnum < 1 || pnum>100000) {
			exit(0);
		}
		int *people = new int[pnum+1];
		for (int j = 0; j < pnum; j++) {
			int a, b;
			cin >> a >> b;
			if (a<1 || a > 100000 || b<1 || b > 100000) {
				exit(0);
			}
			people[a] = b;
		}

		int counter = 0;
		int selector = 0;
		for (int j = 1; j <= pnum; j++) {
			if (j == 1) {
				counter++;
				selector = people[j];
				continue;
			}
			if (people[j] < selector) {
				counter++;
				selector = people[j];
			}
		}
		result[i] = counter;
	}
	for (int i = 0; i < testcase; i++) {
		cout << result[i] << endl;
	}
}

9방향을 다 체크해본다.

무식한 방법이다.

#include <iostream>

using namespace std;

int map[10][10];

bool letmego(int go, int x, int y, int depth, int counter,int blank) {
	if (depth > 4) {
		return false;
	}
	if (depth == 4) {
		if ((counter == 4 && blank == 1) || counter==5) {
			return true;
		}
	}
	if (go == 0 && x > 0 && y > 0) {
		if (map[x - 1][y - 1] == 1) {
			return letmego(go, x - 1, y - 1, depth + 1, counter + 1, blank);
		}
		else if (map[x - 1][y - 1] == 2) return false;
		else {
			return letmego(go, x - 1, y - 1, depth + 1, counter, blank+1);
		}
	}
	else if (go == 1 && y > 0) {
		if (map[x][y - 1] == 1) {
			return letmego(go, x, y - 1, depth + 1, counter + 1, blank);
		}
		else if (map[x][y - 1] == 2) return false;
		else {
			return letmego(go, x, y - 1, depth + 1, counter, blank+1);
		}
	}
	else if (go == 2 && x < 9 && y > 0) {
		if (map[x + 1][y - 1] == 1) {
			return letmego(go, x + 1, y - 1, depth + 1, counter + 1, blank);
		}
		else if (map[x + 1][y - 1] == 2) return false;
		else {
			return letmego(go, x + 1, y - 1, depth + 1, counter, blank+1);
		}
	}
	else if (go == 3 && x > 0) {
		if (map[x - 1][y] == 1) {
			return letmego(go, x - 1, y, depth + 1, counter + 1, blank);
		}
		else if (map[x - 1][y] == 2) return false;
		else {
			return letmego(go, x - 1, y, depth + 1, counter, blank+1);
		}
	}
	else if (go == 4 && x < 9) {
		if (map[x + 1][y] == 1) {
			return letmego(go, x + 1, y, depth + 1, counter + 1, blank);
		}
		else if (map[x + 1][y] == 2) return false;
		else {
			return letmego(go, x + 1, y, depth + 1, counter, blank+1);
		}
	}
	else if (go == 5 && x > 0 && y < 9) {
		if (map[x - 1][y + 1] == 1) {
			return letmego(go, x - 1, y + 1, depth + 1, counter + 1, blank);
		}
		else if (map[x - 1][y + 1] == 2) return false;
		else {
			return letmego(go, x - 1, y + 1, depth + 1, counter, blank+1);
		}
	}
	else if (go == 6 && y < 9) {
		if (map[x][y + 1] == 1) {
			return letmego(go, x, y + 1, depth + 1, counter + 1, blank);
		}
		else if (map[x][y + 1] == 2) return false;
		else {
			return letmego(go, x, y + 1, depth + 1, counter, blank+1);
		}
	}
	else if (go == 7 && x < 9 && y < 9) {
		if (map[x + 1][y + 1] == 1) {
			return letmego(go, x + 1, y + 1, depth + 1, counter + 1, blank);
		}
		else if (map[x + 1][y + 1] == 2) return false;
		else {
			return letmego(go, x + 1, y + 1, depth + 1, counter, blank+1);
		}
	}
	return false;
}

int main() {
	int a = 0, b = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			char temp;
			cin >> temp;
			if (temp == 'X') {
				map[i][j] = 1;
				a++;
			}
			else if (temp == 'O') {
				map[i][j] = 2;
				b++;
			}
			else if (temp == '.') map[i][j] = 0;
		}
	}
	if (a != b) {
		exit(0);
	}
	bool flag = false;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if(map[i][j] == 1){
				for (int k = 0; k < 8; k++) {
					if (letmego(k, i, j, 0, 1, 0))	flag = true;
				}
			}
		}
	}
	if (flag) {
		cout << 1<<endl;
	}
	else {
		cout << 0 << endl;
	}
}

#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <string.h>

using namespace std;

int main(){
	string s;
    cin >> s;

    char before = s[0];
    vector< pair<int,bool> > steel_num(1,make_pair(1, true));
	for(int i = 1; i< s.length(); i++){
        if(s[i] == '('){
            steel_num.push_back(make_pair(1,true));
        }
        else if(s[i] == ')'){
            if(before == '('){  //레이저일때
                steel_num.pop_back();
                for(int j = 0; j<steel_num.size(); j++){
                    if(steel_num[j].second == true)
                        steel_num[j].first++;
                }
            }
            else{
                for(int j = steel_num.size()-1; j >= 0; j--){
                    if(steel_num[j].second == true){
                        steel_num[j].second = false;
                        break;
                    }
                }
            }
        }
        before = s[i];
	}
	int result = 0;
    for(int i = 0; i<steel_num.size(); i++){
        //cout<<steel_num[i].first<<" ";
        result += steel_num[i].first;
    }
    cout<<result<<endl;

    return 0;
}