Data Structures & Algorithms with Javascript : Arrays

2024.07.17 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript

Data Structures & Algorithms with Javascript : Intro

컴퓨터 프로그래밍에서 가장 익숙한 자료구조라면 "Array"라고 할 수 있다.
모든 프로그래밍 언어는 어떤 형태로든 array를 내장하고 있다.
Array가 built-in이기 때문에 효율적이고 데이터 저장 목적에 좋은 선택으로 여겨진다.

🍀 오늘은 자바스크립트에서 array를 자바스크립트에서 어떻게 어떤 경우들에 사용할 지에 대해 알아보자.

 

Array 사용

자바스크립트 Array를 사용해 봤다면 엄청 유연하다는 걸 느꼈을 것이다.

Array를 생성, 요소를 찾거나 sort 하는 방법에는 여러 가지가 있다. 이 방법들에 대해 하나씩 알아보자.

 

Array 생성

// 가장 간단하게 array 선언하는 방법은 '[ ]' 연산자를 활용하는 것이다.
const emptyArray = [];

// 자바스크립트 array에 내장된 length 프로퍼티를 호출해서 길이가 0 인 배열이라는 걸 알 수 있다.
console.log(emptyArray.length);

// 배열에 요소를 넣어 배열을 선언할 수 있다.
const numbers = [1, 2, 3, 4, 5];
console.log(numbers.length); // 5

// Array constructor와 new 키워드로 호출하여 array를 생성할 수 있다.

// 숫자 1개를 매개변수로 전달하면 해당 숫자만큼의 빈 배열을 생성한다.
// 이때 empty는 비어 있다는 것이고, 실제 empty라는 값이 들어가 있는 건 아니다.
const empty10Arr = new Array(10);
console.log(empty10Arr); // [empty × 10]


// 2개 이상의 숫자를 전달할 경우에는 해당 숫자들을 원소로 하는 배열을 생성한다.
const numbers3 = new Array(1, 2, 3, 4, 5);
console.log(numbers3.length); // 5

// (스크립트 언어들 제외) 다른 프로그래밍 언어와는 달리 자바스크립트 array의 요소들은 다른 타입을 가질 수 있다.
const diffTypeArr = new Array(1, "Joe", true, null);

 

다음과 같이 Array.isArray()에 매개변수로 넘겨 확인할 수 있다.

const arr = [1,2,3];
const obj = {"0":1,"1":2,"2":3};
Array.isArray(arr); // true
Array.isArray(obj); // false

 

Array constructor를 호출하는 것보다는 [ ] 연산자를 활용하는 것이 가장 효율적이라고 한다.

Array 요소 삽입과 접근

// [배열의 인덱스] = 배열 인덱스에 할당할 값 형태로 [] 연산자를 활용해 값을 할당할 수 있다.
const nums = [];
for(let i = 0; i < 100; i++){
	nums[i] = i+1;
}

// 마찬가지로 배열의 인덱스로 요소에 접근 가능하다
const nums2 = [1,2,3,5,8,13,21];
let sum = 0;
for(let i = 0; i < numbers.length; i++){
	sum += nums2[i];
}

console.log(sum); //53

String으로부터 배열 생성

string을 잘라줄 기준 문자열을 split()의 매개변수로 전달하여 배열을 생성할 수 있다.

const sentence = "the quick brown fox jumped over the lazy dog"; 
const words = sentence.split(" ");
for (let i = 0; i < words.length; ++i) {
       console.log("word " + i + ": " + words[i]);
    }
    /**
    word 0: the
    word 1: quick
    word 2: brown
    word 3: fox
    word 4: jumped
    word 5: over
    word 6: the
    word 7: lazy
    word 8: dog
    */

배열 합쳐주기

얕은 복사

// 얕은 복사 : 배열은 객체다. 객체는 주소를 참조하기 때문에
// 원본 배열을 다른 배열에 할당하면 복사본인 배열은 원본 배열의 주소를 참조하여 (서로 같은 걸 참조) 
// 복사본의 변경사항이 원본 배열에도 반영된다 (서로 변경 사항이 반영).
const nums = [];
for (var i = 0; i < 10; ++i) {
       nums[i] = i+1;
    }
const samenums = nums;

nums[0] = 400;
samenums[0];

 

깊은 복사

// 얕은 복사를 하면 값이 어디서 의도치 않게 변경될 수도 있다.
// 깊은 복사로 해당 문제를 해결할 수 있다.

// 복사 함수
function copy(arr1, arr2) {
for (let i = 0; i < arr1.length; ++i) {
          arr2[i] = arr1[i];
       }
}

