[Algorithm] 배열

배열(Array)

 

- 정의: 메모리 상에 원소를 연속하게 배치한 자료구조.

 

- 특징

 

    (1) 다른 자료구조와 달리 원소를 저장하는 것 이외에 추가적으로 소모되는 메모리의 양(=오버헤드)이 거의 없는 것이 장점

 

    (2) 메모리 상에 원소가 연속해서 있어야 한다는 성질로 인해 cache hit rate(https://parksb.github.io/article/29.html)가 높다는 장점이 있으나 할당에 제약이 걸린다는 단점도 있음

 

    (3) 배열의 길이: 따로 변수를 하나 두어 배열의 길이 저장. 따라서 배열의 길이를 알고 있다고 가정

 

 

- 시간 복잡도

 

    (1) 임의의 위치에 있는 원소를 확인/변경: 원소는 연속하므로 O(1)

 

    (2) 원소를 끝에 추가: 배열의 길이를 알고 있으니 마지막 위치에 원소를 두기만 하면 되므로 O(1)

 

    (3) 마지막 원소를 제거: 배열의 길이를 알고 있으니 O(1)

 

    (4) 임의의 위치에 원소를 추가: 그 뒤의 원소들을 전부 한 칸씩 밀어야 하므로 평균적으로 N/2이다. 따라서 O(N)

 

    (5) 임의의 위치에 원소를 제거: 그 뒤의 원소들을 전부 한 칸씩 앞으로 밀어야 함으로 O(N)

 

 

- 배열 전체를 특정 값으로 초기화 시켜주고 싶을 때

 

    (1) memset 함수

 

#include <string.h>

void* memset( void* ptr, int value, size_t num);

• ptr: 채우고자 하는 메모리의 시작 포인터(시작 주소)
• value: 메모리에 채우고자 하는 값. int 형이지만 내부에서는 unsigned char(1 byte)로 변환되어 저장
• num: 채우고자 하는 바이트의 수. 즉, 채우고자 하는 메모리의 크기

    EX)

memset(a, 65, sizeof(a)); 

 

 

    (2) for 문

 

int a[20][20];

for(int i=0;i<20;i++){
	for(int j=0;j<20;j++){
    	a[i][j]=0;
    }
}

 

 

    (3) fill 함수

 

#include <algorithm>

void fill (ForwardIterator first, ForwardIterator last, const T& val);

• first : 채우고자 하는 자료구조의 시작위치 iterator
• last : 채우고자 하는 자료구조의 끝위치 iterator이며 last는 포함하지 않는다!
• val : first부터 last전까지 채우고자 하는 값으로 어떤 객체나 자료형을 넘겨줘도 템플릿 T에 의해서 가능

    EX)

int a[20][30];

for(int i=0;i<20;i++)
	fill(a[i],a[i]+30,0);

-장점: 인덱스에 해당하는 원소에 빠르게 접근 가능, 데이터를 자주 바꾸지 않고 쌓아둘때

 

-단점: 데이터의 삭제/삽입이 빈번하면 비효율

 

 

 

문제

 

백준 10808번 알파벳 개수 https://www.acmicpc.net/problem/10808

 

 

내 코드

 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(void) {
	string arr;
	int tmp[26];

	getline(cin, arr);

	for (int i = 0; i < 26; i++) tmp[i] = 0;
	for (int i = 0; i < arr.size(); i++) tmp[int(arr[i]) - 97]++;
	for (int i = 0; i < 26; i++) cout << tmp[i] << " ";
	
    return 0;
}

-string을 입력 받을 때 getline(cin, 배열명); 사용

 

-string의 길이는 arr.size(), 배열의 길이는 sizeof(tmp)/sizeof(자료형);

 

-memset함수를 사용하면 런타임 에러나 날 수 있음.

 

-배열 선언시 int arr[20]={}; 라고 하면 0으로 초기화 됨.

 

 

 

 

 

 

참고

 

https://blog.encrypted.gg/725?category=773649

https://twpower.github.io/121-usage-of-fill-function

https://twpower.github.io/79-usage-of-memset-function

https://simsimjae.tistory.com/39