도전 프로 그래 밍 경기 2 - 알고리즘 과 데이터 구조

먼저 기 초 를 잘 다 졌 으 니 이 책 을 한 번 닦 아 라!!
글 목록

제2 장

2.5 입문 문제

제3 장 초등 정렬

3.2 정렬 법 삽입

3.3 거품 정렬 법

3.4 정렬 법 선택

제4 장 데이터 구조

4.2 스 택 역 폴란드 표현 식

4.3 대기 열 임무 스케줄 링 모델

4.4 링크

4.6 계산 면적

제5 장 검색

5.2 선형 검색

5.3 2 점 검색

5.4 산열 법 해시 표 의 실현

제6 장 재 귀 와 분 치 법

6.2 빈 거 검색

제7 장 고등 정렬

7.1 병합 정렬

제8 장 나무

8.2 뿌리 나무의 표현

8.3 이 진 트 리 의 표현

8.4 나무의 옮 겨 다 니 기

제1 1 장 동적 기획 법

피 보 나치 수열

제1 2 장 그림

12.4 광도 우선 검색

제1 7 장 동적 기획 법

17.3 최 장 증가 서브 시퀀스

제2 장
2.5 입문 문제
ALDS1_1_D:Maximum Profit

#include
using namespace std;
int n,ma=INT_MIN,mi=INT_MAX,num;//     ，
//      int         INT_MAX INT_MIN
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>num;
        ma=max(ma,num-mi);//       
        mi=min(mi,num);//    i      
    }
    cout<<ma<<"
";
}

제3 장 초등 정렬
3.2 정렬 법 삽입
ALDS1_1_A:Insertion Sort

#include
using namespace std;
const int maxn=100+10;
int n,arr[maxn];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    for(int i=0;i<n;i++){
        int v=arr[i];//      
        int j=i-1;
        while(j>=0&&arr[j]>v){//  v           
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=v;// v    v                      
        for(int i=0;i<n;i++){
            if(i) cout<<" "<<arr[i];
            else cout<<arr[i];
        }cout<<"
";
    }
}

3.3 거품 정렬 법
ALDS1_2_A:Bubble Sort

#include
using namespace std;
const int maxn=100+10;
int n,arr[maxn],cnt=0;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    bool flag=1;
    for(int i=0;flag;i++){
        flag=0;//            ，        ，     
        for(int j=n-1;j>i;j--){//     
            if(arr[j-1]>arr[j]){
                flag=1;
                swap(arr[j],arr[j-1]);
                cnt++;
            }
        }
    }
    for(int i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<arr[i];
    }
    cout<<"
"<<cnt<<"
";
}

3.4 정렬 법 선택
ALDS1_2_B:Selection Sort

//  1
#include
using namespace std;
const int maxn=100+10;
int n,arr[maxn],cnt=0;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    for(int i=0;i<n;i++){
        int minj=i;
        for(int j=i;j<n;j++){//               
            if(arr[j]<arr[minj]){
                minj=j;
            }
        }
        if(i!=minj){
            cnt++;
            swap(arr[i],arr[minj]);
        }
    }
    for(int i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<arr[i];
    }
    cout<<"
"<<cnt<<"
";
}
//  2
#include
using namespace std;
const int maxn=100+10;
int n,arr[maxn],cnt=0;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    for(int i=0;i<n;i++){
        int minj=i;
        minj=min_element(arr+i,arr+n)-arr;//min_element             ，      *min_element(begin,end),        min_element(begin,end)-arr
        if(i!=minj){
            cnt++;
            swap(arr[i],arr[minj]);
        }
    }
    for(int i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<arr[i];
    }
    cout<<"
"<<cnt<<"
";
}

제4 장 데이터 구조
4.2 스 택 역 폴란드 식
ALDS1_3_A:Stack

