알못에서 잘알까지

    4번 문제   

www.acmicpc.net/problem/1966

    내가 풀이한 답   

  문제에서 문서의 인덱스를 기준으로 문서를 찾아야 하기 때문에 <int, int> 쌍의 queue 자료구조와 문서의 중요도를 확인하기 위해 priority_queue 자료구조를 사용하였다. priority_queue의 첫 번째 요소와 queue의 중요도가 같지 않으면 queue의 첫 번째 요소를 뒤로 보내고 만약 priority_queue의 첫 번째 요소와 queue의 중요도가 같고 문서의 인덱스와 주어진 문제의 인덱스(m)와 같으면 종료하고 그렇지 않으면 priority_queue의 첫 번째 요소와 queue의 첫 번째 요소를 제거한다. 

//#include <bits/stdc++.h>
#include <iostream>
#include <queue>
using namespace std;
 
int main() {
	//freopen("input.txt", "rt", stdin);
	int t, i, n, m, j, a, idx, imp, cnt;
	cin >> t;
	for(i=0; i<t; i++){
		cnt=0;
		queue<pair<int, int> > q;
		priority_queue<int> pq;
		
		cin >> n >> m;
		for(j=0; j<n; j++){
			cin >> a;
			q.push({j, a});
			pq.push(a);
		}
		
		while(true){
			idx = q.front().first;
			imp = q.front().second;
			
			if(imp == pq.top()){
				cnt++;
				if(idx==m) break;
				q.pop();
				pq.pop();
			}
			else {
				q.push({idx, imp});
				q.pop();
			}
		}
		cout << cnt << endl;
	}
 
	return 0;
}

    3번 문제   

www.acmicpc.net/problem/11866

    내가 풀이한 답   

  k번째 까지 원소를 뒤로 넣은 다음 k번째 원소를 제거하는 행위를 원소가 하나 남을 때까지 이 과정을 반복하였다.

//#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int main() {
	//freopen("input.txt", "rt", stdin);
	queue<int> q;
	vector<int> v;
	int n, k, i;
	
	cin >> n >> k;
	
	for(i=1; i<=n; i++){
		q.push(i);
	}
	
	while(true){
		if(q.size()==1) {
			v.push_back(q.front());
			break;	
		}
		for(i=1; i<k; i++){
			q.push(q.front());
			q.pop();
		}
		v.push_back(q.front());
		q.pop();
	}
	
	cout << "<";
	for(i=0; i<v.size()-1; i++){
		cout << v[i] << ", ";
	}
	cout << v[v.size()-1] << ">";
	return 0;
}

    2번 문제   

www.acmicpc.net/problem/2164

    내가 풀이한 답   

  기본적인 큐를 사용하는 문제이다. 큐의 함수들을 안다면 쉽게 풀 수 있는 문제이다. 

//#include <bits/stdc++.h>
#include <iostream>
#include <queue>
using namespace std;
 
int main() {
	//freopen("input.txt", "rt", stdin);
	queue<int> q;
	int n, temp=0;
	cin >> n;
	
	for(int i=1; i<=n; i++){
		q.push(i);
	}
	
	
	while(true){
		if(q.size()==1) break;
		q.pop();
		temp = q.front();
		q.pop();
		q.push(temp);
	}
	
	cout << q.front();
}

    1번 문제   

    내가 풀이한 답   

 Stack 자료구조를 사용하였다. 이 문제를 풀 때 주의해야 할 점은 두 가지가 있는데 첫 번째는 while문에서 종료 조건문을 n이 k진수보다 작을 때 종료해야 한다는 점과 16진수에서 10이상 15이하의 숫자는 A~F로 표현된다는 점이다. 

//#include <bits/stdc++.h>
#include <iostream>
#include <stack>
using namespace std;
 
