프린세스 다이어리

> 자바스크립트 해시 테이블 구현하는 방법에서 이어진다. class HashTable { table = new Array(3); /// ... } 만약 위 같이 테이블의 길이가 너무 짧은 경우에는 해시 충돌이 일어난다. myTable.setItem('firstName', 'eunjin'); myTable.setItem('lastName', 'lee'); myTable.setItem('age', 29); myTable.setItem('birth', '2000-00-00'); console.log(myTable.getItem('firstName')); // 2000-00-00 console.log(myTable.getItem('lastName')); // 2000-00-00 당장 key-value 4개만 집..

const person = {}; person['firstName'] = 'eunjin'; person['lastName'] = 'lee'; 위 코드는 string 자료형의 key에 해당하는 공간에 string 자료형의 value를 집어넣은 것이다. 이렇게 키와 값의 형태로 데이터를 저장하는 자료 구조를 자바스크립트의 object나 map, 파이썬의 dictionary 등으로 구현할 수 있다. 이들은 모두 해시 테이블의 일종이다. 자료구조를 공부할 때 흔히 이야기하는 해시 테이블이라 함은 특정 오퍼레이션에 대해 시간복잡도를 해결해야 할 때, 원하는 값을 key로 사용하는 자료구조다. 해시 테이블이 무엇인지 공부하고 자바스크립트로 해시 테이블을 짜는 방법을 정리해 보았다. 1. Hash Table 생성하기..

1. 트리란 트리는 나무를 뒤집어 놓은 형태의 자료구조다. 일반적으로 트리의 최상단 노드를 루트 노드라고 하고, 루트 노드에서 가지를 이용해서 각각의 노드로 연결되며, 가장 마지막에 해당하는 원소들을 리프 노드라고 부른다. 또한 트리는 기본적으로 부모와 자식 간의 관계로 이루어져 있다. 가지로 연결된 관계에서 루트 노드에 가까운 노드를 부모 노드, 리프 노드에 가까운 노드를 자식 노드라고 한다. 트리 구조에서 길이란 출발 노드에서 목적지 노드까지 거쳐야 하는 가짓수를 의미한다. 가지를 2번 거쳐서 1번 노드에서 35번 노드까지 간다면, 길이가 2가 되는 것이다. 깊이란 루트 노드에서 특정 노드까지의 길이를 의미한다. 높이는 가장 높은 노드부터 가장 깊은 노드까지의 길이를 의미한다. 2. 이진 트리란 이진..

1. 퀵 정렬이란 퀵 정렬이란 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는 데에 N번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 logN번이 소요되므로, 평균적으로 0(NlogN)의 시간 복잡도를 가진다. 퀵 정렬은 편향된 분할이 발생할 때 연산의 양이 최악의 경우 O(N2) 이다. 따라서 실제로 정렬할 때는 퀵 정렬을 굳이 직접 구현하지는 않는다. C++에 Algorithm 라이브러리에 포함된 sort() 함수는 퀵 정렬을 기반으로 하면서 O(NlogN)을 보장한다. 피벗 값이 가장 왼쪽이라고 가정한다. 5 4 3 8 9 6 7 1 10 2 (1) 5의 왼쪽부터 시작해서 5보다 큰 값을 찾는다. 또 오른쪽부터 시작해..

문제 nums는 숫자로 이루어진 배열입니다. 가장 자주 등장한 숫자를 k 개수만큼 return해주세요. 예시 nums = [1,1,1,2,2,3], k = 2 return [1,2] nums = [1], k = 1 return [1] 접근방향 문제에 최대 nums의 길이나 k의 범위가 제시되어 있지 않아 key를 이용해 상수 시간 복잡도로 접근할 수 있도록 object을 활용하여 풀었다. 마지막에 Object.keys를 활용하여 정렬을 할 때, string 자료형으로 배열에 들어가기 때문에 map함수로 number 형으로 바꿔주는 것에 유의한다. 해답 function topK(nums, k) { let obj = {}; for (let i = 0; i < nums.length; i++) { if (num..

1. 연결 리스트, 큐 구조체 만들기 #include #include #define INF 99999999 typedef struct Node { int data; struct Node *next; } Node; typedef struct Queue { Node *front; Node *rear; int count; } Queue; Queue에는 front, rear, 그리고 큐에 들어가 있는 원소들의 개수를 count로 정했다. 2. push 함수 구현하기 큐는 rear가 가리키는 노드 뒤쪽에 들어가기 때문에, 먼저 노드를 뒤에 만들어 놓고 rear의 next가 그 노드를 가리키게 만든 다음에, rear가 그 노드를 가리키도록 하면 된다. void push(Queue *queue, int data) {..

1. 큐란 무엇인가 큐(queue)는 뒤쪽으로 들어가서 앞쪽으로 나오는 자료 구조다. 스케줄링, 탐색 알고리즘 등에서 다방면으로 활용된다. 큐는 크게 데이터를 넣는 push, 데이터를 빼내는 pop 함수로 이루어진다. 스택과 마찬가지로 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현 방법으로 나누어진다. push(7) -> push(5) -> push(4) -> pop() -> push(6) -> pop() 2. 큐를 배열로 구현하기 #include #define SIZE 10000 #define INF 99999999 int queue[SIZE]; int front = 0; int rear = 0; void push(int data) { if (rear >= SIZE) { printf("큐 오버플..

1. 중위 표기법과 후위 표기법 뜻 중위 표기법이란, 일반적으로 사람이 수식을 표기할 때 사용하는 표기 방법이다. 흔히 우리는 두 개의 피연산자가 있고 한 개의 연산자가 있을 때, 피연산자 사이에 연산자가 들어갈 수 있도록 표기를 한다. 그러나 컴퓨터가 좋아하는 방식은 후위 표기법이다. 후위 표기법은 연산자가 뒤쪽에 위치한다. 중위 표기법: 7 * 9 + 2 후위 표기법: 7 9 * 2 + 2. 기본적인 구조체와 push, pop 함수 만들기 #include #include #include // 문자열을 처리할 거기 때문에 typedef struct Node{ char data[100]; // 하나의 문자열을 담을 수 있도록. 숫자 또는 연산자 등 다양한 형태가 들어가기 떄문에. struct Node *..