4. Factorial

November 5, 2018 Algorithms

What is Factorial?

Factorial이란, 해당하는 수부터 그 이하로 1까지를 모두 곱하는 수를 말한다.
예를 들어, 3!이면 3 x 2 x 1 = 6을 말한다.

[Problem]

Factorial을 구현하는 함수를 작성하시오.

[Algorithms]

number가 1일 경우, number를 반환한다.
number가 2이상이면 number부터 1씩 값을 줄여가면서, 모두 곱한다.
곱한 최종 값을 반환한다.

[Solution]

function factorial(number) {
  if(number === 1) return number;
  let result = 1;
  for (var i = number; i >= 1 ; --i ) {
    result *= i;
  }

  return result;
}

console.log(factorial(5)); // 120

[Better Practice]

function factorial(number) {
  if(number === 1) {
      return number;
  } else {
      return number * factorial(number-1);
  }
}

console.log(factorial(5)); // 120

String Method

November 5, 2018 Algorithms

1. String.prototype.charAt(index)

매개변수로 전달한 index 번호에 해당하는 위치의 문자를 반환한다.
index 번호는 0 ~ (문자열 길이 - 1) 사이의 정수이다.

const str = 'Hello';

console.log(str.charAt(0)); // H
console.log(str.charAt(1)); // e
console.log(str.charAt(2)); // l
console.log(str.charAt(3)); // l
console.log(str.charAt(4)); // o

// 지정한 index가 범위(0 ~ str.length-1)를 벗어난 경우 빈문자열을 반환한다.
console.log(str.charAt(5)); // ''

2. String.prototype.concat(index)

매개변수로 전달된 1개 이상의 문자열과 연결하여 새로운 문자열을 반환한다.
concat 메소드를 사용하는 것보다는 +, += 할당 연산자를 사용하는 것이 성능상 유리하다.

let str = 'My name is ';
let name = 'Cheon';

str = str.concat(name); // str = str + name;
console.log(str); // 'My name is Cheon'

3. String.prototype.split(string | regular Expression, number)

첫번째 인자에 전달된 문자열 또는 정규표현식을 대상 문자열에서 검색하여 문자열을 구분한 후, 분리된 각 문자열로 이루어진 배열을 반환한다.
원본 문자열은 변경되지 않는다.
인수가 없는 경우, 대상 문자열 전체를 단일 요소로 하는 배열을 반환한다.

let str = 'How are you doing?';

// 공백으로 구분(단어로 구분)하여 배열로 반환한다
let splitStr = str.split(' ');
console.log(splitStr); // [ 'How', 'are', 'you', 'doing?' ]

// 원본 문자열은 변경되지 않는다
console.log(str); // How are you doing?


// 인수가 없는 경우, 대상 문자열 전체를 단일 요소로 하는 배열을 반환한다.
splitStr = str.split();
console.log(splitStr); // [ 'How are you doing?' ]

// 각 문자를 모두 분리한다
splitStr = str.split('');
console.log(splitStr); // [ 'H','o','w',' ','a','r','e',' ','y','o','u',' ','d','o','i','n','g','?' ]

// 공백으로 구분하여 배열로 반환한다. 단 요소수는 3개까지만 허용한다
splitStr = str.split(' ', 3);
console.log(splitStr); // [ 'How', 'are', 'you' ]

// 'o'으로 구분하여 배열로 반환한다.
splitStr = str.split('o');
console.log(splitStr); // [ 'H', 'w are y', 'u d', 'ing?' ]

4. String.prototype.substring(start, end)

첫번째 인자에 전달된 index(start)에 해당하는 문자부터 두번째 인자에 전달된 index(end)에 해당하는 문자의 바로 이전 문자까지를 모두 반환한다.
이때 첫번째 인수 < 두번째 인수의 관계가 성립된다.

let str = 'Hello World'; // str.length == 11

let res = str.substring(1, 4);
console.log(res); // ell

// 첫번째 인수 > 두번째 인수 : 두 인수는 교환된다.
res = str.substring(4, 1);
console.log(res); // ell

// 두번째 인수가 생략된 경우 : 해당 문자열의 끝까지 반환한다.
res = str.substring(4);
console.log(res); // o World