// 사용
const nums = [];
for (let i = 0; i < 100; ++i) {
       nums[i] = i+1;
    }
const samenums = [];
copy(nums, samenums);
nums[0] = 400; 
console.log(samenums[0]); // 1

Array 접근 함수

앞에서 array의 인덱스를 [] 연산자로 접근할 수 있다는 걸 살펴봤다.

이 외에 array 요소에 접근하는 방법에는 접근자 함수를 활용하는 방법이 있는데, 접근자 함수들을 살펴보자.

 

indexOf() : array에 요소가 등장하지 않으면 -1, 등장하면 가장 마지막 등장 인덱스

const names = ["David", "Cynthia", "Raymond", "Clayton", "Jennifer"]; 

const present_name = 'Cynthia';
const non_present_name = 'Elsa';

function getPosition(name){
    const position = names.indexOf(name);
    if (position >= 0) {
    	console.log("Found " + name + " at position " + position);
    }
    else {
        console.log(name + " not found in array.");
    }
}

getPosition(present_name); // Found Cynthia at position 1
getPosition(non_present_name); // Elsa not found in array.

Array를 String 형태로

join() : 매개변수로 넘긴 문자열로 array 요소들을 합쳐준 string 생성, 매개변수를 넘기지 않다면 ', '로 합쳐준다.

toString() : ', '로 array 요소들을 합쳐준 string 생성

const names = ["David", "Cynthia", "Raymond", "Clayton", "Mike", "Jennifer"];
names.join(); // 'David,Cynthia,Raymond,Clayton,Mike,Jennifer'
names.toString(); // 'David,Cynthia,Raymond,Clayton,Mike,Jennifer'

Array들로부터 새로운 Array 생성

concat() : 두 개 이상의 array를 이어 붙일 수 있다. 배열. concat(이어 붙여줄 배열) 형태

const lowercase = ["a", "b", "c", "d", "e"];
const uppercase = ["A", "B", "C","D","E"];
const lower_upper = lowercase.concat(uppercase);
const upper_lower = uppercase.concat(uppercase);
console.log(lower_upper) // ['a', 'b', 'c', 'd', 'e', 'A', 'B', 'C', 'D', 'E']
console.log(upper_lower) // ['A', 'B', 'C', 'D', 'E', 'A', 'B', 'C', 'D', 'E']

 

splice() : 매개변수는 차례대로 시작 인덱스, 삭제해 줄 항목 개수, 추가해 줄 요소들 형태.

원본 array을 변경하기 때문에 만약에 변경없이 새로운 array를 만들고 싶다면 slice(시작인덱스, 끝 인덱스)를 활용하자.

 

const lowercase = ["a", "b", "c", "d", "e","f","g","h"];

// lowercase의 인덱스 3번부터 3개를 잘라서 배열을 생성
const spliced = lowercase.splice(3,3);

console.log(spliced); // ["d", "e","f"]
console.log(lowercase); // ["a", "b", "c", "g", "h"]

// 시작 인덱스 3에서부터 0개를 삭제하고 스프레드 문법(...)을 활용하여 spliced의 원소들을 삽입
lowercase.splice(3,0,...spliced); 
console.log(lowercase); // ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

Array mutator 함수

push() : array 끝에 요소 추가

const nums = [1, 2, 3, 4, 5];
console.log(nums); // 1, 2, 3, 4, 5
nums.push(6);
console.log(nums); // 1, 2, 3, 4, 5, 6

 

unshift() : array 앞에 요소 추가, 매개변수를 ','로 구분하여 여러 개 추가 가능

// 직접 배열의 요소를 하나씩 밀어주고 맨 앞에 요소 추가 
const nums = [2,3,4,5];
const newnum = 1;
const N = nums.length;
for (let i = N; i >= 0; --i) {
       nums[i] = nums[i-1];
    }
nums[0] = newnum;
console.log(nums); // [1, 2, 3, 4, 5]

// unshift를 통해 간단하게 앞에 요소를 추가할 수 있다

const newnum = 1; 

let nums = [2,3,4,5]; 
print(nums); // [2,3,4,5]

nums.unshift(newnum); 
console.log(nums); // [1,2,3,4,5] 

nums = [3,4,5]; 
nums.unshift(newnum,1,2); 
console.log(nums); // [1, 1, 2, 3, 4, 5]

Array 요소 제거

pop() : array 맨 끝 요소 제거

const nums = [1,2,3,4,5];
nums.pop(); // 5
console.log(nums); // [1,2,3,4]

 

shift() : array 맨 첫 요소 제거

const nums = [1,2,3,4,5];

