[기본과정, 4단계]

여기부터는 STL(c++)입니다.

이 단계는 중등부가 전국대회 준비할 때 학습하는 단계입니다.

4-1.vector
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>

using namespace std;
int main()
{
    int i,n;
    long long b;
    vector<long long> a;

    scanf("%d",&n);
    for(i=1; i<=n; i++){
        cin >> b;
        a.push_back(b);
    }
    a.pop_back();
    a.pop_back();
    
    for(i=0; i<a.size(); i++) cout << a[i] << " ";
    cout <<endl;
    
    return 0;
} 




4-2. deque
#include<iostream>
#include<deque>
using namespace std;

int main()
{
    int i,n;
    char b[10];
    deque<string> a;

    a.push_front("hi");
    a.push_front("good");
    a.push_back("babo");
    a.push_front("good2");
    a.push_back("babo2");
    
    a.pop_front();
    a.pop_back();
    
   for(i=0; i<a.size(); i++) cout << a[i] << " ";
   cout <<endl;
    
    return 0;
}  




4-3. set
#include <iostream>
#include <set>
using namespace std;

int main()
{
    set<int> m;
    set<int>::iterator i;

    m.insert(50);
    m.insert(30);
    m.insert(20);
    m.insert(70);
    m.insert(20);
    m.insert(10);
    m.insert(20);
    m.insert(20);

    for(i=m.begin(); i!=m.end(); i++){
        cout << *i << " ";
    }
    cout <<endl;

    return 0;
} 




4-4. multiset
#include <iostream>
#include <set>
using namespace std;

int main()
{
    multiset<int> m;
    multiset<int>::iterator i;

    m.insert(50);
    m.insert(30);
    m.insert(20);
    m.insert(70);
    m.insert(20);
    m.insert(10);
    m.insert(20);
    m.insert(20);

    for(i=m.begin(); i!=m.end(); i++){
        cout << *i << " ";
    }
    cout <<endl;
    cout <<m.count(20)<<endl;

    i=m.find(30);
    i++;
    cout << *i <<endl;

    return 0;
} 



4-5. map
#include <iostream>
#include <map>
using namespace std;

int main()
{
    map<int, int> m;
    map<int, int>::iterator i;

    m[4]=100;
    m[2]=300;
    m[7]=500;
    m[9]=400;
    m[6]=300;
    for(i=m.begin(); i!=m.end(); i++){
        cout << (*i).first << " "<<(*i).second << " " <<endl;
    }
    cout <<endl;

    for(i=m.begin(); i!=m.end(); i++){
        cout << i->first << " "<< i->second << " " <<endl;
    }
    cout <<endl;

    return 0;
} 




4-6. multimap
#include <iostream>
#include <map>
using namespace std;

int main()
{
    multimap<int, int> m;
    multimap<int, int>::iterator i;
    int j;

    m.insert(pair<int,int>(7,100));
    m.insert(pair<int,int>(6,200));
    m.insert(pair<int,int>(2,300));
    m.insert(pair<int,int>(4,400));
    m.insert(pair<int,int>(7,500));

    for(i=m.begin(); i!=m.end(); i++){
        cout << i->first << " "<< i->second << " " <<endl;
    }
    cout <<endl;

    i= m.find(7);
    cout << i->first << " "<< i->second <<endl;

    cout << m.count(7) <<endl;

    j=m.erase(7);
    for(i=m.begin(); i!=m.end(); i++){
        cout << i->first << " "<< i->second << " " <<endl;
    }
    cout <<endl;

    return 0;
} 




4-7. 최댓값 최솟값 초기화
#include <iostream>
#include <stdio.h>
#include <limits.h>
using namespace std;

int main()
{
    long long  min=LONG_LONG_MAX, max=LONG_LONG_MIN;

    printf("%lld %lld\n", min, max);

    return 0;
}




4-8. memset, fill
#include <iostream>
#include <stdio.h>
#include <memory.h>

using namespace std;

int main()
{
    int i;
    bool a[20], aa[20];
    char b[20], bb[20];
    int c[20], cc[20];
    memset(a, 0, sizeof(a));
    memset(b, 'A', sizeof(b));
    memset(c, 0, sizeof(c));

    fill(cc,cc+20, 5);
    fill(cc+10,cc+15, 7);
    fill(aa, aa+20, true);
    fill(bb, bb+20, 'G');

    for(i=0; i<20; i++) printf("%d",a[i]);printf("\n");
    for(i=0; i<20; i++) printf("%c",b[i]);printf("\n");
    for(i=0; i<20; i++) printf("%d",c[i]);printf("\n");

    for(i=0; i<20; i++) printf("%d",aa[i]);printf("\n");
    for(i=0; i<20; i++) printf("%c",bb[i]);printf("\n");
    for(i=0; i<20; i++) printf("%d",cc[i]);printf("\n");

    return 0;
}




