취준생의 메모장

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

#include<deque>
#include<iostream>

using namespace std;

int main(){
    int n;
    cin>>n;
    deque<int> d;
    for (int i = 1; i <= n; i++)
        d.push_back(i);
    while(1)
    {
        if(d.size()==1){
            cout<<d.front()<<'\n';
            return 0;
        }
        d.pop_front();
        int x=d.front();
        d.pop_front();
        d.push_back(x);
    }
}

덱 자료구조를 활용해서 풀었는데 생각해보니 큐로도 충분하다.

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

#include<iostream>
//#include<cstdio>
using namespace std;

typedef struct node{
    int data;
    struct node* right;
    struct node* left;
}node;

node* preorder(node * root,int input){
    if(!root)
    {
        root = new node();
        root->data = input;
        root->left = root->right=NULL;
    }
    else if(root->data > input)
        root->left=preorder(root->left,input);
    else
        root->right=preorder(root->right,input); 
    return root;
}
void postorder(node *root)
{
    if(root)
    {
        postorder(root->left);
        postorder(root->right);
        cout<<root->data<<"\n";
    }
}
int main(){

    int input;
    node* root=NULL;
    while(cin>>input)
        root=preorder(root,input);
    postorder(root);
    return 0;
}

이진 검색 트리를 생성할 때는 전위 순회를, 출력할 때는 후위 순회를 하는 문제이다.

이 문제를 풀면서 했던 오류는 먼저 트리를 배열을 이용해서 만들고자 했던 것이다. 최대로 들어오는 input의 개수가 10000개라 배열로 해야겠다는 잘못된 생각을 했다.

이진 검색 트리의 경우 생성시에 최대 트리의 높이가 O(n) 일 수 있기 때문에 최악의 경우에 10000번째 들어오는 노드에 해당하는 인덱스가 2^9999 일 수 있다는 것이다. 이렇게 하면 무조건 터질 수밖에 없다.

따라서 노드를 구조체를 이용해서 만들어 트리를 구현하였다.

여기서 했던 실수는 함수 내부에서 new 연산을 통해서 새로운 메모리를 할당해 온 뒤 루트에 연결하지 않고 재귀적으로 함수를 실행 했던 것이었다.

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

#include<iostream>
using namespace std;
int main(){
    int n,m;
    unsigned long long arr[101][101]={0,};
    unsigned long long arr2[101][101]={0,};

    cin>>n>>m;
    
    arr[1][0]=1;
    arr[1][1]=1;
    for (int i = 2; i <101; i++)
    {
        arr[i][0]=1;
        arr[i][i]=1;
    }
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <=i-1; j++)
            {
                arr[i][j]=arr[i-1][j-1]+arr[i-1][j];
                arr2[i][j]=arr2[i-1][j-1]+arr2[i-1][j];
                if(arr[i][j]>=1000000000000000000LL)
                {
                    arr2[i][j]+=arr[i][j]/1000000000000000000LL;

                    arr[i][j]%=1000000000000000000LL;
                }
            }
    if(!arr2[n][m])
        cout<<arr[n][m]<<"\n";
    else
        cout<<arr2[n][m]<<arr[n][m]<<"\n";
    return 0;
}

long long 이상의 값이 도출될 가능성을 전혀 생각도 하지 않고 풀다가 두 번쯤 틀리고 나니깐

예전에 big integer 때문에 파이썬을 쓴다는 말을 들었던 기억이 났다.

그래서 해결방법을 알아보니 long long int 배열을 두개 사용해서 어떤 임계값보다 크게 나올 경우 두 번째 배열의 값에 임계값으로 나눈 몫을 담고 기존에 값은 임계값으로 나눈 나머지를 담는 방식으로 long long을 벗어나는 범위의 수를 나타낼 수 있다는 것을 알게 되었다.

실버 3이라고 쉽게 생각하고 풀다가 숫자 범위를 표현하는 것에서 막힐 것이라는 생각은 전혀 못했다. 파이썬으로 문제 푸는 것을 연습해야겠다고 생각된 날이다!

#pragma waring(disable:4996)
#include<cstdio>
#include<queue>

using namespace std;
int main() {
	int n;
	priority_queue<int> pq;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		int x;
		scanf("%d", &x);
		if (x != 0)
			pq.push(-x);
		if (x == 0) {
			if (pq.empty())
				printf("0\n");
			else {
				printf("%d\n", -pq.top());
				pq.pop();
			}
		}
	}
}

STL 중에서 우선순위 큐를 이용하여 최소 힙을 구현한 것이다.

우선순위 큐는 따로 정렬 규칙을 정하지 않는다면 값이 큰 것이 우선순위가 높은 최대 힙 구조이다.

따라서 문제에서 요구하는 최소 힙을 구현하기 위해서는 마이너스 부호를 붙여서 값을 넣어주어야 하고,

출력할 때는 다시 마이너스를 붙여서 원래의 값이 나올 수 있도록 하였다.

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

#pragma waring(disable:4996)
#include<cstdio>
#include<queue>

using namespace std;
int main() {
	int n;
	priority_queue<int> pq;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		int x;
		scanf("%d", &x);
		if (x != 0)
			pq.push(x);
		if (x == 0) {
			if (pq.empty())
				printf("0\n");
			else {
				printf("%d\n", pq.top());
				pq.pop();
			}
		}
	}

}

