본문 바로가기
Research/Data structure & algorithm

Data Structure: Arrays

by RIEM 2022. 11. 24.
728x90

065. Arrays Introduction

What Is Arrays?

Arrays organize data sequentially. Array는 한 마디로 정보들을 나란히 정렬시킨 형태의 데이터 구조다. 

Pros and Cons?

Pros

  • Fast lookups
  • Fast push/pop
  • Ordered

Cons

  • Slow inserts
  • Slow deletes
  • Fixed size(if static array)

 

Big O in Arrays

  • lookup: O(1)
  • push: O(1)
  • insert: O(n)
  • delete: O(n)
 
const strings = ['a', 'b', 'c', 'd'];
// saving datas in sequential memory
// 4 * 4 = 16 bytes of storage

// O(1)
console.log(strings[2]) //"c"
// 1. go to array called 'strings'
// 2. and grab the third one in it

// push 
// - O(1)
// - go 'strings' array and add one in the last position
strings.push('e')
console.log(strings) // ["a", "b", "c", "d", "e"]

// pop
// - O(1)
strings.pop();
console.log(strings) // ["a", "b", "c", "d"]

// unshift
// - O(n) : because of loop to re-assign 
strings.unshift('x')
console.log(strings) // ["x", "a", "b", "c", "d"]

// both push ans unshift is adding element. But push is more economic

// splice
// 1. go to index
// 2. add something
// 3. shift the rest one forward

strings.splice(2, 0, 'alien') // O(n/2) - half of operation -> O(n) simplified
console.log(strings) // ["x", "a", "alien", "b", "c", "d"]

Array와 BigO

Array를 다루는 메소드에 따라 BigO가 어떻게 달라지는지 알아보자.

strings[2]

  • strings라는 어레이로 가서, 3번째(2번 인덱스)의 데이터를 가져와줘
  • 그 주소에 가서 데이터를 가지고 오는 것이기 때문에 constant time
  • O(1)

push, pop

  • strings라는 어레이로 가서, 마지막 순서에 데이터 하나를 추가하거나(push) 마지막 데이터를 없애줘(pop)
  • 이미 있던 데이터들과는 무관하게 하나의 방만 더 추가하는 것이므로 달라질 것 없다
  • O(1)

unshift

  • strings라는 어레이의 가장 앞에 데이터 하나를 추가하고, 기존에 있던 데이터들은 한칸씩 뒤로 옮겨줘. 0번->1번, 1번 ->2번, …, n번 -> n+1번(iterate)
  • 반복문을 써야하므로
  • O(n)

splice(2, 0, ‘alien’)

  • strings 어레이의 2번 인덱스부터, 0개의 인덱스를 지우고(그냥 두고), ‘hello’를 삽입해줘
  • [‘x’, ‘a’, ‘alien’, ‘b’, ‘c’, ‘d’]에서 ‘alien’이 전체 어레이의 중간즈음에 위치하고, 그 뒤 나머지 데이터들을 루프로 한칸씩 뒤로 옮기기
  • O(n/2) -> O(n) simplified one

 

066. Static vs. Dynamic Arrays

Difference?

  • Static arrays: you need to specify the number of items before
  • Dynamic arrays: enable to copy and rebuild the array in new location with more memory. 

In code

in C,

int a[20]; 

int b[5] {1, 2, 3, 4, 5}

저수준의 언어인 C의 경우 메모리를 지정해주는 정적 배열인 것과 달리, 파이썬의 경우 메모리를 지정해주지 않아도 늘어나는 동적 배열이다. 언어마다 다른 유형의 배열을 가지고 있다. 그래서 메모리를 제대로 관리를 하고 싶은 경우 JS, Python보다 C를 사용한다.

Dynamic Arrays

BigO

  • lookup: O(1)
  • append: O(1) or O(n)
  • insert: O(n)
  • delete: O(n)
// fixed 4 items array
const strings = ['a', 'b', 'c', 'd'];
const strings2 = ['a', 'b', 'c', 'd', ‘e’, _ , _ , _];

// Dynamic arrays
// 1. 'loop' strings
// 2. copy it and paste to new location

strings[2] // O(1)

// push
strings.push('e'); // O(n) -> loop

// pop
strings.push(); //O(1)

// unshift
strings.unshift('x') // O(n)
  • static array로 공간이 부족한 경우, static array를 복제하여 새로운 공간에 dynamic array를 만든다. 
  • 복제 시, static array의 아이템들을 루프로 하나하나 확인한다. 따라서 만약 push(append)를 했는데 공간이 부족하여 dynamic array를 만들게 된다면 루프가 실행되므로 O(1)이 아니라 O(n)이 된다.

 

 

069. Implementing An Array

Data Structure

  1. How to Build One
  2. How to Use it

 

Let’s build the array ourselves. Arrays in JS are object with integer-based keys

// 069. Implementing An Array

// Arrays in JS are object with integer-based keys

class MyArray {
	constructor() {
		this.length = 0;
		this.data = {};
	}
	
	// 	access data
	get(index) {
		return this.data[index]
	}
	
	push(item) {
		this.data[this.length] = item
		this.length++
		return this.length
	}
	
	pop() {
		const lastItem = this.data[this.length - 1];
		delete this.data[this.length - 1];
		this.length--;
		return lastItem;
	}
	
	delete(index) {
		const item = this.data[index];
		// How can we delete and shift the rest elements?
		// -> Let's create the function for it
		this.shiftItems(index)
		return item;
	}
	