4-9. 1차원 sort
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;

int a[100];
int main()
{
    int i;

    for(i=0; i<5; i++)scanf("%d",&a[i]);
    sort(a, a+5);
    for(i=0; i<5; i++)printf("%d ",a[i]);
    printf("\n");

    return 0;
} 




4-10. 2차원 sort
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;

struct data{
    int aa,bb,cc;
};
int dc(const data p, const data q)
{
    return p.cc < q.cc;
}
int main()
{
    data a[5];
    int i;

    for(i=0; i<5; i++)scanf("%d %d %d",&a[i].aa, &a[i].bb, &a[i].cc);
    sort(a, a+5, dc);
    printf("sort...\n");
    for(i=0; i<5; i++)printf("%d %d %d\n",a[i].aa, a[i].bb, a[i].cc);
    printf("\n");

    return 0;
} 




4-11. 문자열 포함한 2차원Sort
include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <string.h>
using namespace std;

struct data{
    float aa;
    int bb;
    char cc[10];
};
int dc(const data p, const data q)
{
    if(strcmp(p.cc, q.cc)==1) return 0;
    else return 1;
}
int main()
{
    data a[5];
    int i;

    for(i=0; i<3; i++)scanf("%f %d %s",&a[i].aa, &a[i].bb, a[i].cc);
    sort(a, a+3, dc);
    printf("sort...\n");
    for(i=0; i<3; i++)printf("%f %d %s\n",a[i].aa, a[i].bb, a[i].cc);
    printf("\n");

    return 0;
}

더 많은 STL과 알고리즘에 관하여 공부하려면
"출판사 한빛미디어, 뇌를 자극하는 C++STL" 책과 
"출판사 한빛미디어, 뇌를 자극하는 알고리즘" 책을 
구입하시어 참고하세요!
이 곳의 STL 소스의 출처도 이 책의 도움을 받았습니다.

- list

#include <iostream>
#include <stdio.h>
#include <list>
using namespace std;

int main()
{
    list <int> t;

    t.push_back(10);

    list <int> :: iterator i;
    for(i=t.begin(); i !=t.end(); ++i) printf("%d ",*i);
    printf("\n");

    return 0;
} 




- list에서 삭제

#include <iostream>
#include <stdio.h>
#include <list>
using namespace std;

int main()
{
    int j;
    list <int> tt;
    list <int>::iterator ii;
    list <int>::iterator jj=tt.begin();

    tt.push_back(10);
    tt.push_back(20);
    tt.push_front(30);
    tt.push_front(40);
    tt.push_front(50);
    tt.push_front(45);

    for(ii=tt.begin(); ii !=tt.end(); ii++) printf("%d ",*ii);
    printf("\n");

    for(j=1; j<=2; j++) ++jj; ii=tt.erase(jj);

    for(ii=tt.begin(); ii !=tt.end(); ii++) printf("%d ",*ii);
    printf("\n");

    return 0;
} 




- list 중간 삭제 후 삽입(대체)

#include <iostream>
#include <stdio.h>
#include <list>
using namespace std;
int main()
{    
    list <int> tt;
    list <int>::iterator ii;
    list <int>::iterator jj=tt.begin();

    tt.push_back(10);    tt.push_back(20);    tt.push_front(30);   
    tt.push_front(40);   tt.push_front(50);   tt.push_front(45);
    
    int j;
    for(j=1; j<=2; j++) ++jj; ii=tt.erase(jj);
    jj=ii; ii=tt.insert(jj,60);

    for(ii=tt.begin(); ii !=tt.end(); ii++) printf("%d ",*ii);printf("\n");

    return 0;
}




- list 일괄삭제

#include <iostream>
#include <stdio.h>
#include <list>
using namespace std;
int main()
{
    list <int> tt;
    list <int>::iterator ii;
    list <int>::iterator jj=tt.begin();

    tt.push_back(10);    tt.push_back(20);    tt.push_front(30);
    tt.push_front(40);   tt.push_front(10);   tt.push_front(10);
/*
    int j;
    for(j=1; j<=2; j++) ++jj; ii=tt.erase(jj);
    jj=ii; ii=tt.insert(jj,60);
*/
    for(ii=tt.begin(); ii !=tt.end(); ii++) printf("%d ",*ii);printf("\n");

    tt.remove(10);
    for(ii=tt.begin(); ii !=tt.end(); ii++) printf("%d ",*ii);printf("\n");

    return 0;
} 