#include
using namespace std;
int main()
{
    stack<int>st;
    char s[100];
    while(cin>>s){
        int a,b;
        if(s[0]=='+'){
            a=st.top();st.pop();
            b=st.top();st.pop();
            st.push(b+a);
        }else if(s[0]=='-'){
            a=st.top();st.pop();
            b=st.top();st.pop();
            st.push(b-a);
        }else if(s[0]=='*'){
            a=st.top();st.pop();
            b=st.top();st.pop();
            st.push(b*a);
        }else st.push(atoi(s));//atoi()                  
    }
    cout<<st.top()<<"
";
}

4.3 대기 열 작업 스케줄 링 모델
ALDS1_3_B:Queue

#include
using namespace std;
struct node {
    char name[100];
    int t;
};
int main() {
    int n,q,t;
    scanf("%d%d",&n,&q);
    queue<node>qu;//   queue >qu  
    for(int i=0; i<n; i++) {
        node N;
        scanf("%s%d",N.name,&N.t);
        qu.push(N);
    }
    int sum=0;
    while(!qu.empty()) {
        node this_node=qu.front();
        qu.pop();
        sum+=min(this_node.t,q);
        if(this_node.t<=q) {
            printf("%s %d
",this_node.name,sum);
        } else {
            this_node.t-=q;
            qu.push(this_node);
        }
    }
}

4.4 링크
ALDS1_3_C:Doubly Linked List

#include
using namespace std;
int main()
{
    list<int>lst;
    int num;char c[20];
    int n;scanf("%d",&n);
    while(n--){
        scanf("%s",c);
        if(c[0]=='i') {scanf("%d",&num);lst.push_front(num);}
        else if(c[6]=='F') lst.pop_front();//deleteFirst
        else if(c[6]=='L') lst.pop_back();//deleteLast
        else if(c[0]=='d'){
            scanf("%d",&num);
            for(list<int>::iterator it=lst.begin();it!=lst.end();it++){
                if(*it==num) {
                    lst.erase(it);break;
                }
            }
        }
    }
    int i=0;
    for(list<int>::iterator it=lst.begin();it!=lst.end();it++) {
        if(i++) printf(" ");
        printf("%d",*it);
    }
    printf("
");
    return 0;
}
//  STL 
#include
using namespace std;
struct Node {
    int key;
    Node *prev,*next;
};
Node *nil;
void init() {
    nil=(Node *)malloc(sizeof(Node));
    nil->next=nil;
    nil->prev=nil;
}
Node * listSearch(int key) {
    Node *cur=nil->next;//             
    while(cur!=nil&&cur->key!=key) {
        cur=cur->next;
    }
    return cur;
}
void printList() {
    Node *cur=nil->next;
    int isf=0;
    while(1) {
        if(cur==nil) break;
        if(isf++>0) printf(" ");
        printf("%d",cur->key);
        cur=cur->next;
    }
    printf("
");
}
void deleteNode(Node *t) {
    if(t==nil) return ;//t         
    t->prev->next=t->next;
    t->next->prev=t->prev;
    free(t);
}
void deleteFirst() {
    deleteNode(nil->next);
}
void deleteLast() {
    deleteNode(nil->prev);
}
void deleteKey(int key){
    deleteNode(listSearch(key));
}
void insert(int key){
    Node *x=(Node *)malloc(sizeof(Node));
    x->key=key;
    //         
    x->next=nil->next;
    x->next->prev=x;
    nil->next=x;
    x->prev=nil;
}
int main() {
    char c[20];
    int n,num;
    init();
    scanf("%d",&n);
    while(n--){
        scanf("%s",c);
        if(c[0]=='i') {scanf("%d",&num);insert(num);}
        else if(c[6]=='F') deleteFirst();
        else if(c[6]=='L') deleteLast();
        else if(c[0]=='d'){
            scanf("%d",&num);
            deleteKey(num);
        }
    }
    printList();
}

4.6 면적 계산
ALDS1_3_D: Areas on the Cross - Section Diagram 이라는 문 제 는 모든 고인 물 구역 의 총 면적 과 얼마 가 있 는 지, 각 고인 물 구역 의 면적 이 각각 얼마 인지 구 하 는 것 입 니 다.

#include
using namespace std;
int main()
{
    stack<int>st;//    \   j，     \/     （         ）
    //  \/      i-j
    stack<pair<int,int> >area;
    char c;
    int sum=0;
    for(int i=0;cin>>c;i++){
        if(c=='\\') st.push(i);
        else if(c=='/'&&st.size()>0){
            int j=st.top();st.pop();
            sum+=(i-j);//  \/      i-j
            int a=i-j;
            while(area.size()>0&&area.top().first>j){//          \/    \        area            \    ，
            //      
                a+=area.top().second;area.pop();
            }
            area.push(make_pair(j,a));//    push  
        }
    }
    vector<int>ans;
    while(!area.empty()){
        ans.push_back(area.top().second);
        area.pop();
    }
    reverse(ans.begin(),ans.end());
    cout<<sum<<"
"<<ans.size();
    for(auto i:ans){
        cout<<" "<<i;
    }
    cout<<"
";
}

제5 장 검색
5.2 선형 검색
ALDS1_4_A:Linear Search

#include
using namespace std;
const int maxn=1e4+10;
int main()
{
    int n,q,S[maxn],key;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&S[i]);
    sort(S,S+n);
    scanf("%d",&q);
    int cnt=0;
    for(int i=0;i<q;i++) {
        scanf("%d",&key);
        if(*lower_bound(S,S+n,key)==key) cnt++;
    }
    printf("%d
",cnt);
}

5.3 2 점 검색
ALDS1_4_B Binary Search

#include
using namespace std;
vector<int>S;
int bisearch(int n,int a){
    int left=0,right=n;
    while(left<right){
        int mid=left+(right-left)/2;
        if(a==S[mid]) return 1;
        else if(a<S[mid]) right=mid;
        else left=mid+1;
    }
    return 0;
}
int main()
{
    int n,a,q,cnt=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a);
        S.push_back(a);
    }
    scanf("%d",&q);
    for(int i=0;i<q;i++){
        scanf("%d",&a);
        cnt+=bisearch(n,a);
    }
    printf("%d
",cnt);
}

5.4 산열 법 해시 표 의 실현
ALDS1_4_C:Dictionary
제6 장 재 귀 와 분 치 법
6.2 빈 거 수색
ALDS1_5_A:Exhaustive Search

#include
using namespace std;
const int maxn=20+5;
int n,num,arr[maxn],q,vis[400010];
void dfs(int cur,int sum){// vis     arr                 
    if(cur==n) return ;
    vis[sum]=1;
    dfs(cur+1,sum+arr[cur+1]);
    dfs(cur+1,sum);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    cin>>q;
    dfs(-1,0);
    while(q--){
        cin>>num;
        if(vis[num]) cout<<"yes
";
        else cout<<"no
";
    }
}
#include
using namespace std;
const int maxn=20+5;
int n,arr[maxn],q,num;
bool solve(int idx,int m){//   arr     idx       m
    if(m==0) return true;
    if(idx==n) return false;//   if     ，    
    return solve(idx+1,m)||solve(idx+1,m-arr[idx]);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    cin>>q;
    while(q--){
        cin>>num;
        if(solve(0,num)) cout<<"yes
";
        else cout<<"no
";
    }
}

제7 장 고등 정렬
7.1 병합 정렬
ALDS1_5_B:Merge Sort

#include
using namespace std;
#define LL long long
#define INF INT_MAX
const int maxn=5e5+10;
int L[maxn/2+2],R[maxn/2+2];
int cnt;
void merge(int A[],int n,int left,int mid,int right){
    int n1=mid-left;
    int n2=right-mid;
    for(int i=0;i<n1;i++) L[i]=A[left+i];
    for(int i=0;i<n2;i++) R[i]=A[mid+i];
    L[n1]=R[n2]=INF;
    int i=0,j=0;
    for(int k=left;k<right;k++){
        cnt++;//      
        if(L[i]<=R[j]) A[k]=L[i++];
        else A[k]=R[j++];
    }
}
void mergeSort(int A[],int n,int left,int right){
    if(left+1<right){
        int mid=(left+right)/2;
        mergeSort(A,n,left,mid);
        mergeSort(A,n,mid,right);
        merge(A,n,left,mid,right);
    }
 
}
int main()
{
    int A[maxn],n;
    cnt=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    mergeSort(A,n,0,n);
    for(int i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<A[i];
    }cout<<endl;
    cout<<cnt<<endl;
}

제8 장 나무
8.2 뿌리 나무 표현
ALDS1_7_A: Rooted Trees 는 왼쪽 오른쪽 형제 표현 법 (left - child right - sibling representation) 으로 나 무 를 표시 합 니 다.

#include
using namespace std;
#define NIL -1
const int MAX=1e5+10;
struct Node{
    int p,l,r;//parent,left,right
    Node(int p=NIL,int l=NIL,int r=NIL){
        this->p=p;this->l=l;this->r=r;
    }
}T[MAX];
int n,D[MAX];//D   ，O(n)   
void rec(int cur,int dep){
    D[cur]=dep;
    if(T[cur].l!=NIL) rec(T[cur].l,dep+1);
    if(T[cur].r!=NIL) rec(T[cur].r,dep);
}
void print(int cur){
    cout<<"node "<<cur<<": parent = "<<T[cur].p<<", "<<"depth = "<<D[cur]<<", ";
    if(T[cur].p==NIL) cout<<"root, [";
    else if(T[cur].l==NIL) cout<<"leaf, [";
    else cout<<"internal node, [";
    for(int i=0,c=T[cur].l;c!=NIL;c=T[c].r,i++){
        if(i) cout<<", ";
        cout<<c;
    }
    cout<<"]
";
}
int main()
{
    int id,k,v;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>id>>k;
        int rr;
        for(int j=0;j<k;j++){
            cin>>v;
            if(j==0) T[id].l=v;
            else T[rr].r=v;
            rr=v;
            T[v].p=id;
        }
    }
    int root;
    for(int i=0;i<n;i++) if(T[i].p==NIL) {root=i;break;}//    
    rec(root,0);
    for(int i=0;i<n;i++) print(i);
}

8.3 이 진 트 리 의 표현
ALDS1_7_B:Binary Trees

#include
#define NIL -1
using namespace std;
const int MAX=30;
int n,D[MAX],H[MAX];
struct Node{
    int p,l,r;//parent,left,right
    Node(int p=NIL){this->p=p;}
}T[MAX];
void setDepth(int cur,int dep){
    D[cur]=dep;
    if(T[cur].l!=NIL) setDepth(T[cur].l,dep+1);
    if(T[cur].r!=NIL) setDepth(T[cur].r,dep+1);
}
int setHeight(int cur){
    int hl=0,hr=0;
    if(T[cur].l!=NIL) hl=setHeight(T[cur].l)+1;
    if(T[cur].r!=NIL) hr=setHeight(T[cur].r)+1;
    return H[cur]=max(hl,hr);
}
int getSibling(int cur){
    if(T[cur].p==NIL) return NIL;
    if(T[T[cur].p].l!=cur&&T[T[cur].p].l!=NIL) return T[T[cur].p].l;
    if(T[T[cur].p].r!=cur&&T[T[cur].p].r!=NIL) return T[T[cur].p].r;
    return NIL;
}
int getDegree(int cur){
    int deg=0;
    if(T[cur].l!=NIL) deg++;
    if(T[cur].r!=NIL) deg++;
    return deg;
}
void print(int cur){
    cout<<"node "<<cur<<": parent = "<<T[cur].p<<", sibling = "<<getSibling(cur)<<", degree = ";
    cout<<getDegree(cur)<<", depth = "<<D[cur]<<", height = "<<H[cur]<<", ";
    if(T[cur].p==NIL) cout<<"root
";
    else if(T[cur].l==NIL&&T[cur].r==NIL) cout<<"leaf
";
    else cout<<"internal node
";
}
int main()
{
    int id,left,right;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>id>>left>>right;
        T[id].l=left;
        T[id].r=right;
        if(left!=NIL) T[left].p=id;//    ，      
        if(right!=NIL) T[right].p=id;
    }
    int root;
    for(int i=0;i<n;i++) if(T[i].p==NIL){root=i;break;}
    setDepth(root,0);
    setHeight(root);
    for(int i=0;i<n;i++) print(i);
}

