개발새발 로그

정렬 요소들을 일정한 순서대로 열거하는 알고리즘 정렬의 특징 - 정렬 기준은 사용자가 정할 수 있다. - 크게 비교식과 분산식 정렬로 나눌 수 있다. - 대부분의 언어가 빌트인으로 제공해준다. - 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재한다. 비교식 정렬 버블 정렬 - 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘 - O(n^2) 시간복잡도를 가진다. 버블정렬 이 과정을 반복한다.(가장 큰 수가 뒤로간다.) function solution(arr){ let answer=arr; for(let i=0; i

구글이나 네이버 검색에서 자동완성을 하려면 어떻게 해야할까? 이런 경우에 사용하기에 적합한 자료 구조로 트라이(Trie) 가 있다. 트라이 - 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 구조 트라이의 특징 - 검색어 자동완성, 사전 찾기 등에 응용될 수 있다. - 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다. - L이 문자열의 길이일 때, 삽입은 O(L)만큼 걸린다. - 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 더 많은 저장공간을 사용한다. Trie 생성하기 Trie 구조 - 루트는 비어있다. - 각 간선은 추가될 문자를 키로 가진다. - 각 정점은 이전 정점의 값 + 간선의 키를 값으로가진다. - 해시테이블과 연결리스트를 이용하여 구현할 수 있다. 자..

우선순위 큐 - FIFO인 큐와 달리 우선순위가 높은 요소가 먼저 나가는 큐 - 이때 우선순위 큐는 자료구조가 아닌 개념이다. 우선순위 큐를 구현하는 방법은 다양하게 존재한다. 그 중 힙은 우선순위 큐를 구현하기에 가장 적합한 방법이다. 힙 - 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 정렬되는 특징이 있다. 우선순위 큐와 힙은 다른 것이다! -만약 배열을 매번 우선순위에 따라 정렬하면 그것도 우선순위 큐가 될 수 있다. 단지 힙보다 효율이 떨어질 뿐이다. 힙의 특징 - 우선순위가 높은 요소가 먼저나가는 특징을 가진다. - 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙이 있다. - 아쉽게도 자바스크립트에서는 직접 구현해서 사용..

비선형 자료구조인 트리에 대해서 알아보자 트리 - 방향 그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 구조를 가지고 있다. 트리의 특징 - 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다. - 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다. - 루트에서 특정 정점으로 가는 경로는 유일하다. -> 하나의 부모 정점을 가지기 때문에 생긴 특징 이진 트리 - 이진트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미한다. 이진트리 완전 이진트리 : 마지막 레벨을 제외하고 모두 채워져 있는 이진 트리 포화 이진 트리 : 완전히 채워져 있는 이진 트리 편향 트리 : 한 방향으로만 정점이 이어진 이진 트리 이진트리의 특징 - 정점이 N개인 이진트리는 최악의 경우 높이가 N이 될 ..

그래프 - 정점과 정점사이를 연결하는 간선으로 이루어진 비선형 자료구조 - 정점 집합과 간선 집합으로 표현할 수 있다. - ex) 지하철 노선도, 페이지랭크 알고리즘 그래프의 특징 - 정점은 여러개의 간선을 가질 수 있다. - 크게 방향그래프와 무방향 그래프로 나눌 수 있다. - 간선은 가중치를 가질 수 있다. - 사이클이 발생할 수 있다. 무방향 그래프 - 간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다. - 표현하기에 (A,B)와 (B,A)는 같은 간선으로 취급된다. 방향 그래프 - 간선에 방향성이 존재하는 그래프 - 양방향으로 갈 수 있더라도 와 는 다른 간선으로 취급된다. 연결 그래프 -모든 정점이 서로 이동이 가능한 상태 그래프 - 특정 정점에서 다른 특정 정점까지 모든 경우의 수가 이동가..

해시테일블은 사물함이라고 생각하면 된다. 사물함 각 칸에는 이름과 번호가 있어서 쉽게 위치를 찾을 수 있다. 해시테이블은 한정된 배열 공간에 key를 index로 변환하여 값들을 넣게된다. 그럼 index는 어떻게 구할까? 해시테이블 - 키와 값을 받아 키를 해싱하여 나온 index에 값을 저장하는 선형자료구조 - 삽입은 O(1)이며 키를 알고 있다면 삭제, 탐색도 O(1)로 수행한다. 해시 함수 - 입력받은 값을 특정 범위 내 숫자로 변경하는 함수 - 해시함수는 특정한 구현 방법이 있지 않아서 사용자 임의대로 만들면 된다. - 예를 들어 입력받은 문자열을 각 문자열의 아스키코드를 더한 값을 해시로 정할 수 있다. 해시테이블의 문제점 만약 해시 함수의 결과가 동일하여 겹친다면 문제가 생긴다. -> 이를 ..

큐 - First In First Out이라는 개념을 가진 선형 자료구조이다. - Linear Queue(선형 큐)의 Circular Queue(환형 큐)가 존재한다. Linear Queue Array로 표현하기 -Linear Queue를 Array로 표현할 수 있다. - EnQueue가 계속 되어 한정된 공간인 배열이 꽉 차게 된다면 더이상 큐에 값을 추가할 수가 없습니다. - 자바스크립트에서는 배열의 크기가 자동적으로 증감되기 때문에 이러한 문제가 없지만 Front나 Rear의 인덱스 값이 무한정 커질 수 있다는 문재가 있다. -> 공간을 더 활용하기 위해 데이터를 앞당기는 작업이 필요하다. -> 이 작업을 수행하면 선형시간이 소요된다. -> 이런 문제를 해결하기위해 연결리스트로 큐를구현해야한다. A..

스택 Last In First Out이라는 개념을 가진 선형 자료구조 스택 메모리 스택을 Array로 표현하기 push : 배열에 순차적으로 값을 삽입한다. pop : 가장 마지막 요소를 제거한다. 이런 방식은 배열의 단점인 중간요소 추가, 삭제 로직이 전혀 사용되지 않기 때문에 굉장히 유리한 방식이다. 또한 자바스크립트에서는 배열의 크기가 동적으로 변하기때문에 더 편하게 구현이 가능하다. 물론 자바스크립트의 배열은 Array타입은 아니므로 컴파일러언어보다는 성능이 떨어질 수 있다. Linked List로 표현하기 스택을 Linked List로 표현할 수 있다. 이 경우 연길리스트의 haed가 Top이라고 할 수 있다. 자바스크립트에서 stack 사용법 const stack = []; // Push 사용..