- 조건 삭제

#include <iostream>
#include <stdio.h>
#include <list>
using namespace std;
bool p(int n){return n>=20 && n<=50;}
int main()
{
    list <int> tt;
    list <int>::iterator ii;
    list <int>::iterator jj=tt.begin();

    tt.push_back(10);    tt.push_back(20);    tt.push_front(30);
    tt.push_front(70);   tt.push_front(10);   tt.push_front(10);
/*
    int j;
    for(j=1; j<=2; j++) ++jj; ii=tt.erase(jj);
    jj=ii; ii=tt.insert(jj,60);
*/
    for(ii=tt.begin(); ii !=tt.end(); ii++) printf("%d ",*ii);printf("\n");

    tt.remove_if(p);
    for(ii=tt.begin(); ii !=tt.end(); ii++) printf("%d ",*ii);printf("\n");

    return 0;
} 




- list sort

#include <iostream>
#include <stdio.h>
#include <list>
using namespace std;
bool p(int n){return n>=20 && n<=50;}
int main()
{
    list <int> tt;
    list <int>::iterator ii;
    list <int>::iterator jj=tt.begin();

    tt.push_back(10);    tt.push_back(20);    tt.push_front(30);
    tt.push_front(70);   tt.push_front(10);   tt.push_front(10);

    int j;
    for(j=1; j<=3; j++) ++jj; ii=tt.erase(jj);
    jj=ii; ii=tt.insert(jj,60);

    tt.sort();
    for(ii=tt.begin(); ii !=tt.end(); ii++) printf("%d ",*ii);printf("\n");

    return 0;
} 



n! (비순환)

#include<iostream>
#include<stack>
using namespace std;
stack<int> s;
int main()
{
	int n,nn;

	cin >> n;
	nn=n;
	while(1){
		s.push(nn);
		if(nn==1)break;
		nn--;
	}
	while(1){
		nn=s.top(); s.pop(); 
		s.top()*=nn;
		if(s.size()==1)break;
	}
	cout << s.top();
	
	return 0;
}



피보나치 (비순환)

#include<iostream>
#include<stack>
using namespace std; 
stack<int> s;
int d[1004]; 
int main()
{
	int n,nn,sp=0,np;

	cin >> n;
	d[1]=1; d[2]=1; nn=n;
	while(1)
	{
		s.push(nn);
		if(d[nn]!=0)break;
		nn--;
	}
	while(1)
	{
		nn=s.top(); s.pop(); 
		if(s.size()==0)break;
		np=nn-1;
		d[s.top()]=d[nn]+d[np];
	}
	cout << d[nn];

	return 0;
}



2진트리 전위 (비순환)

#include<iostream>
#include<stack>
using namespace std;
stack<int> s;

int main()
{
	int n,sp=0,nl,nr;

	cin >> n;
	s.push(1);
	while(1){
		cout << s.top() << " ";
		nl=s.top()*2; nr=s.top()*2+1; s.pop();
		if(nr<=n)s.push(nr);
		if(nl<=n)s.push(nl);
		if(s.size()==0)break;
	}
	cout << endl;

	return 0;
}



2진트리 중위 (비순환)

#include<iostream>
#include<stack>
using namespace std;
stack<int> s; bool d[1004];

int main()
{
	int n,sp=0,nl,nr; 

	cin >> n;
	s.push(1);
	while(1){
		if(d[s.top()]==0){
			nl=s.top()*2; d[s.top()]=1;
			if(nl <= n)s.push(nl);
		}else{
			cout << s.top() << " ";
			nr=s.top()*2+1; s.pop();
			if(nr<=n)s.push(nr);
		}
		if(s.size()==0)break;
	}

	return 0;
}

 

2진트리 후위 (비순환)

#include<iostream>
#include<stack>
using namespace std;
stack<int> s;
bool d[1004];

int main()
{
	int n,sp=0,a,nl;
	cin >> n;
	s.push(1);
	while(1){
		if(d[s.top()]==0){
			nl=s.top()*2; d[s.top()]=1;
			if(nl<=n)s.push(nl);
			else {
				cout << s.top() << " "; 
				a=s.top(); s.pop();
				if(a%2==0)if(a+1<=n)s.push(a+1);
			}
		}
		else {
			cout << s.top() << " "; 
			a=s.top(); s.pop();
		}
		if(sp==0)break;
	}
	
	return 0;
}



- 2011년 지역본선 고등부3번 줄 세우기 참고

