03 배열

 

1. 알게된 개념

(1) 배열에서 시간 복잡도

임의의 위치에 있는 원소를 확인/변경==O(1)

원소를 끝에 추가==O(1)

마지막 원소를 제거==O(N)

 

2. 추가 제거 함수 구현

(1) insert 함수

void insert(int idx, int num, int arr[], int& len){
  for(int i = len; i > idx; i--)
    arr[i] = arr[i-1];
  arr[idx] = num;
  len++;
}

길이가 len인 배열이다. inx 인덱스에 num을 추가하는 함수이며 +1 된 마지막 index인 len index부터 idx전까지 요소들을 한칸씩 뒤로 땡겨온다.

그 후, arr[idx]에 num을 저장한다.

len++로 배열의 길이를 증가시킨다.

 

(2) erase 함수

void erase(int idx, int arr[], int& len){
  len--;
  for(int i = idx; i < len; i++)
    arr[i] = arr[i+1];
}

우선 len--로 길이를 줄인다.

오른쪽에 있는 요소를 한칸 왼쪽으로 땡겨온다.

arr[idx]에 arr[idx+1]을 저장하는것부터 시작해서 i<len까지 반복한다.

 

3.관련 백준문제

(1)10808 알파벳 개수

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

#include <bits/stdc++.h>
using namespace std;

int freq[26];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  string s;
  cin >> s;
  for(auto c : s)
    freq[c-'a']++;
  for(int i = 0; i < 26; i++)
    cout << freq[i] << ' ';
}

출처:바킹독

 

int freq[26] 을 전역변수로 배열을 선언해놓고

for문 안에서 아스키코드를 활용하여 freq[c-'a']++로 구현한 것을 주목해볼만 하다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

출처: 바킹독

https://github.com/encrypted-def/basic-algo-lecture/tree/master/0x03

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