8.4 나무의 옮 겨 다 니 기
ALDS1_7_C:Tree Walk

#include
#define NIL -1
using namespace std;
const int maxn=30;
struct Node{
    int p,l,r;
    Node(int p=NIL){this->p=p;}
}T[maxn];
void Preorder(int cur){
    if(cur==NIL) return ;
    cout<<" "<<cur;
    Preorder(T[cur].l);
    Preorder(T[cur].r);
}
void Inorder(int cur){
    if(cur==NIL) return ;
    Inorder(T[cur].l);
    cout<<" "<<cur;
    Inorder(T[cur].r);
}
void Postorder(int cur){
    if(cur==NIL) return ;
    Postorder(T[cur].l);
    Postorder(T[cur].r);
    cout<<" "<<cur;
}
int main()
{
    int n,id,ll,rr;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>id>>ll>>rr;
        T[id].l=ll;
        T[id].r=rr;
        if(ll!=NIL) T[ll].p=id;
        if(rr!=NIL) T[rr].p=id;
    }
    int root;
    for(int i=0;i<n;i++) if(T[i].p==NIL) {root=i;break;}
    cout<<"Preorder
";
    Preorder(root);
    cout<<"
Inorder
";
    Inorder(root);
    cout<<"
Postorder
";
    Postorder(root);
    cout<<"