#include <iostream>
#include <stdio.h>
#include <list>
using namespace std;
int d[100001], f[100001];
int main()
{
    list <int> tt;
    list <int>::iterator ii;
    list <int>::iterator jj=tt.begin();
    int n,i,a,j,cc=0;

    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d",&a);
        tt.push_back(a);
    }
    tt.sort();
    for(ii=tt.begin(); ii !=tt.end(); ii++) printf("%d ",*ii);printf("\n");

    for(i=1; i<=n; i++)scanf("%d",&d[i]);
    for(i=n; i>=1; i--){
        jj=tt.begin(); for(j=0; j<d[i]; j++) ++jj;
        cc++; f[cc]=*jj;
        ii=tt.erase(jj);
    }
    for(i=n; i>=1; i--)cout <<f[i]<< " ";
    return 0;
} 




- 제26회 지역본선 초등부4번 탑

#include <iostream>
#include <stdio.h>
#include <list>
using namespace std;
int d[100001], f[100001];
int main()
{
    list <int> t1;
    list <int>::iterator i1;
    list <int>::iterator j1=t1.begin();

    list <int> t2;
    list <int>::iterator i2;
    list <int>::iterator j2=t2.begin();
    int n,i,a,j,k,f=0;

    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d",&a);\
        t1.push_back(a);
        t2.push_back(i);
        i1=t1.end(); i2=t2.end();
        for(j=i; j>0; j--){
            --i1; --i2;
            if(a < *i1){
                f=0;
                printf("%d ", *i2);
                break;
            }
            else if(a > *i1){
                j1=t1.erase(i1); i1=j1;
                j2=t2.erase(i2); i2=j2;
            }
            if(i1==t1.begin()){
                f=1;
                break;
            }
        }
        if(f==1)printf("0 ");
    }
    printf("\n");
    return 0;
} 




- 2012년 중등부 2번 회전초밥 list 바전

#include <iostream>
#include <stdio.h>
#include <list>
using namespace std;
int d[100001], z[100001];
int main()
{
    list<int> t;
    list<int>::iterator i1=t.begin();
    list<int>::iterator i2;

    int i, n, a, j,k;
    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    scanf("%d",&n);

    for(i=0; i<n; i++){
        scanf("%d",&a);
        i1=t.begin();
        for(j=0; j<n; j++){
            if(a > *i1) ++i1;
            else break;
        }
        i2=t.insert(i1,a);
    }
    for(i1=t.begin(); i1 !=t.end(); i1++) printf("%d ", *i1);printf("\n");

    return 0;
} 




- 삽입정렬 1(list)

#include <iostream>
#include <stdio.h>
#include <list>
using namespace std;
int d[100001], z[100001];
int main()
{
    list<int> t;
    list<int>::iterator i1=t.begin();
    list<int>::iterator i2;

    int i, n, a, j,k;
    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    scanf("%d",&n);

    for(i=0; i<n; i++){
        scanf("%d",&a);
        i1=t.begin();
        for(j=0; j<n; j++){
            if(a > *i1) ++i1;
            else break;
        }
        i2=t.insert(i1,a);
    }
    for(i1=t.begin(); i1 !=t.end(); i1++) printf("%d ", *i1);printf("\n");

    return 0;
} 




- 삽입정렬 2(list)

#include <iostream>
#include <stdio.h>
#include <list>
using namespace std;

int main()
{
    list<int> t;
    list<int>::iterator i1;
    list<int>::iterator i2;

    int i, n, a,k;
    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    scanf("%d",&n);
    cin >> a;
    t.push_back(a);
    for(i=2; i<=n; i++){
        cin >> a;
        i1=t.end(); i1--;
        while(1){
            if(a > *i1) break;
            if(i1 == t.begin()) break;
            i1--;
        }
        i1++;
        i2=t.insert(i1,a);
    }
    for(i1=t.begin(); i1 !=t.end(); i1++) printf("%d ", *i1);printf("\n");

    return 0;
}




-삽입정렬 3(list)

#include <iostream>
#include <stdio.h>
#include <list>
using namespace std;

int main()
{
    list<int> t;
    list<int>::iterator i1;
    list<int>::iterator i2;

    int i, n, a,k;
    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    scanf("%d",&n);
    cin >> a;
    a=10000-a;
    t.push_back(a);
    for(i=2; i<=n; i++){
        cin >> a;
        a=10000-a;
        i1=t.end();
        while(1){
            i1--;
            if(a > *i1) break;
            if(i1 != t.begin()) continue;
        }
        i1++;
        i2=t.insert(i1,a);
    }
    for(i1=t.begin(); i1 !=t.end(); i1++) printf("%d ", 10000-*i1);printf("\n");

    return 0;
} 