5. String.prototype.toLowerCase()

대상 문자열의 모든 문자를 소문자로 변경한다.

let str = 'Hello World!';

const res = str.toLowerCase();
console.log(res); // hello world!

6. String.prototype.toUpperCase()

대상 문자열의 모든 문자를 대문자로 변경한다.

let str = 'Hello World!';

const res = str.toUpperCase();
console.log(res); // HELLO WORLD!

Array Method for Advanced

November 5, 2018 Algorithms

1. Array.prototype.forEach(function(elem, index, array))

배열을 순회하며 배열의 각 요소에 대하여 인자로 주어진 콜백함수를 실행한다.
콜백함수의 매개변수를 통해 배열 요소의 값(elem), 요소 인덱스(index), 순회할 배열(array)을 전달 받을 수 있다.
반환값은 undefined이다.
forEach 메소드는 원본배열을 변경하지 않는다.
forEach 메소드는 for 문과는 달리 break 문을 사용할 수 없고, 일반 for 구문에 비해 성능이 좋지는 않다.
forEach()는 배열을 순회하며 요소 값을 참조하여 무언가를 하기 위한 함수

let sum = 0;
const arr = [1, 3, 5, 7, 9];

arr.forEach(function (elem, index, array) {
  console.log('[' + index + '] = ' + elem);
  sum += elem;
});

console.log(sum); // 25

// 원본배열이 유지된다.
console.log(arr); // [ 1, 3, 5, 7, 9 ]

2. Array.prototype.map(function(elem, index, array))

배열을 순회하며 각 요소에 대하여 인자로 주어진 콜백함수의 반환값(결과값)으로 새로운 배열을 생성하여 반환한다.
원본 배열은 변경되지 않는다.
콜백함수의 매개변수를 통해 배열 요소의 값(elem), 요소 인덱스(index), 순회할 배열(array)을 전달 받을 수 있다.
map()은 배열을 순회하며 요소 값을 다른 값으로 맵핑하기 위한 함수이다.

const arr = [1, 4, 9];

// 배열을 순회하며 각 요소에 대하여 인자로 주어진 콜백함수를 실행
const result = arr.map(elem => {
  return Math.sqrt(elem);
});

// map 메소드는 새로운 배열을 반환한다
console.log(result);   // [ 1, 2, 3 ]

// map 메소드는 원본 배열은 변경하지 않는다
console.log(arr); // [ 1, 4, 9 ]

3. Array.prototype.filter(function(elem, index, array))

배열을 순회하며 각 요소에 대하여 인자로 주어진 콜백함수의 실행 결과가 true인 배열 요소의 값만을 추출한 새로운 배열을 반환한다.
이때 원본 배열은 변경되지 않는다.
콜백함수의 매개변수를 통해 배열 요소의 값(elem), 요소 인덱스(index), 순회할 배열(array)을 전달 받을 수 있다.
filter()는 배열에서 특정 케이스만 필터링 조건으로 추출하여 새로운 배열을 만들고 싶을 때 사용한다.

const arr = [1, 2, 3, 4, 5];
const result = arr.filter(function (elem, index, array) {
  console.log('[' + index + '] = ' + elem);
  return elem % 2; // 홀수만을 필터링한다 (1은 true로 평가된다)
});

console.log(result); // [ 1, 3, 5 ]

// 원본배열은 유지된다.
console.log(arr); // [ 1, 2, 3, 4, 5 ]

정렬 함수 sort() 사용법

November 5, 2018 Algorithms

Array.prototype.sort()

배열안에 원소를 정렬하는 함수로, 원본 배열을 직접 변경하며 정렬된 배열을 반환한다.

sort(compareFunction) 함수는 sort() 안에 인자로 정렬 순서를 정의하는 함수를 넣어서 정렬을 한다. 만약, 생략하게 되면, 기본 문자열에 순서에 따라 정렬이 된다. 즉, ASCII 문자 순서(오름차순)로 정렬된다. 또한, sort() 함수는 정렬하는 원소가 문자열, 숫자, 또는 객체형이냐에 따라 사용법이 조금씩 다르다.