// 직접 맨 앞에 요소 추가
const nums = [9,1,2,3,4,5];
console.log(nums); // [9,1,2,3,4,5]
for (let i = 0; i < nums.length; ++i) {
       nums[i] = nums[i+1];
    }
console.log(nums); //  [1, 2, 3, 4, 5, undefined] // 배열의 크기는 그대로라서 반쪽짜리 제거다

// shift() 함수를 활용해 맨 앞에 요소 추가
nums.shift(); // 9
console.log(nums); // [1,2,3,4,5]

Array 요소 순서대로 정렬

reverse() : 요소들을 내림차순(큰 값부터 작은 값 순)으로 정렬

const nums = [1,2,3,4,5]; 
nums.reverse(); 
console.log(nums); //  [5, 4, 3, 2, 1]

 

sort() : 사전적으로 요소들을 정렬

// sort() 함수는 요소들이 문자열이라고 가정하고 정렬한다.
// 즉 100은 숫자 100이 아니라 문자 "1","0","0"이 이어진 값이고, 2도 숫자가 아닌 문자 "2"이다.
// 따라서 숫자 순서 1,2,3,4,100,200 이 아니라 
// 문자 순서 "1", "100", "2" , "200", "3", "4"로 정렬한다.
const nums = [3, 1, 2 , 100, 4, 200]; 
nums.sort(); 
console.log(nums); // [1, 100, 2, 200, 3, 4]

// sort()함수에 매개변수로 비교 함수를 전달하여 숫자순으로 정렬하도록 할 수 있다.

function compare(num1, num2) { 
	return num1 - num2;
}
nums.sort(compare); 
console.log(nums); // [1, 2, 3, 4, 100, 200]

 

Iterator 함수

iterator함수는 배열 요소들을 순회하면서 연산을 하고 나서 새로운 배열을 생성하는 것과, 생성하지 않는 것이 있다.

먼저 새로운 배열을 생성하지 않는 iterator 함수를 살펴보자.

 

forEach() : 매개변수로 함수를 전달하면 해당 함수의 연산을 array의 각 요소에 적용

function square(num) { 
	console.log(num, num * num);
}
const nums = [1,2,3,4,5,6,7,8,9,10];
nums.forEach(square);

/**
    1 1 
    2 4 
    3 9
    4 16
    5 25
    6 36
    7 49
    8 64
    9 81 10 100
*/

 

every() : 매개변수로 전달한 boolean 함수를 array의 각 요소에 적용하고 모든 요소가 true인 경우 true를 리턴한다.

function isEven(num) { 
	return num % 2 == 0;
}
const num1 = [2,4,6,8,10];
const num2 = [2,4,6,7,8,10];
const allAreEven = (nums) => nums.every(isEven)? "all numbers are even":"not all numbers are even"; 

console.log(allAreEven(num1)); // all numbers are even
console.log(allAreEven(num2)); // not all numbers are even

 

some() : 매개변수로 전달한 boolean 함수를 array의 각 요소에 적용하고 하나라도 요소가 true인 경우 true를 리턴한다.

function isEven(num) { 
	return num % 2 == 0;
}
const num1 = [1,3,5,7,8,9];
const num2 = [1,3,5,7,9];
const someAreEven = (nums) => nums.some(isEven)? "some numbers are even":"all numbers are not even"; 

someAreEven(num2) // 'some numbers are even'
someAreEven(num2) // 'all numbers are not even'

 

reduce() : 매개변수로 전달한 함수의 연산 결과를 축적해서 하나의 결과를 리턴한다.

// reduce는 왼쪽에서 오른쪽으로 연산이 진행된다.
function add(accumulatedValue, currentValue) { 
	return accumulatedValue + currentValue;
}
const nums = [1,2,3,4,5,6,7,8,9,10]; 
const sum = nums.reduce(add); 
console.log(sum); // 55


// 반면 reduceRight()로 오른쪽에서 왼쪽으로 연산이 되도록 할 수 있다.
function concat(accumulatedString, item) { 
	return accumulatedString + item;
}
const words = ["the ", "quick ","brown ", "fox "]; 
const sentence = words.reduceRight(concat); 
console.log(sentence); // 'fox brown quick the '

 

이번에는 새로운 array를 리턴하는 함수들을 살펴보자.

 

map() : forEach() 함수처럼 array를 순회하면서 각 요소에 연산을 한다. forEach()와 달리 연산 결과를 담은 새로운 array 생성하여 리턴

function curve(grade) { 
	return grade += 5;
}
const grades = [77, 65, 81, 92, 83];
const newgrades = grades.map(curve); 
console.log(newgrades); // [82, 70, 86, 97, 88]

 