- merge sort(list)

#include <iostream>
#include <stdio.h>
#include <list>
#include <algorithm>
using namespace std;

int main()
{
    list<int> t;
    list<int> tt;
    list<int>::iterator i1=t.begin();
    list<int>::iterator i2=tt.begin();

    int i, n, a, j,k;
    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    scanf("%d",&n);

    for(i=0; i<n; i++){
        scanf("%d",&a);
        i1=t.begin();
        for(j=0; j<n; j++){
            if(a > *i1) ++i1;
            else break;
        }
        i2=t.insert(i1,a);
    }

    for(i1=t.begin(); i1 !=t.end(); i1++) printf("%d ", *i1);printf("\n");

    tt.push_back(1);
    tt.push_back(5);
    for(i2=tt.begin(); i2 !=tt.end(); i2++) printf("%d ", *i2);printf("\n");

    t.merge(tt);
    for(i1=t.begin(); i1 !=t.end(); i1++) printf("%d ", *i1);printf("\n");


    return 0;
}




- 단지번호 붙이기 (vector)

#include<lstdio.h>
#include<liostream>
#include<lvector>
using namespace std;
int d[100][100];
int main()
{
    int i,j,n,xx,yy;
    vector<lint> dx,dy;

    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    scanf("%d",&n);
    for(i=1; i<l=n; i++){
        for(j=1; j<l=n; j++){
            scanf("%d",&d[i][j]);
        }
    }
    while(1){    
        cout <l<lendl;
        int ff=0;
        for(i=1; i<l=n; i++){
            for(j=1; j<l=n; j++){
                if(d[i][j]==1){
                    dx.push_back(i);
                    dy.push_back(j);
                    ff=1;
                    break;
                }
            }
            if(ff==1)break;
        }    
        if(ff==0)break;
        
        while(1){
            if(dx.size()==0) break;
            cout <l<l dx.back() <l<l "," <l<ldy.back() <l<lendl;
    
            if(d[dx.back()][dy.back()]==1){    
                xx =dx.back(); yy=dy.back();
                d[dx.back()][dy.back()]=0;            
                dx.pop_back(); dy.pop_back();    
        
                if(d[xx-1][yy]==1){
                    dx.push_back(xx-1);
                    dy.push_back(yy);
                }
                if(d[xx][yy-1]==1){
                    dx.push_back(xx);
                    dy.push_back(yy-1);
                }    
                if(d[xx+1][yy]==1){
                    dx.push_back(xx+1);
                    dy.push_back(yy);
                }    
                if(d[xx][yy+1]==1){
                    dx.push_back(xx);
                    dy.push_back(yy+1);
                }    
            }else{dx.pop_back(); dy.pop_back();}        
        }    
    }
    for(i=1; i<l=n; i++){
        for(j=1; j<l=n; j++){
            printf("%d ",d[i][j]);
        }
        printf("\n");
    }

    return 0;
} 



- 단지번호 붙이기 (deque)

#include<stdio.h>
#include<iostream>
#include<deque>
using namespace std;
int d[100][100];
int main()
{
    int i,j,n,xx,yy;
    deque<int> dx,dy;

    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    scanf("%d",&n);
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            scanf("%d",&d[i][j]);
        }
    }
    while(1){    
        cout <<endl;
        int ff=0;
        for(i=1; i<=n; i++){
            for(j=1; j<=n; j++){
                if(d[i][j]==1){
                    dx.push_back(i);
                    dy.push_back(j);
                    ff=1;
                    break;
                }
            }
            if(ff==1)break;
        }    
        if(ff==0)break;
        
        while(1){
            if(dx.size()==0) break;
            cout << dx.front() << "," <<dy.front() <<endl;
    
            if(d[dx.front()][dy.front()]==1){    
                xx =dx.front(); yy =dy.front();
                d[dx.front()][dy.front()]=0;            
                dx.pop_front(); dy.pop_front();    
        
                if(d[xx-1][yy]==1){
                    dx.push_back(xx-1);
                    dy.push_back(yy);
                }
                if(d[xx][yy-1]==1){
                    dx.push_back(xx);
                    dy.push_back(yy-1);
                }    
                if(d[xx+1][yy]==1){
                    dx.push_back(xx+1);
                    dy.push_back(yy);
                }    
                if(d[xx][yy+1]==1){
                    dx.push_back(xx);
                    dy.push_back(yy+1);
                }    
            }else{dx.pop_front(); dy.pop_front();}        
        }    
    }

    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            printf("%d ",d[i][j]);
        }
        printf("\n");
    }

    return 0;
}