sort() 안에 인자인 compareFunction를 지정하면, 값은 아래 중 하나로 반환된다.

첫번째 인수가 두번째 인수보다 작을 경우 -> ‘-‘
첫번째 인수가 두번째 인수보다 클 경우 -> ‘+’
두 인수가 같을 경우 -> 0

1. 정렬할 원소가 문자열일 경우

// 오름차순
const arr = ['orange', 'apple', 'banana'];

console.log(arr.sort()); // [ 'apple', 'banana', 'orange' ]

// 내림차순(ES6) - 문자열끼리 비교할 때는 비교연산자를 사용한다.(숫자는 뺄셈연산자 사용)
console.log(arr.sort((a, b) => {
  if(a > b) return -1;
  else if(b> a) return 1;
  else return 0;
})); // [ 'orange', 'banana', 'apple' ]

// 내림차순(ES5) - 문자열끼리 비교할 때는 비교연산자를 사용한다.(숫자는 뺄셈연산자 사용)
console.log(arr.sort(function(a, b) {
  if(a > b) return -1;
  else if(b> a) return 1;
  else return 0;
})); // [ 'orange', 'banana', 'apple' ]

2. 정렬할 원소가 숫자일 경우

const arr = [3, 11, 12, 10, 9, 1];

// ASCII 문자 순서로 정렬되어 숫자의 크기대로 나오지 않음 -> sort()안에 인자로 함수를 추가해줘야 함
console.log(arr.sort()); // [ 1, 10, 11, 12, 3, 9 ]

// 오름차순(ES6)
console.log(arr.sort((a, b) => { // [ 1, 3, 9, 10, 11, 12 ]
  return a - b;
}));

// 오름차순(ES5)
console.log(arr.sort(function(a, b) { // [ 1, 3, 9, 10, 11, 12 ]
    return a - b;
}));

// 내림차순(ES6)
console.log(arr.sort((a, b) => { // [ 12, 11, 10, 9, 3, 1 ]
  return b - a;
}));

// 내림차순(ES5)
console.log(arr.sort(function(a, b) { // [ 12, 11, 10, 9, 3, 1 ]
    return b - a;
}));

3. 정렬할 원소가 객체일 경우

const person = [
  { name : "john", age : 25},
  { name : "smith", age : 15},
  { name : "ro", age : 35},
  { name : "park", age : 45}
]

/* 이름순으로 정렬 */
// 문자열끼리 비교할 때는 비교연산자를 사용한다.

// 오름차순(ES6)
console.log(person.sort((a, b) => {
  return a.name < b.name ? -1 : a.name > b.name ? 1 : 0;
})); // [ { name: 'john', age: 25 }, { name: 'park', age: 45 }, { name: 'ro', age: 35 }, { name: 'smith', age: 15 } ]

// 오름차순(ES5)
console.log(person.sort(function(a, b) {
  return a.name < b.name ? -1 : a.name > b.name ? 1 : 0;
})); // [ { name: 'john', age: 25 }, { name: 'park', age: 45 }, { name: 'ro', age: 35 }, { name: 'smith', age: 15 } ]


// 내림차순(ES6)
console.log(person.sort((a, b) => {
  return a.name > b.name ? -1 : a.name < b.name ? 1 : 0;
})); // [ { name: 'smith', age: 15 }, { name: 'ro', age: 35 }, { name: 'park', age: 45 }, { name: 'john', age: 25 } ]

// 내림차순(ES5)
console.log(person.sort(function(a, b) {
  return a.name > b.name ? -1 : a.name < b.name ? 1 : 0;
})); // [ { name: 'smith', age: 15 }, { name: 'ro', age: 35 }, { name: 'park', age: 45 }, { name: 'john', age: 25 } ]


/* 나이순으로 정렬 */
// 숫자끼리 비교할 때는 뺄셈연산자를 사용한다.

const sortingField = "age";

// 오름차순(ES6)
console.log(person.sort((a, b) => {
  return a[sortingField] - b[sortingField];
})); // [ { name: 'smith', age: 15 }, { name: 'john', age: 25 }, { name: 'ro', age: 35 }, { name: 'park', age: 45 } ]