filter() : array를 순회하면서 각 요소에 매개변수로 전달받은 boolean 함수를 수행하여 true인 요소 값만 리턴하는 새로운 배열 생성

function isEven(num) { 
	return num % 2 == 0;
}
function isOdd(num) { 
	return num % 2 != 0;
}

const nums = [];
for (let i = 0; i < 20; ++i) {
       nums[i] = i+1;
    }

const evens = nums.filter(isEven); 
const odds = nums.filter(isOdd); 

console.log(`Even numbers: ${evens}`);  // 'Even numbers: 2,4,6,8,10,12,14,16,18,20'
console.log(`Odd numbers: ${odds}`); // 'Odd numbers: 1,3,5,7,9,11,13,15,17,19'

이차원/ 다차원 Array

자바스크립트 array는 1차 배열이다. 하지만 배열을 중첩하여 다차원 배열을 생성할 수 있다.

 

이차원 Array 생성

// array를 생성하고 내부에 5개의 빈 배열을 삽입
var twod = [];
var rows = 5;
for (var i = 0; i < rows; ++i) {
       twod[i] = [];
    }

console.log(twod) // (5) [Array(0), Array(0), Array(0), Array(0), Array(0)]

// 직접 생성함수 구현

Array.matrix = function(numrows, numcols, initial) { 
const arr = [];
for (var i = 0; i < numrows; ++i) {
    let columns = [];
    for (let j = 0; j < numcols; ++j) {
                 columns[j] = initial;
              }
              arr[i] = columns;
           }
    return arr; 
}

console.log(Array.matrix(5,5,0));
/**
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
*/

// 들어갈 요소 값을 안다면 직접 값을 넣은 배열로 생성
let grades = [[89, 77, 78],[76, 82, 81],[91, 94, 89]];
console.log(grades[2][2]); // 89

// Array.from() 활용
let arr = Array.from({length:5},()=>Array(5).fill(0));
/**
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]
*/

 

이차원 Array 다루기

 

이차원 array는 요소를 (행)row 또는 (렬) column 위주로 접근하는 패턴이 있다.

두 패턴에 모두 중첩 for문을 사용해 살펴볼 것이다.

 

s1,s2,s3는 column 중심의 데이터 처리, t1,t2,t3는 row 중심의 데이터 처리다.

 

column중심의 처리를 위해서 외부 루프는 row를 순회하고, 내부 루프는 column을 처리한다.

각 행(row)이 한 학생의 성적이고 각 cell이 시험 점수라고 할 때, 각각의 학생들의 평균 성적을 구하는 다음 예제를 살펴보자.

const grades = [[89, 77, 78],[76, 82, 81],[91, 94, 89]];

// 각 학생의 평균 grad을 구하기 위해 
// 각 row의 요소들을 더한 뒤 
// row의 length만큼 나눠주면 구할 수 있다.
let total = 0;
let average = 0.0;
for (let row = 0; row < grades.length; ++row) {
    for (let col = 0; col < grades[row].length; ++col) { 
        total += grades[row][col];
     }
     average = total / grades[row].length;
     console.log("Student " + parseInt(row+1) + " average: " +
         average.toFixed(2));
     total = 0;
     average = 0.0;
}
/**
'Student 1 average: 81.33'
'Student 2 average: 79.67'
'Student 3 average: 91.33'
*/

 

row중심의 처리를 위해서 외부 루프는 column을 순회하고, 내부 루프는 row를 처리한다.

이번에는 각 시험 당 학생들의 평균을 구하는 법을 살펴보자.

const grades = [[89, 77, 78],[76, 82, 81],[91, 94, 89]];

// 각 학생의 평균 grad을 구하기 위해 
// 각 row의 요소들을 더한 뒤 
// row의 length만큼 나눠주면 구할 수 있다.
let total = 0;
let average = 0.0;
for (let col = 0; col < grades.length; ++col) {
    for (let row = 0; row < grades[col].length; ++row) { 
        total += grades[row][col];
     }
     average = total / grades[col].length;
     console.log("Test " + parseInt(col+1) + " average: " +
         average.toFixed(2));
     total = 0;
     average = 0.0;
}
/**
'Test 1 average: 85.33'
'Test 2 average: 84.33'
'Test 3 average: 82.67'
*/

 

Jagged Arrays

Jagged Arrays란 array에 각 row의 길이가 다른 array를 뜻한다. 예를 들면, 어떤 row는 3개의 요소를, 다른 row는 5개의 요소를, 또 다른 row는 요소가 1개뿐일 수 있는 중첩 array다. 이런 들쑥날쑥한 array라고 해도 javascript for-loop을 통해 내부 array의 길이들을 각각 구할 수 있다.

 