STL 중에서 우선순위 큐를 이용하면 간단하게 풀 수 있다!

시간복잡도는 O(nlogn)이다.

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

#include<cstdio>
#include<queue>
#include<vector>

using namespace std;
int a[50][50];
int dx[8]={0,0,1,-1,1,1,-1,-1};
int dy[8]={1,-1,0,0,-1,1,1,-1};
int col,row;
bool vis[50][50];
void bfs(int x,int y){
	queue<pair<int,int> > q;
	vis[x][y] = 1;
	q.push(make_pair(x,y));

	while(!q.empty())
	{
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop();
		for(int i=0;i<8;i++)
		{
			int nx = cx+dx[i];
		   	int ny = cy+dy[i];
			if(nx<0||ny<0||nx>=row||ny>=col)
				continue;
			if(vis[nx][ny]||!a[nx][ny])
				continue;
			q.push(make_pair(nx,ny));
			vis[nx][ny] =1;
		}	
	}
}
void init_v(bool vis[][50])
{
	for(int i=0;i<50;i++)
		for(int j=0;j<50;j++)
			vis[i][j]=0;
}
int main()
{
	while(1)
	{
		int cnt=0;
		init_v(vis);
		scanf("%d %d",&col,&row);
		if(!col&&!row)
			return 0;
		for(int i=0;i<row;i++)
			for(int j=0;j<col;j++)
				scanf("%d",&a[i][j]);
		//bool vis[50][50]={0,};
		for(int i=0;i<row;i++){
			for(int j=0;j<col;j++){
				if(!vis[i][j]&&a[i][j])
				{
					bfs(i,j);
					cnt++;
				}
			}
		}
		printf("%d\n",cnt);
	}
	return 0;
}

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

#include<cstdio>
#include<string.h>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
    int people;
    vector<int> v;
    scanf("%d",&people);
    for (int i = 0; i < people; i++)
    {
        int x;
        scanf("%d",&x);
        v.push_back(x);
    }
    sort(v.begin(),v.end());
    for (int i = 1; i < v.size(); i++)
    {
        v[i]+=v[i-1];
    }
    int sum=0;
    for (int i = 0; i < v.size(); i++)
    {
        sum+=v[i];
    }
    printf("%d\n",sum);
    return 0;
}

#include<cstdio>
#include<string.h>
#include<vector>
using namespace std;
char a[51];
char res[51];
int alp[26];
int main(){
    vector<int> v;
    scanf("%s",&a);
    for (int i = 0; i < strlen(a); i++)
    {
        alp[a[i]-'A']++;
    }
    int odd=0;
    int even=0;
    int odd_pos;
    for (int i = 0; i < 26; i++)
    {
        if(alp[i]>0)
        {
            if(alp[i]%2==1)
            {
                odd++;
                odd_pos = i;
                if(alp[i]>1)
                {
                    v.push_back(i);
                }
            }
            else
            {
                even++;
                v.push_back(i);
            }
        }
    }
    int len = strlen(a);
    if(len%2 == 1){
        if(odd!=1){
            printf("I'm Sorry Hansoo\n");
            return 0;
        }
        res[len/2] = 'A' + odd_pos;
        alp[odd_pos]--;
        int x=0;
    
        for (int i = 0; i < v.size(); i++)
        {
             
            while(alp[v[i]])
            {
                res[x] = v[i] + 'A';
                res[len-1-x] = v[i] + 'A';
                x++;
                alp[v[i]]-=2;
            }
        }
    }
    else{
        if(odd){
            printf("I'm Sorry Hansoo\n");
            return 0;
        }
        int x=0;
        for (int i = 0; i < v.size(); i++)
        {
             
            while(alp[v[i]])
            {
                res[x] = v[i] + 'A';
                res[len-1-x] = v[i] + 'A';
                x++;
                alp[v[i]]-=2;
            }
        }
    }
    printf("%s\n",res);
}

#include<cstdio>

using namespace std;
int main(){
    int a, b;
    scanf("%d %d",&a,&b);
    int cnt=0;
    while(a<b)
    {
        if(b%2==0){
            b/=2;
            cnt++;
        }
        else if(b%10==1)
        {
            b/=10;
            cnt++;
        }
        else
        {
            printf("-1\n");
            return 0;
        }
    }
    if(a==b)
        printf("%d\n",cnt+1);
    else
        printf("-1\n");
    return 0;
}

알고리즘 분류에 너비 우선 탐색이라고 되어있는데 그냥 수학으로도 풀렸다

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
int arr[100001];
vector<int> v[100001];
bool vis[100001];
void bfs(int vtx){
    queue<int> q;
    q.push(vtx);
    vis[vtx]=1;
    arr[vtx]= -1;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(auto i:v[now])
        {
            if(vis[i])
                continue;
            q.push(i);
            vis[i] = 1;
            arr[i] = now;
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n-1; i++)
    {
        int s,e;
        scanf("%d %d",&s,&e);
        v[s].push_back(e);
        v[e].push_back(s);
    }
    bfs(1);
    for(int i=2;i<=n;i++)
        printf("%d\n",arr[i]);
}

루트가 1번 vertex로 정해져 있기 때문에 1번부터 시작해서 bfs 방식을 이용해 부모의 vertex 값을 넣어주면 된다!