	shiftItems(index) {
		for (let i = index; i < this.length; i++) {
			this.data[i] = this.data[i+1]; // 뒤에 있는 것을 앞으로
		}
		delete this.data[this.length-1];
		this.length--;
	}
}

const newArray = new MyArray();
newArray.push('hi');
newArray.push('you');
console.log(newArray);
// [object Object] { data: [object Object] {0: "hi", 1: "you"}, length: 2 }

newArray.push('a');
newArray.push('b');
newArray.pop();
console.log(newArray);
// [object Object] {data: [object Object] {0: "hi",1: "you",2: "a"},length:3}

newArray.delete(1); 
console.log(newArray)
// Without deleting the last item 'undefined' in shiftItems()
// console.log(newArray)[object Object] {data: [object Object] {0: "hi", 1: "a", 2: undefined }, length: 2}

// With deleting the last item 'undefined' in shiftItems()
// [object Object] { data: [object Object] { 0: "hi", 1: "a" }, length: 2}
 

우선 어레이의 기본 프로퍼티가 length이고 데이터는 키:벨류 페어로 구성되어있다는 점이 재밌다. key:value 페어 즉, 객체 형태이다. 이를 통해 왜 어레이가 객체 타입인지 알 수 있다. 

그리고 클래스 하단에 메소드들이 있는데 get, push, pop, delete, shiftItems가 있다. shiftItems는 delete에서 사용되는데, 특정 index를 찾은 뒤 나머지를 앞으로 당겨주는(shift) 역할을 수행한다. 흥미로운 점은 1)shiftItems 메소드에서 당겨줄 때 현재 아이템에 다음 인덱스의 아이템을 assign해주는 방식이 신선했고, 2) 앞으로 당겨지고 남은 item의 공간이 undefined 상태로 남는 점이다. 남는 item 공간은 객체의 프로퍼티를 삭제하는 delete operator로 제거했다. 객체의 operator인 delete와 우리가 만든 delete 메소드 명이 같아서 햇갈린다.

어레이 객체를 직접 클래스로 구현하는 것을 경험해보니, 어레이를 좀 더 깊은 수준에서 이해할 수 있었던 것 같다. 그리고 나만의 데이터 구조를 커스터마이징 해서 쓸 수도 있다는 점에서 재미있는 작업으로 느껴졌다.

 

070. Strings and Arrays

string question? convert into array with split(). and then return it to string.

 

071, 72. Solution: Reverse A String

reverse1의 방식이 길지만 input의 type을 체크하는 코드를 넣은 점이 좋다고 생각한다. 최근 프로그래머스의 문제를 풀다보면 input 타입과 확장성을 고려하지 않아서 에러가 발생하는 경우가 많았는데, 이와 같이 input의 다양성으로 인해 발생할 에러들을 사전에 고려해서 코드를 짜는 것이 중요한 덕목이라는 생각이 든다.

function reverse(str) {
	let t0 = performance.now();
	let answer = '';
	for(let i = str.length -1; i >= 0; i--) {
		answer += str[i]
	}
	let t1 = performance.now();
	console.log(`Performance 00: ${(t1 - t0).toFixed(20)}`)
	return answer;
}


function reverse1(str) {
	let t0 = performance.now();

  if(!str || typeof str != 'string' || str.length < 2 ) return str;
	
	const backwards = [];
	const totalItems = str.length - 1;
	for (let i = totalItems; i >= 0; i--) {
		backwards.push(str[i]);
	}
	let t1 = performance.now();
	console.log(`Performance 01: ${(t1 - t0).toFixed(20)}`)
	return backwards.join('');	
}


function reverse2(str) {
	return str.split('').reverse().join('')
}

// Using method
const reverse3 = str => str.split('').reverse().join('');

// More modern way
const reverse4 = str => [...str].reverse().join('');


console.log(reverse('hello'))
console.log(reverse1('hello'))
console.log(reverse2('hello'))
console.log(reverse3('hello'))
console.log(reverse4('hello'))
 

073, 74. Merge Sorted Array

function mergeSortedArrays(array1, array2){
  const mergedArray = [];
  let array1Item = array1[0];
  let array2Item = array2[0];
  let i = 1;
  let j = 1;
  
  //We should actually move these 2 if statements to line 2 so that we do the checks before we do assignments in line 3 and 4!
  if(array1.length === 0) {
    return array2;
  }
  if(array2.length === 0) {
    return array1;
  }

  while (array1Item || array2Item){
   if(array2Item === undefined || array1Item < array2Item){
     mergedArray.push(array1Item);
     array1Item = array1[i];
     i++;
   }   
   else {
     mergedArray.push(array2Item);
     array2Item = array2[j];
     j++;
   }
  }
  return mergedArray;
}

mergeSortedArrays([0,3,4,31], [3,4,6,30]);
 

75. Interview Question

Nice exercises to practice interview questions related to Arrays. 

Good to learn regex

 

728x90
저작자표시

'Research > Data structure & algorithm' 카테고리의 다른 글

s10. Data Structure: Trees  (0) 2022.11.29
Data Structure: Stacks + Queues  (0) 2022.11.28
Data Structure: Hash Tables  (0) 2022.11.25
Data Structure: Introduction  (0) 2022.11.24
Big O의 개념, 유형, 계산 원칙 그리고 의미  (0) 2022.11.23

관련글

댓글

티스토리툴바