분류 전체보기
-
해시 테이블Data Structure & Algorithm 2022. 3. 27. 16:17
정의 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조 특징 요소의 추가는 O(1)이며 키를 알고 있다면 삭제, 탐색도 O(1)로 수행 테이블의 인덱스는 Bucket 이라고 함 테이블의 각 요소는 키-값을 둘 다 저장 Hash: 해쉬 브라운의 해쉬와 같은 단어이며 고기와 감자를 잘게 다져 요리하듯, 입력받은 키를 잘게 잘라 숫자로 만든다는 점에서 유사 해시 함수 입력받은 값을 특정 범위 내 숫자로 변경하는 함수 해시 함수의 결과가 동일하다면 해시 충돌 발생 해시 충동 해결 방법 선형 탐사법: 충돌이 발생하면 인덱스를 옆으로 한 칸 이동 단순하지만 데이터가 몰릴 수 있다는 단점이 있으며 충돌이 연속해서 발생하면 계속해서 옆으로 이동하게 됨 최악의 경우에 탐색에 O..
-
프린터Coding Test/Programmers Level 2 2022. 3. 27. 01:11
문제 https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 코드 function solution(priorities, location) { var indicies = Array.from(new Array(priorities.length), (_, i) => i); var sortedValues = []; var sortedIndicies = []; while(priorities.length !== 0){ var hea..
-
올바른 괄호Coding Test/Programmers Level 2 2022. 3. 27. 00:58
문제 https://programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 programmers.co.kr 코드 function solution(s){ var count = 0; for(var char of s){ if(char === '(') { count += 1; } else { if (count === 0) return false; count -= 1; } } return count === 0; } 설명 위의 ..
-
큐Data Structure & Algorithm 2022. 3. 24. 21:11
정의 First In First Out 이라는 개념을 가진 선형 자료구조 Linear Queue와 Circular Queue가 존재 특징 Front: 큐의 맨 앞 요소 Rear: 큐의 맨 뒤 요소 EnQueue: 큐(의 가장 뒤)에 요소를 추가하는 것 DeQueue: 큐(의 가장 앞)에서 요소를 제거하는 것 현실에서 비유하면 대기열이라고 할 수 있음 Linear Queue 를 Array 로 구현하는 경우 Javascript Array 로 표현 가능하지만 배열의 길이가 고정되어 있지 않기 때문에 큐가 무한정으로 커질 수 있음 DeQueue 를 한 뒤에 요소를 앞으로 당기게 되면 O(n) 의 시간이 소요됨 Linear Queue 를 Linked List 로 구현하는 경우 Front 는 Head 가 되고 Re..
-
스택Data Structure & Algorithm 2022. 3. 23. 21:17
정의 Last In First Out 이라는 개념을 가진 선형 자료구조 특징 push: 스택에 요소를 추가하는 것 pop: 스택에서 요소를 제거하는 것 top: 스택의 가장 위(마지막)에 있는 요소 박스나 프링글스를 비유로 들 수 있음 Javascript 에서 스택 함수 호출이 스택 메모리로 관리됨 배열로 스택 구현 가능 => 배열 요소 사이에 새로운 요소를 추가하거나, 삭제하지 않으므로 효율이 높아짐 Array 클래스에 push, pop 메서드가 구현되어 있음
-
객체Data Structure & Algorithm 2022. 3. 21. 21:17
객체 여러 값을 키-값 형태로 결합시킨 복합 타입 사물함에 비유 가능 Javascript 에서 객체 생성 const obj1 = new Object(); const obj2 = {}; const obj3 = { name: "kim", age: 15}; console.log(obj1); // {} console.log(obj2); // {} console.log(obj3); {name: 'kim', age: 15} 객체에 키-값 추가/삭제 const obj = new Object(); obj['name'] = 'kim'; obj.age = 16; console.log(obj); // {name: 'kim', age: 16} delete obj.age; console.log('name' in obj); //..
-
배열Data Structure & Algorithm 2022. 3. 20. 23:45
정의 연관된 데이터를 연속적인 형태로 저장하는 자료구조 특징 배열에 포함된 원소는 순서대로 번호(index)가 붙음 원하는 원소의 index를 알고 있다면 배열 내의 원소를 찾을 수 있음 배열 내 원소를 삭제하면 해당 index에 빈자리가 생김 고정된 크기를 가지며 일반적으로는 동적으로 크기를 변경할 수 없음 => JS 등의 스크립트 언어에서는 배열의 크기가 가변적인 경우가 많음 배열에 원소 추가/삭제 시 O(n) 이 소요됨 => 추가/삭제가 반복되는 로직에는 배열 사용이 권장되지 않음 탐색이 많은 경우에 유리 Javascript 에서 배열 사용 시 유의할 점 배열 내 원소의 추가/삭제 시 사용되는 splice 의 경우 O(n) 의 시간복잡도를 가짐 배열의 크기가 가변적 자바스크립트의 배열은 기본적으로 ..
-
Big-O 표기법Data Structure & Algorithm 2022. 3. 20. 23:32
Big-O 표기법이란? 시간복잡도를 나타내는 방법 중 하나 Big-O 복잡도 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) n이 모두 같은 수일 때 위의 순서로 복잡도가 높아지며 수행 시간이 늘어남(성능이 떨어짐) Big-O 표기법 4법칙 Big-O 표기법은 점근적 표기법을 따름 따라서 상수를 더하거나 곱하는 등의 표기를 따로 하지 않음 물론 실제 계산에서는 상수에 따라 성능이 달라질 수 있음 계수 법칙 n이 무한에 가까울수록 상수(k)의 의미가 없어지기 때문에 계수를 생략 합의 법칙 Big-O 간 합산 가능 곱의 법칙 Big-O 간 곱셈 가능 다항 법칙 특정 함수가 3차 다항식이면 해당 함수의 Big-O 복잡도는 O(n³) 이 됨 정리 아래 ..