알고리즘 필수 개념과 메서드 (프로그래머스 레벨 1)

 해시 알고리즘(Hash Algorithm)

 

해시는 Key-value 쌍으로 데이터를 저장하는 자료구조입니다. key-value를 이용해 어떤 것과 다른 것 사이의 관계를 모형화할 수 있고, 중복을 막을 수 있습니다. 평균적인 경우 해시 테이블은 모든 항목에 대해 O(1)시간(상수 시간)이 걸립니다. 이는 해시 테이블의 크기에 상관없이 항상 똑같은 시간이 걸린다는 의미로, 해시 테이블에서 무언가를 찾을 때 굉장히 빠릅니다. 알고리즘 테스트에서는 해시를 이용하면 더 효율적으로 해결할 수 있는 문제들을 제시합니다.

 

 

// Object.keys() 오브젝트의 key를 배열로 가져오기

const object1 = {
  a: 'somestring',
  b: 42,
  c: false
};

console.log(Object.keys(object1));
// expected output: Array ["a", "b", "c"]

console.log(Object.keys(object1).length);
// expected output: 3

 

// Object.entries() 주어진 객체의 [key, value] 쌍의 배열을 리턴

const object1 = {
  a: 'somestring',
  b: 42
};

for (const [key, value] of Object.entries(object1)) {
  console.log(`${key}: ${value}`);
}

// expected output:
// "a: somestring"
// "b: 42"
// 순서는 보장되지 않는다.

 

// Object.prototype.hasOwnProperty() 오브젝트가 해당 key를 가지고 있는지 여부를 boolean으로 리턴

const object1 = {};
object1.property1 = 42;

console.log(object1.hasOwnProperty('property1'));
// expected output: true

console.log(object1.hasOwnProperty('toString'));
// expected output: false

 

 

 

 

 스택과 큐(Stack and Queue)

 

스택과 큐는 데이터 구조 중의 일부입니다. 스택은 책을 쌓는 것 처럼 물건을 아래서 부터 위로 쌓는 것처럼 데이터를 세로로 차곡차곡 쌓아 갑니다. 스택에 새로운 데이터를 쌓으려면 가장 위에 데이터를 추가합니다(push). 쌓여 있는 데이터 중 하나를 꺼내려면, 위에서 부터 차례로 모두 꺼내야 합니다(pop). 이처럼 나중에 넣은 것을 먼저 꺼내는 구조를 'Last In First Out'의 약자를 따 'LIFO'라고도 합니다. 큐는 '대기 행렬'이라고 합니다. 주문을 하기위해 줄을 서있는 사람 행렬을 떠올리면 쉽습니다. 큐에 데이터를 추가하면 가장 뒤에 추가가 됩니다(enqueue). 큐에서 데이터를 꺼낼 때는 가장 늦게 추가된 데이터 부터 꺼냅니다(dequeue). 가장 줄을 빨리선 사람부터 주문을 한다고 생각하면 쉽습니다. 먼저 넣은 것을 먼저 꺼내는 구조를 'First In First Out'의 약자를 따 'FIFO'라고 합니다. 

 

// Array.prototype.push()
// push() 메서드는 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새로운 길이를 반환합니다.

const animals = ['pigs', 'goats', 'sheep'];

const count = animals.push('cows');
console.log(count);
// expected output: 4
console.log(animals);
// expected output: Array ["pigs", "goats", "sheep", "cows"]

// Array.prototype.pop()
// pop() 메서드는 배열에서 마지막 요소를 제거하고 그 요소를 반환합니다.

const plants = ['broccoli', 'cauliflower', 'cabbage', 'kale', 'tomato'];

console.log(plants.pop());
// expected output: "tomato"

console.log(plants);
// expected output: Array ["broccoli", "cauliflower", "cabbage", "kale"]


// Array.prototype.shift()
// shift() 메서드는 배열에서 첫 번째 요소를 제거하고, 제거된 요소를 반환합니다. 이 메서드는 배열의 길이를 변하게 합니다.

const array1 = [1, 2, 3];

const firstElement = array1.shift();

console.log(array1);
// expected output: Array [2, 3]

console.log(firstElement);
// expected output: 1


// Array.prototype.unshift()
// unshift() 메서드는 새로운 요소를 배열의 맨 앞쪽에 추가하고, 새로운 길이를 반환합니다.

const array1 = [1, 2, 3];

console.log(array1.unshift(4, 5));
// expected output: 5

console.log(array1);
// expected output: Array [4, 5, 1, 2, 3]

 

 

 

 

 삽입 정렬(Insert sort)

 

왼쪽 끝의 숫자를 정렬이 끝났다고 생각하고, 오른쪽에 있는 숫자와 비교해 자신보다 작으면 위치를 바꿉니다. 이 작업을 모든 숫자가 정렬될 때까지 반복합니다.

 

// sort()

 

 

 

 

 결론

 

아직도 알아야할 게 많다. 

 

 

 

 

 출처

[Object.keys()] - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/keys

[Object.entries()] - https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Object/entries

[Object.prototype.hasOwnProperty()] - https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Object/hasOwnProperty

[Array.prototype.push()] - https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/push

[Array.prototype.pop()] - https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/pop

[Array.prototype.shift()] - https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/shift

[Array.prototype.unshift()] - https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/unshift