int main() {
	//freopen("input.txt", "rt", stdin);
	
	int n, k;
	char a[6] = {'A', 'B', 'C', 'D', 'E', 'F'};
	cin >> n >> k;
	stack<int> s;
	
	while(n>k-1){
		s.push(n%k);
		n = n/k;
 		if(n<k) {
 			s.push(n);	
		}
	}
	
	
	while(!s.empty()){
		if(k==16) {
			if(s.top()>=10) {
				cout << a[s.top()-10];
				s.pop();
			}
			cout << s.top();
			s.pop();	
		}
		else {
			cout << s.top();
			s.pop();	
		}	
	}
	
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int stack[100], top=-1;
 
void push(int x){
	stack[++top]=x;
}
int pop(){
	return stack[top--];
}
 
int main(){
	freopen("input.txt", "rt", stdin);
	int n, k;
	char str[20]="0123456789ABCDEF";
	scanf("%d %d", &n, &k);
	while(n>0){
		push(n%k);
		n=n/k;
	}
	while(top!=-1){
		printf("%c", str[pop()]);
	}	
	return 0;
}
 
 
 
 
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;		
int main(){
	freopen("input.txt", "rt", stdin);
	int n, k;
	stack<int> s;
	char str[20]="0123456789ABCDEF";
	scanf("%d %d", &n, &k);
	while(n>0){
		s.push(n%k);
		n=n/k;
	}
	while(!s.empty()){
		printf("%c", str[s.top()]);
		s.pop();
	}	
	return 0;
}

    10번 문제   

programmers.co.kr/learn/courses/30/lessons/43165

    내가 풀이한 답   

 더하는 경우와 빼는 경우만 고려하면 되므로 재귀 함수를 2번 호출하여 구하면 쉽게 구할 수 있다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int answer = 0;
 
void dfs(int level, int sum, vector<int> numbers, int target){
    if(level == numbers.size()){
        if(target==sum) {
            answer++;
        }
    }
    else {
        dfs(level+1, sum+numbers[level], numbers, target);
        dfs(level+1, sum-numbers[level], numbers, target);
    }
}
 
int solution(vector<int> numbers, int target) {
    
    dfs(0, 0, numbers, target);
    
    return answer;
}

    9번 문제   

    내가 풀이한 답   

 7, 8번 문제와 비슷한 유형을 계속 풀다보니 재귀함수를 몇 번 써야 하는지가 중요하게 느껴졌다.  7번과 8번은 포함o, 포함 x로 2가지의 경우만 고려하면 됐지만 위 문제 같은 경우는 +, -, 포함x 총 3가지의 경우를 고려해야 한다. 

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int n, m, a[11], count = 0;
 
void dfs(int level, int sum){
	if(level == n+1){
		if(m == sum) count++;
	}
	else {
		dfs(level+1, sum+a[level]);
		dfs(level+1, sum-a[level]);
		dfs(level+1, sum);
	}
}
	
int main() {
	//freopen("input.txt", "rt", stdin);
	int i;
	cin >> n >> m;
	for(i=1; i<=n; i++){
		cin >> a[i];
	}
	
	dfs(1, 0);
	
	if(count!=0) cout << count;
	else cout << -1; 
			
	return 0;
}

    사이트의 답안   

 
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int a[11], n, m, cnt=0;
void DFS(int L, int sum){
	if(L==n+1){
		if(sum==m){
			cnt++;
		}
	}
	else{
		DFS(L+1, sum+a[L]);
		DFS(L+1, sum);
		DFS(L+1, sum-a[L]);
	}
}
 
int main(){
	freopen("input.txt", "rt", stdin);
	int i;
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
	}
	DFS(1, 0);
	if(cnt==0) printf("-1\n");
	else printf("%d\n", cnt);
	return 0;
}
 

    8번 문제   

    내가 풀이한 답   

 앞의 7번 문제를 응용하면 쉽게 풀 수 있다. 

 두 개의 부분집합으로 나뉘기 때문에 부분집합의 총 합과 (전체 총 합 - 부분집합의 총 합)이 같으면 두 부분 집합이 같게 된 점을 이용하면 쉽게 풀 수 있다.

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int n, a[11], total=0;
bool flag = false;
 
void dfs(int level, int sum){
	if(level == n+1){
		if(total-sum == sum) flag = true; 
	}
	else {
		dfs(level+1, sum+a[level]);
		dfs(level+1, sum);
	}
}
 
int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int i;
	cin >> n;
	for(i=1; i<=n; i++){
		cin >> a[i];
		total+=a[i];
	}
	
	dfs(1, 0);
	
	if(flag) cout << "YES";
	else cout << "NO";
	
	return 0;
}

    사이트의 답안   

#include<stdio.h>
int n, a[11], total=0;
bool flag=false;
void DFS(int L, int sum){
	if(sum>(total/2)) return;
	if(flag==true) return;
	if(L==n+1){
		if(sum==(total-sum)){
			flag=true;
		}		
	}
	else{
		DFS(L+1, sum+a[L]);
		DFS(L+1, sum);
	}
}
int main(){
	freopen("input.txt", "rt", stdin);
	int i;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
		total+=a[i];
	}
	DFS(1, 0);
	if(flag) printf("YES\n");
	else printf("NO\n");
	return 0;
}

    7번 문제   

    내가 풀이한 답   

 위의 그림과 같이 완전탐색으로 n 값에 대한 부분집합을 구할 수 있다. 해당 숫자를 포함하는 경우와 포함하지 않는 경우를 나누면 해결할 수 있다.  

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int n, check[11];
 
void dfs(int level){
	if(level==n+1){
		for(int i=1; i<=n; i++){
			if(check[i]==1) cout << i << " ";
		}
		cout << endl;
	}
	else {
		check[level] = 1;
		dfs(level+1);
		check[level] = 0;
		dfs(level+1);
	}
}
 
int main() {
	//freopen("input.txt", "rt", stdin);
	cin >> n;
	
	dfs(1);
	return 0;
}

    사이트의 답안   

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n, ch[100];
void DFS(int L){
	int i;
	if(L==n+1){
		for(i=1; i<=n; i++){
			if(ch[i]==1) printf("%d ", i);
		}
		puts("");
	}
	else{
		ch[L]=1;
		DFS(L+1);
		ch[L]=0;
		DFS(L+1);
	}
}	
int main(){
	freopen("input.txt", "rt", stdin);
	scanf("%d", &n);
	DFS(1);
	return 0;
}