// 오름차순(ES5)
console.log(person.sort(function(a, b) {
  return a[sortingField] - b[sortingField];
})); // [ { name: 'smith', age: 15 }, { name: 'john', age: 25 }, { name: 'ro', age: 35 }, { name: 'park', age: 45 } ]


// 내림차순(ES6)
console.log(person.sort((a, b) => {
  return b[sortingField] - a[sortingField];
})); // [ { name: 'park', age: 45 }, { name: 'ro', age: 35 }, { name: 'john', age: 25 }, { name: 'smith', age: 15 } ]

// 내림차순(ES5)
console.log(person.sort(function(a, b) {
  return b[sortingField] - a[sortingField];
})); // [ { name: 'park', age: 45 }, { name: 'ro', age: 35 }, { name: 'john', age: 25 }, { name: 'smith', age: 15 } ]

Array Method for Basic

November 5, 2018 Algorithms

1. Array.prototype.indexOf()

arr.indexOf(searchElement, fromIndex): arr에서 찾아야할 값(searchElement)이 몇번째 인덱스부터(fromIndex) 시작해서 그 찾아야할 값에 대한 index를 찾을 때 사용

indexOf 메소드의 인자로 지정된 요소를 배열에서 검색하여 인덱스를 반환한다. 중복되는 요소가 있는 경우 첫번째 인덱스만 반환된다. 만일 해당하는 요소가 없는 경우, -1을 반환한다.

const arr = [1, 2, 2, 3];
console.log(arr.indexOf(2));    // 1
console.log(arr.indexOf(4));    // -1
console.log(arr.indexOf(2, 2)); // 1

2. Array.prototype.concat()

concat 메소드의 인수로 넘어온 값들(배열 또는 값)을 자신의 복사본에 요소로 추가하고 반환한다. 이때 원본 배열은 변경되지 않는다.

const arr1 = ['a', 'b', 'c'];
const arr2 = ['x', 'y', 'z'];

const c = arr1.concat(arr2);
console.log(c); // ['a', 'b', 'c', 'x', 'y', 'z']

const d = arr1.concat('hello');
console.log(d); // ['a', 'b', 'c', 'hello']

// 원본 배열은 변하지 않는다.
console.log(arr1); // [ 'a', 'b', 'c' ]

3. Array.prototype.join()

배열 요소 전체를 연결하여 생성한 문자열을 반환한다. 구분자(separator)는 생략 가능하며 기본 구분자는 ,이다. 이때, 원본 배열은 유지된다.

const arr = ['a', 'b', 'c', 'd'];

const x = arr.join();
console.log(x);  // 'a,b,c,d';

const y = arr.join('');
console.log(y);  // 'abcd'

const z = arr.join(':');
console.log(z);  // 'a:b:c:d'

console.log(arr); // [ 'a', 'b', 'c', 'd' ]

4. Array.prototype.reverse()

배열 요소의 순서를 반대로 변경한다. 이때 원본 배열이 변경된다. 반환값은 변경된 배열이다.

const arr1 = ['a', 'b', 'c'];
const arr2 = arr1.reverse();

// 원본 배열이 변경된다
console.log(arr1); // [ 'c', 'b', 'a' ]
console.log(arr2); // [ 'c', 'b', 'a' ]

5. Array.prototype.slice(start, end)

인자로 지정된 배열의 부분을 복사하여 반환한다. 원본 배열은 변경되지 않는다. 첫번째 매개변수 start에 해당하는 인덱스를 갖는 요소부터 매개변수 end에 해당하는 인덱스를 가진 요소 전까지 복사된다.

const arr = ['a', 'b', 'c', 'd', 'e'];

// items[1]부터 items[2] 이전(items[2] 미포함)까지 반환
const res2 = arr.slice(1, 2);
console.log(res2);  // [ 'b' ]

// items[1]부터 이후의 모든 요소 반환
const res3 = arr.slice(1);
console.log(res3);  // [ 'b', 'c', 'd', 'e' ]

// 인자가 음수인 경우 배열의 끝에서 2개의 요소를 반환
const res4 = arr.slice(-2);
console.log(res4);  // [ 'd', 'e' ]

