GGym's Practice Notes

세그먼트 트리 문제 세그먼트 트리에 대해서 알고 있다면 쉽게 풀 수 있는 문제다. 응용 없이 생성 - 갱신 - 합 과정 만을 사용한다. #include// 2042_구간합구하기 [세그먼트트리] #include #include using namespace std; #define max(x,y) x>y?x:y int N, M, K; // 세그먼트 트리 // - 생성 과정 long long init( vector &a, vector &tree, int node, int start, int end ){ // 리프 노드일 경우 if(start == end) return tree[node] = a[start]; // 가지 뻗기 else{ int mid = (start + end)/2; return tree[node..

스택 문제 스택에 폭발 문자열의 앞부분을 쌓아두고 터지면 스택에 있는 것을 pop하면서 없애면 된다. 스택에 쌓이는 도중에 다른 문자열이 들어오면 스택 앞에 있는 문자열은 터지지 않으므로 스택을 비워놓는 것이 중요하다. #include //9935_문자열폭발 [스택] #include #include using namespace std; int main(){ stack S; char str[1000001]; char boom[1000001]; string result = ""; scanf("%s %s", str, boom); int l; for(l=0; boom[l]!='\0'; l++); for(int i=0; str[i] != '\0';i++){ if (boom[0] == str[i]) S.push(1..

백트래킹을 이용한 문제이다. 탐색을 이용하여 K개의 글자를 체크하면서 입력한 단어중 체크한 글자에 최대로 포함되어 있는 것을 찾으면 된다. 밤새고 새벽에 풀어서 그런지 탐색에서 사소한 실수로 좀 고생을 많이했다. #include //1062_가르침 [백트래킹] #define MAX(x,y) x>y?x:y unsigned int word[50], max, N, K, check; int GetCnt(){ int cnt = 0; for(int i=0; i

오랜만에 알고리즘을 풀었다. 이 문제는 DFS를 이용해서 구한다. 처음에 모든 리프노드는 모두 루트노드가 될 수 있으니 리프노드를 전부 검색하는 방법으로 구현했지만 노드가 10만개라서 시간초과가 날 것이라 생각했다. 해결 방법으론 아무 리프노드나 골라 최대 경로를 구한 후 최대 경로의 끝 노드를 루트 노드로 다시 최대 경로를 구하면 된다. DFS 2번이면 해결 가능하지만 더 빠른 방법이 있을 것 같다. #include// #include using namespace std; vector tree[100001]; bool visits[100001]; int largest = 0; int temp = 0; bool isLeaf(int n){ if(tree[n].size() == 1) return true; ..

문자열을 피연산자와 연산자로 구분하고 경우의 수가 6가지이므로 우선순위에 맞게 처리 하였다. 연산자 처리과정이 3단계(*, +, -) 로 구분되기 때문에 다음 과정을 저장할 vector 피연산자, 연산자 배열을 두고 사용하였다. 저장된 계산과정은 스택에 저장하였지만.. 어차피 하나밖에 저장안하기 때문에 스택을 사용하지 않아도 될 것 같다. (비어있는경우 처리하는 것만 어떻게 한다면.) #include // Level2_ 수식 최대화 #include #include #include #include using namespace std; char RANK[6][3] = { {'+', '-', '*'}, {'+', '*', '-'}, {'-', '+', '*'}, {'-', '*', '+'}, {'*', '+'..

큐와 우선순위 큐를 사용했다. 우선순위가 9~1까지 밖에 없는 걸 생각해 9~1 순으로 우선순위 큐에서 나온 갯수만큼 저장하고 큐를 돌면서 출력하도록 하였다. 그리고 역시나 백준에 좀더 어려운 버전의 똑같은 문제가 존재했다.. [BOJ 1966 프린터 큐] : www.acmicpc.net/problem/1966 1966번: 프린터 큐 첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음 www.acmicpc.net 3년전에 문제를 풀어서 어떻게 풀었는지는 기억나지 않지만 queue 자료구조를 사용하지 않고 구현했었다. 프로그래머스 코..