- 3일차 배열 (성질, 기능)

해당 포스터는 파킹독님의 유튜브를 보고 작성되는 점 참고해주세요.

https://www.youtube.com/watch?v=mBeyFsHqzHg 

 

배열이란?

---

배열 : 메모리 상에 원솔르 연속하게 배치한 자료구조 (이 점 때문에 본인의 vector 구현이 realloc해서 인덱스 접근이 가능한 점!)

 

배열의 성질

1. 메모리 상에서 연속하기에 O(1)로 k번째 원소를 확인 / 변경 가능하다.
2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없다 (운영체제에서 나오는 것, 참조의 지역성때문, cache hit rate가 높음)
3. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸린다.

배열의 기능

1. 임의의 위치에 원소를 추가, O(n)
2. 임의의 위치에 원소를 삭제, O(n)

 

사실 C를 사용하는 것이 아니라면 C++ STL에 잘 구현돼있는 vector를 이용하면 좋지만, 필자는 c언어로 문제를 풀기에 vector를 따로 구현해서 문제를 풀려고 한다.

c언어로 구현한 vector가 궁금하다면 (https://i-m-possible.tistory.com/14) 여기로 들어가면 된다.

 

---

 

문제 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x03.md

GitHub - encrypted-def/basic-algo-lecture: 바킹독의 실전 알고리즘 강의 자료

 

문제풀이

---

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

10808번: 알파벳 개수

C언어 정답코드

배열의 인덱스를 알파벳이라고 생각을 하고 갯수를 세주면 된다.

#include <stdio.h>
int a[26];
char b[101];
main(){scanf("%s",b);
    for(int i=0;b[i];i++)a[b[i]-'a']++;
    for(int i=0;i<26;i++)printf("%d ",a[i]);
}

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

2577번: 숫자의 개수

C언어 정답코드

b에다가 모든 수를 곱해놓고 10씩 나누는데, a의 배열이 0~9라는 숫자라고 생각하고 숫자를 세준다.

#include <stdio.h>
int a[10],b,c,d;
main(){scanf("%d %d %d",&b,&c,&d);
    for(b*=c*d;b;b/=10)a[b%10]++;
    for(int i=0;i<10;i++)printf("%d\n",a[i]);
}

 

 

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

1475번: 방 번호

C언어 정답코드

6번과 9번은 바꿔서 쓸 수가 있다. 그렇기에 6번과 9번일 때는 배열에 들어있는 값에 따라서 바꿔서 넣어주면 된다.

 

그럼 여기서 갯수를 어떻게 알면 되냐면 따로 최대 갯수를 갖고만 있으면 된다.

 

어차피 1이라는 아이가 3번 필요하면 세트가 3개 필요하기 때문이다.

#include <stdio.h>
#define max(a,b)(a>b?a:b)
int n,a[10],c;
main(){scanf("%d",&n);
    while(n){int v=n%10;
        if(v==6 || v==9){
            if(a[6] > a[9])v=9;
            else v=6;
        }
        ++a[v];
        c=max(c,a[v]);
        n/=10;
    }
    printf("%d",c);
}

 

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

3273번: 두 수의 합

C언어 정답코드

O(n)의 풀이이다.

b라는 배열은 arr에서 이미 들어온 숫자들을 저장하는 배열이다.

 

저장을 해놓고 arr를 돌면서 만약 arr의 i번째 값과 합쳐서 x를 만들 수 있는 값이 이미 나온 적이 있어서 b배열에 있다면

그 갯수만큼 더해주면 된다.

#include <stdio.h>
#define size 1000000+2
int n,arr[size],b[size],x,cnt;
main(){scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&arr[i]);
    scanf("%d",&x);
    for(int i=0;i<n;i++){
        if(x-arr[i]>0 && b[x-arr[i]])cnt+=b[x-arr[i]];
        b[arr[i]]++;
    }
    printf("%d",cnt);
}

 

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

10807번: 개수 세기

C언어 정답코드

t가 -100부터 100까지 들어올 수 있기 때문에 갯수를 세줄 때 100을 더해줘서 0~201이라고 생각하고 저장하면 된다.

#include <stdio.h>
int n,arr[300],t;
main(){scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&t),arr[t+100]++;
    scanf("%d",&t);printf("%d",arr[t+100]);
}

python 정답코드

파일 입출력을 통해 b에 리스트 형태로 값을 저장하고

b에 저장된 e를 세주기만 하면된다.

a,*b,e=open(0)
print(b[0].split().count(e.strip()))

 

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

13300번: 방 배정

C언어 정답코드

방이 배정될 때 k명이 되고 한 명 더 들어오면 방을 증가해주고, 또한 새로운 방에  한 명이 들어갈 때도 방을 증가시키면 된다.

#include <stdio.h>
int n,k,a[7][2],c;
main(){scanf("%d %d",&n,&k);
    for(int i=0,s,y;i<n;i++){
        scanf("%d %d",&s,&y);
        if(a[y][s]==k)c++,a[y][s]=1;
        else {
            if(!a[y][s])c++;
            a[y][s]++;
        }
    }
    printf("%d",c);
}

 

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

11328번: Strfry

C언어 정답코드

string 헤더파일에 있는 strcpy를 통해서 문자열을 손쉽게 복사할 수 있었다.

일단 a,b문자열을 받고 c라는 배열에 몽땅 저장하는데, a는 더하고 b에 있는 알파벳은 뺀다.

 

그런 뒤에 c배열을 돌면서 알파벳이 음수, 양수라면 다른 알파벳이 있으니 절대로 둘이 같게 만들 수 없으므로 impossible을 복사해서 출력해준다.

#include <string.h>
int n;
char a[1002],b[1002],result[11];
main(){scanf("%d",&n);
    while(n--){
        int c[26]={};strcpy(result,"Possible");
        scanf("%s %s",a,b);
        for(int i=0;a[i];i++)c[a[i]-'a']++;
        for(int i=0;b[i];i++)c[b[i]-'a']--;
        for(int i=0;i<26;i++){
            if(c[i]){
                strcpy(result,"Impossible");
                break;
            }
        }
        printf("%s\n",result);
    }
}

 

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

1919번: 애너그램 만들기

 

C언어 정답코드

알파벳 세기와 비슷하게 a는 세주고 b는 없앤다.

그리고 음수든 양수든 있다는 것은 없애야 에너그램을 만들 수 있는 것이므로 갯수를 세주면 된다.

#define abs(a)(a>0?a:-a)
/*
 https://www.acmicpc.net/problem/1919
 1919번 에너그램 만들기
*/
char a[1001],b[1001];
int c[26],cnt;
main(){
    scanf("%s %s",a,b);
    for(int i=0;a[i];i++)c[a[i]-'a']++;
    for(int i=0;b[i];i++)c[b[i]-'a']--;
    for(int i=0;i<26;i++)cnt+=abs(c[i]);
    printf("%d",cnt);
}