// 모든 요소를 반환 (= 복사본 생성)
const res5 = arr.slice();
console.log(res5);  // [ 'a', 'b', 'c', 'd', 'e' ]

// 원본은 변경되지 않는다.
console.log(arr); // [ 'a', 'b', 'c', 'd', 'e' ]

6. Array.prototype.splice(start, end)

기존의 배열의 요소를 제거하고 그 위치에 새로운 요소를 추가한다. 배열 중간에 새로운 요소를 추가할 때도 사용되고, 삭제만 할 때도 사용된다.

const arr = [1, 2, 3, 4, 5, 6];

// items[1]부터 2개의 요소를 제거하고 제거된 요소를 배열로 반환
const res = arr.splice(1, 2);

// 원본 배열이 변경된다.
console.log(arr); // [ 1, 4, 5, 6 ]
// 제거한 요소가 배열로 반환된다.
console.log(res);   // [ 2, 3 ]

7. Array.prototype.push()/pop()/shift()/unshift()

4가지 메소드는 모두 원본을 변경한다.

출처: Array push/pop/shift/unshift

8. Array.prototype.includes()

arr.includes(searchElement, fromIndex): 배열에 특정 요소가 포함되어 있는지 여부를 확인할 때 사용

const arr = [1,2,3,4];
const result1 = arr.includes(3);
const result2 = arr.includes(1, 1);
console.log(result1); // true
console.log(result2); // false
// 원본 배열이 유지된다.
console.log(arr); // [1,2,3,4]

9. Array.prototype.toString()

arr.toString(): 배열에 있는 원소를 문자열로 반환할 때 사용

const arr = [1,2,3];
const result = arr.toString();
console.log(result); // "1,2,3"
// 원본 배열이 유지된다.
console.log(arr); // [1,2,3]

Javascript Technique for Algorithms

November 5, 2018 Algorithms

배열이나 문자열에서 i번째 인덱스 내용을 삭제해야 하는 경우

1. 원본을 유지하면서, 삭제하는 방법

array 메소드 중, slice()를 사용하면, 원본을 유지하면서, 삭제된 새로운 배열을 생성할 수 있다.

const arr = [1,2,3,4,5];
const newArr = [...arr.slice(0,3), ...arr.slice(4)]; // 3번째 인덱스 삭제

console.log(newArr); // [1,2,4,5]
console.log(arr); // [1,2,3,4,5]

2. 원본을 변경하면서, 삭제하는 방법

array 메소드 중, splice()를 사용하면, 특정 요소를 삭제함으로써, 원본이 변경된 배열이 된다.

1
2
3

const arr = [1,2,3,4,5];
arr.splice(3,1); // 3번 인덱스부터 1개를 삭제
console.log(arr); // [1,2,3,5]

배열이나 문자열에서 중복을 제거해야 할 때

Set을 사용해서 중복을 제거할 수 있다.(Set은 unique한 자료형만을 저장한다.)

// 배열
const arr = [1, 3, 2, 9, 9, 1, 5, 1, 4, 5, 2];
console.log(new Set(arr)); // { 1, 3, 2, 9, 5, 4 }
const newArr = [...new Set(arr)];
console.log(newArr); // [ 1, 3, 2, 9, 5, 4 ]

// 문자열
const str = "abcdacbe";
console.log(new Set(str)); // { 'a', 'b', 'c', 'd', 'e' }
const newStr = [...new Set(str)].join('');
console.log(newStr); // "abcde"

배열이나 문자열에서 딱 1개만 있는 요소를 찾아야 할 경우

array 메소드 중, filter()와 indexOf()를 사용하면, 딱 1개만 있는 요소를 찾을 수 있다.

// 배열
const arr = [3, 3, 3, 7, 3];
const filterArr = arr.filter( elem => arr.indexOf(elem) === arr.lastIndexOf(elem) );
console.log(filterArr); // [7]

// 문자열
const str = '33373';
const filterStr = str.split('').filter( elem => str.indexOf(elem) === str.lastIndexOf(elem) );
console.log(filterStr); // ['7']

배열에 규칙적인 연속된 값 할당해야할 경우

Array()와 fill()를 사용한다.