";
}

제1 1 장 동적 기획 법
피 보 나치 수열
ALDS1_10_A:Fibonacci Number

제1 2 장 그림
12.4 범위 우선 검색
ALDS1_11_C:Breadth First Search

#include
using namespace std;
const int maxn=100+10;
int n,G[maxn][maxn],dis[maxn],vis[maxn];
void bfs(){
    memset(dis,0,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int>que;
    que.push(1);vis[1]=1;dis[1]=0;
    while(!que.empty()){
        int cur=que.front();que.pop();
        for(int i=1;i<=n;i++){
            if(G[cur][i]&&!vis[i]){
                que.push(i);
                dis[i]=dis[cur]+1;
                vis[i]=1;
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        int u,k;cin>>u>>k;
        for(int j=0;j<k;j++){
            int v;cin>>v;
            G[u][v]=1;
        }
    }
    bfs();
    for(int i=1;i<=n;i++) if(!vis[i]) dis[i]=-1;// bfs          1       -1
    for(int i=1;i<=n;i++) cout<<i<<" "<<dis[i]<<"
";
}
//     
#include
using namespace std;
const int maxn=100+10;
int n,dis[maxn],vis[maxn];
vector<int>G[maxn];
void bfs(){
    memset(dis,0,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int>que;
    que.push(1);vis[1]=1;dis[1]=0;
    while(!que.empty()){
        int cur=que.front();que.pop();
        for(auto i:G[cur]){
            if(!vis[i]){
                que.push(i);
                dis[i]=dis[cur]+1;
                vis[i]=1;
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        int u,k;cin>>u>>k;
        for(int j=0;j<k;j++){
            int v;cin>>v;
            G[u].push_back(v);
        }
    }
    bfs();
    for(int i=1;i<=n;i++) if(!vis[i]) dis[i]=-1;// bfs          1       -1
    for(int i=1;i<=n;i++) cout<<i<<" "<<dis[i]<<"
";
}

제1 7 장 동적 기획 법
17.3 최 장 증가 서브 시퀀스
DPL_1_D:Longest Increasing Subsequence
lower_bound (arr, arr + n, x) 는 arr 배열 (정렬 됨) 에서 x 와 같은 수의 첫 번 째 위치 지침 을 찾 습 니 다.

#include
using namespace std;
const int maxn=1e5+10;
int arr[maxn],n,L[maxn];
const int inf=0x3f3f3f3f;
int main()
{
    memset(L,inf,sizeof L);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        *lower_bound(L,L+n,arr[i])=arr[i];
    }
    cout<<lower_bound(L,L+n,inf)-L<<"
";
}