let grades = [[89, 77],[76, 82, 81],[91, 94, 89, 99]]; 
let total = 0;
let average = 0.0;
for (var row = 0; row < grades.length; ++row) {
	for (var col = 0; col < grades[row].length; ++col) { 
    	total += grades[row][col];
   }
   average = total / grades[row].length;
   console.log("Student " + parseInt(row+1) + " average: " +
         average.toFixed(2));
   total = 0;
   average = 0.0;
}
/** 
Student 1 average: 83.00
    Student 2 average: 79.67
    Student 3 average: 93.25
*/

Object를 요소로 하는  Array

지금까지 원시 데이터 타입의 값을 요소로 갖는 array에 대해서 살펴봤다.

Array는 원시값뿐만 아니라 객체, 함수, 객체의 프로퍼티 값 등 모두를 요소로 가질 수 있다.

function Point(x,y) { 
	this.x = x;
	this.y = y; 
}
function displayPts(arr) {
for (var i = 0; i < arr.length; ++i) {
   console.log(arr[i].x + ", " + arr[i].y);
   }
}
const p1 = new Point(1,2);
const p2 = new Point(3,5);
const p3 = new Point(2,8);
const p4 = new Point(4,4);
const points = [p1,p2,p3,p4];
for (let i = 0; i < points.length; ++i) {
       console.log("Point " + parseInt(i+1) + ": " + points[i].x + ", " +
             points[i].y);
}
const p5 = new Point(12,-3); 
points.push(p5); 
console.log("After push: ");
displayPts(points);
points.shift();
console.log("After shift: ");
displayPts(points);

/**
 Point 1: 1, 2
    Point 2: 3, 5
    Point 3: 2, 8
    Point 4: 4, 4
    After push:
    1, 2
    3, 5
    2, 8
    4, 4
    12, -3
    After shift:
    3, 5
2, 8 4, 4 12, -3

*/

 

Array를 값으로 갖는 Object

온도 array를 값으로 갖고, 온도를 배열에 추가하고, 평균을 구할 수 있는 객체의 예시를 살펴보자.

function weekTemps() { 
	this.dataStore = []; 
    this.add = add; 
    this.average = average;
}
function add(temp) { 
	this.dataStore.push(temp);
}
function average() {
	let total = 0;
	for (let i = 0; i < this.dataStore.length; ++i) {
		total += this.dataStore[i]; 
    }
	return total / this.dataStore.length; 
}
const thisWeek = new weekTemps(); 
thisWeek.add(52);
thisWeek.add(55);
thisWeek.add(61);
thisWeek.add(65);
thisWeek.add(55);
thisWeek.add(50);
thisWeek.add(52);
thisWeek.add(49);
console.log(thisWeek.average()); // 54.875

 

또는 클래스로 해당 코드를 똑같이 구현할 수 있다.

push() 대신 add 메서드를 활용하면 해당 함수가 무엇을 하는지 직관적으로 알 수 있다. 

class WeekTemps{
    constructor(){
        this.dataStore = [];
    }
    add(temp){
        this.dataStore.push(temp);
    }
    average(){
        let total = 0;
        for (let i = 0; i < this.dataStore.length; ++i) {
            total += this.dataStore[i]; 
        }
        return total / this.dataStore.length;
    }
}
const thisWeek = new WeekTemps();
thisWeek.add(52);
thisWeek.add(55);
thisWeek.add(61);
thisWeek.add(65);
thisWeek.add(55);
thisWeek.add(50);
thisWeek.add(52);
thisWeek.add(49);
console.log(thisWeek.average()); // 54.875

👩🏻‍💻 마치면서 

오늘은 자료구조와 알고리즘에 대해 깊이 살펴보기 전에 자바스크립트에서의 기본 자료구조인 Array에 대해 살펴보았다.
주로 내장된 함수가 많고, 데이터 타입의 제한이 없어서 array를 많이 활용했던 거 같다.
책이 지어진 지 (2014년) 10년이 거의 된 오늘, array 관련 함수와 여러 문법들이 추가되었는데 해당 책에 다루지 못해서 아쉬웠다. 예를 들면, 두 함수를 이어 주기 위해서 스프레드 문법( [...arr1, ...arr2])을 활용할 수 있다.

다음에는 List에 대해 살펴보도록 하자.

---

 

📚 Reference

- Data Structures and Algorithms Using Java‐ Script by Michael McMillian (O’Reilly). Copyright 2014 Michael McMillan, 978-1-449-36493-9