const newArr = Array(5).fill(2);
console.log(newArr); // [2, 2, 2, 2, 2]
const newArr2 = Array(5).fill(1).map( (elem, i) => elem + i );
console.log(newArr2); // [1,2,3,4,5]

배열에 최대값/최소값을 찾아야 할 경우

Math.max(), Math.min()를 사용한다.

// 최대값
const arr = [1, 2, 3];
const max = Math.max(...arr); // 3
console.log(max);

// 최소값
const arr = [1, 2, 3];
const min = Math.min(...arr); // 3
console.log(min);

지정된 숫자를 자신보다 작은, 가까운 정수로 내림해야 할 경우

Math.floor()를 사용한다.

const floor1 = Math.floor(2.9); // 2
const floor2 = Math.floor(9.1); // 9
const floor3 = Math.floor(-1.9); // -2
const floor4 = Math.floor(-9.1); // -10

console.log(floor1);
console.log(floor2);
console.log(floor3);
console.log(floor4);

지정된 숫자를 자신보다 큰, 가까운 정수로 올림해야 할 경우

Math.ceil()를 사용한다.

const ceil1 = Math.ceil(1.1);  // 2
const ceil2 = Math.ceil(-1.4); // -1

console.log(ceil1);
console.log(ceil2);

Hash Table이란 무엇인가?

November 4, 2018 Computer Science

Hash Table(해시 테이블)

Hash Table이란, 검색하고자 하는 key 값을 입력받아서 해시함수를 돌려서 반환받은 해시코드를 배열의 인덱스로 환산해서 데이터에 접근하는 방식의 자료구조이다.

Hash Table 작동원리

출처: Hash Table

검색하고자 하는 Key 값을 해시함수를 돌리면, 해시코드를 반환받는다.(해시코드는 정수이다)
반환된 해시코드를 배열의 개수로 나머지(%) 연산을 해서 인덱스 번호로 바꾼다. 예를 들어, 어떤 Key 값의 해시코드가 445이고 배열의 크기가 3이면, 445 % 3 = 1이 되어, 인덱스 번호는 1이 된다.
이 인덱스 번호로 배열에 데이터를 저장한다. 예를 들어, 인덱스 번호가 1이라면, 배열에서 배열방 1번에 저장한다.
즉, 해시코드 자체가 배열방의 인덱스로 사용되어 검색이 필요없고, 해시코드로 바로 배열의 데이터에 접근이 가능하다.
각 배열방에 저장되어 있는 데이터들은 연결 리스트로 되어 있어, 배열방에 새로운 데이터가 추가될 때마다, 연결 리스트에 추가가 된다.
어떤 Key 값에 대한 검색 요청이 들어와 인덱스로 환산한 뒤, 어떤 배열방에서 그 Key 값을 찾기 위해서는, 그 배열방에 연결 리스트를 순회화면서 그 Key 값을 찾는다.

Hash Table 특징

장점: 해시코드 자체가 배열방의 인덱스로 사용되어 다른 검색이 필요없이 해시코드로 바로 배열의 데이터에 접근이 가능하기 때문에, 시간복잡도가 O(1)이다.
단점: 1개의 배열방에 여러 데이터가 겹쳐서 저장되는 경우를 Collision(충돌)이라고 하는데, 이 경우 시간복잡도는 O(n)이다. 이는, 배열방에서 그 Key 값을 찾기 위해, 그 배열방에 연결 리스트를 순회화면서 그 Key 값을 찾아야 하기 때문이다. 이런 문제가 생기는 경우는 크게 2가지이다.
- 서로 다른 Key 값이지만, 동일한 해시코드로 반환받는 경우
  - Key 값은 문자열이고 그 가짓수가 무한한대 반해서 해시코드는 정수개 밖에 제공을 못하기 때문에, 알고리즘이 아무리 좋아도 어떤 Key들은 중복되는 해시코드를 가질 수 밖에 없다.
- 서로 다른 해시코드이지만, 동일한 인덱스로 바뀌는 경우
  - 배열방은 한정되어 있기 때문에, 서로 다른 해시코드이더라도, 환산할 때 동일한 인덱스를 얻게 되는 경우가 있을 수 있기 때문에, 같은 배열방에 배정받는 경우도 있다.

이런 Collision을 최소화하기 위해서는 좋은 해시 알고리즘을 만드는 것이 중요하다. 즉, 배열방을 나눌 때, 규칙을 잘 만들어야 한다.

리스트(List)란 무엇인가?

November 4, 2018 Computer Science

리스트(List)

리스트란, 자료를 순서대로 한 줄로 저장하는 선형 자료구조이다.

head: 리스트에서 제일 처음 데이터를 head라고 한다.
tail: 리스트에서 제일 마지막 데이터를 tail이라고 한다.

리스트(List)의 종류

리스트는 구현방식에 따라, 다음과 같이 분류된다.

순차 리스트(Array List): 배열을 기반으로 구현된 리스트
연결 리스트(Linked List 메모리의 동적 할당을 기반으로 구현된 리스트

출처: ArrayList vs. LinkedList

두 리스트의 차이점을 더 자세하게 알고 싶다면, Linked List와 Array의 차이점를 클릭한다.

연결 리스트(Linked List)의 종류

1. Simple Linked List(단순 연결 리스트)

단순 연결 리스트란, 연결의 형태가 한쪽 방향으로 전개되고 시작과 끝이 분명히 존재하는 리스트를 말한다.

출처: Simple Linked List

2. Doubly Linked List(이중/양방향 연결 리스트)

이중/양방향 연결 리스트란, 노드가 양쪽 방향으로 연결된 구조의 리스트를 말한다. 즉, 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드도 왼쪽 노드를 가리키는 구조이다.

출처: Doubly Linked List

3. Circular Linked List(원형/환형 연결 리스트)

원형/환형 연결 리스트란, 단순 연결 리스트에서 마지막 노드가 첫 번째 노드를 가리켜서 연결의 형태가 원을 이루는 리스트를 말한다.

출처: Circular LinkedList

자료구조(Data Structures)의 분류

November 4, 2018 Computer Science

자료구조(Data Structures)

자료구조란, 자료의 집합으로써, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것을 말한다.

자료구조의 분류

자료구조는 다음과 같이 분류되어 있다.

출처: Data Structures

Stack과 Queue, 그리고 Deque의 차이점

November 4, 2018 Computer Science

Stack

Stack이란, 한쪽 끝에서만 데이터의 삽입, 삭제가 이루어지는 자료구조다.

가장 마지막에 삽입된 항목이 맨 먼저 삭제된다. -> Last In First Out(LIFO)
- push: Stack에 데이터를 넣는 연산
- pop: Stack에 데이터를 꺼내는 연산
- peek: Stack에 데이터를 들여다 보는 연산

출처: Stack

Stack 구현

1. class를 이용한 Stack 구현(ES6)

// ES6
class Stack {
  constructor() {
    this.count = 0;
    this.dataStore = [];
  }

  push(element) {
    this.dataStore[this.count] = element;
    this.count++;
  }

  pop() {
    if(this.count >= 1) {
      let val = this.dataStore[this.count - 1];
      this.count--;
      return val;
    }
    return null;
  }

  peek() {
    return this.dataStore[this.count - 1];
  }

  size() {
    return this.count;
  }

  isEmpty() {
    return this.count === 0;
  }

  clear() {
    this.count = 0;
    this.dataStore = [];
  }
}

// for Test
const stack = new Stack();
console.log(stack); // { count: 0, dataStore: [] }
stack.push('ro1');
stack.push('ro2');
stack.push('ro3');
console.log(stack.peek()); // ro3
console.log(stack.pop()); // ro3
console.log(stack.pop()); // ro2
console.log(stack.size()); // 1
console.log(stack.isEmpty()); // false
console.log(stack.pop()); // ro1
console.log(stack.pop()); // null

2. 생성자 함수를 이용한 Stack 구현(ES5)

// ES5
function Stack() {
  var dataStore = [];
  var count = 0;

  this.push = function(element) {
    dataStore[count] = element;
    count++;
  };

  this.pop = function() {
    if(count >= 1) {
      let val = dataStore[count - 1];
      count--;
      return val;
    }
    return null;
  };

  this.peek = function() {
    return dataStore[count - 1];
  };

  this.size = function() {
      return count;
  };

  this.isEmpty = function() {
    return count === 0;
  };
}

// for Test
var stack = new Stack();
console.log(stack); // { push: [Function], pop: [Function], peek: [Function], size: [Function], isEmpty: [Function] }
stack.push('ro1');
stack.push('ro2');
stack.push('ro3');
console.log(stack.peek()); // ro3
console.log(stack.pop()); // ro3
console.log(stack.pop()); // ro2
console.log(stack.size()); // 1
console.log(stack.isEmpty()); // false
console.log(stack.pop()); // ro1
console.log(stack.pop()); // null

Queue

Queue란, 데이터의 삽입이 한쪽 끝(뒤, rear)에서 이루어지고, 삭제는 다른 쪽(앞, front)에서 이루어지는 자료구조다.

가장 처음 삽입된 항목이 맨 먼저 삭제된다. -> First In First Out(FIFO)
- enqueue: Queue에 데이터를 넣는 연산
- dequeue: Queue에 데이터를 꺼내는 연산

출처: Queue

Queue 구현(2개의 Stack으로 Queue 구현)

1. class를 이용한 Queue 구현(ES6)

// Stack
class Stack {
  constructor() {
    this.count = 0;
    this.dataStore = [];
  }

  push(element) {
    this.dataStore[this.count] = element;
    this.count++;
  }

  pop() {
    if(this.count >= 1) {
      let val = this.dataStore[this.count - 1];
      this.count--;
      return val;
    }
    return null;
  }

  peek() {
    return this.dataStore[this.count - 1];
  }

  size() {
    return this.count;
  }

  isEmpty() {
    return this.count === 0;
  }

  clear() {
    this.count = 0;
    this.dataStore = [];
  }
}

// Queue
class Queue {
  constructor() {
    this.inbox = new Stack();
    this.outbox = new Stack();
    this.size = 0;
  }

  eneque(element) {
    this.inbox.push(element);
  }

  dequeue() {
    if(this.outbox.size() === 0) {
      while(this.inbox.size()) {
        this.outbox.push(this.inbox.pop());
      }
    }
    return this.outbox.pop();
  }

  size() {
    return this.inbox.size() + this.outbox.size();
  }
}

// for Test
const queue = new Queue();
console.log(queue); // { inbox: Stack { count: 0, dataStore: [] }, outbox: Stack { count: 0, dataStore: [] } size: 0 }
queue.eneque('a');
queue.eneque('b');
queue.eneque('c');
console.log(queue.dequeue()); // a
console.log(queue.dequeue()); // b
queue.eneque('d');
queue.eneque('e');
console.log(queue.dequeue()); // c
console.log(queue.dequeue()); // d

2. 생성자 함수를 이용한 Queue 구현(ES5)

// Stack
function Stack() {
  var dataStore = [];
  var count = 0;

  this.push = function(element) {
    dataStore[count] = element;
    count++;
  };

  this.pop = function() {
    if(count >= 1) {
      let val = dataStore[count - 1];
      count--;
      return val;
    }
    return null;
  };

  this.peek = function() {
    return dataStore[count - 1];
  };

  this.size = function() {
      return count;
  };

  this.isEmpty = function() {
    return count === 0;
  };
}

// Queue
function Queue() {
  var inbox = new Stack();
  var outbox = new Stack();

  this.eneque = function(element) {
    inbox.push(element);
  };

  this.dequeue = function() {
      if (outbox.size() === 0) {
          while (inbox.size())
              outbox.push(inbox.pop());
      }
      return outbox.pop();
  };

  this.size = function(){
    return inbox.size() + outbox.size();
  };
}

// for Test
var queue = new Queue();
console.log(queue); // { eneque: [Function], dequeue: [Function], size: [Function] }
queue.eneque('a');
queue.eneque('b');
queue.eneque('c');
console.log(queue.dequeue()); // a
console.log(queue.dequeue()); // b
queue.eneque('d');
queue.eneque('e');
console.log(queue.dequeue()); // c
console.log(queue.dequeue()); // d

Deque

Deque란, 데이터의 삽입과 삭제를 앞, 뒤 양쪽에서 이루어지는 자료구조다.

출처: Deque