☘️ 트라이(Trie) 트라이 정의 트라이는 트리 형태로 되어 있는 자료구조이다. 트라이 문자열 저장 문자열을 효율적으로 탐색하기 위한 자료구조 이전 정점으로부터 더해진 문자열 정보 가짐 트라이 특징 검색어 자동완성, 사전 찾기 트라이는 검색어 자동완성, 사전 찾기 등에서 활용된다. 효율적인 문자열 탐색 단순하게 문자열을 비교하여 탐색하는 것보다 효율적이게 찾을 수 있다. 탐색 시간 문자열을 탐색, 삽입하는 시간 복잡도는 문자열의 길이만큼 소요된다. 문자열 길이: L 시간 복잡도: O(L) 저장공간 각 정점이 자식에 대한 링크를 전부 가지고 있어 저장공간이 많이 차지한다는 단점이 있다. 트라이 구조 특징 빈 루트 트라이의 Root는 문자열이 없는 비어있는 상태이다. 간선(링크) 키 값 각 간선(링크)는 ..

☘️ 힙(Heap) 우선순위 큐 우선 순위가 높은 요소가 먼저 나가는 큐 힙(Heap)은 우선순위 큐를 구현하기 위한 가장 적합한 자료구조이다. 그러면 힙(Heap)은 무엇일까? 힙(Heap) 이진 트리 형태 우선 순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬됨 우선 순위가 높은 요소는 Root에 배치 여기서 우선순위 큐는 자료구조가 아닌 개념이고 힙은 우선순위 큐라는 개념을 구현하기 위한 자료구조이다. 만약 우선순위 큐를 힙이 아닌 배열을 사용하면 매번 우선순위에 따라 정렬이 되며, 단지 힙보다 효율이 떨어질 뿐이다. 우선순위 큐 != 힙 힙의 특징 우선 순위 먼저 나감 힙은 이진트리 형태로 우선 순위가 가장 높은 요소가 Root에 배치하고 항상 먼저 나간다. 최대 힙, 최..

☘️ 그래프 그래프 정의 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조 그래프에서 정점은 Node, 간선은 Edge 라고 불리며, 아래 사진에서 파란색 원이 정점(node), 검은색 선이 간선(edge) 이다. 그래프 사용 예시 이러한 그래프가 사용되는 예시로는 지하철 노선로가 있다. 지하철역이 정점(node), 지하철역과 역 사이를 이어주는 것이 간선(edge) 이라고 할 수 있다. 그래프 특징 1. 다수의 간선 그래프는 비선형 구조라서 정점이 여러 개의 간선을 가질 수 있다. 비선형 구조 하나의 데이터에 여러 개의 데이터가 존재할 수 있고, 데이터 간 1:n 또는 n:n 관계를 가짐 2. 방향, 무방향 그래프 그래프는 방향이 있는 방향 그래프와, 방향이 없는 무방향 그래프가 있다. 3..

☘️ 해시 테이블 해시 테이블은 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조 각 테이블에 해당하는 index를 해시 테이블에서는 buckets 이라고 하며, 테이블의 각 요소는 키와 값이 저장되어 있다. 해시 테이블에서 요소를 삽입하는 것은 상수 시간 O(1) 이 소요되며, 키를 알고 있을 경우 요소를 삭제, 탐색하는 것도 상수 시간 O(1) 이 소요된다. 해시 함수 입력받은 값을 특정 범위 내 숫자로 변경하는 함수 키 값을 해시 함수를 통해 해싱하여 buckets에 저장하며, 해시 함수는 특정한 구현 방법이 없어 사용자 마음대로 구현하면 된다. 해시 테이블 문제점 해시 함수를 통해 키 값을 해싱하는데, 만약 해시 함수의 결과가 동일하여 겹칠 수 있다는 문..

☘️ 스택(stack) 스택은 LIFO(Last In First Out) 로 "나중에 들어간 것이 먼저 나온다" 라는 개념을 가진 선형 자료구조이다. 예를 들어 아래부터 1, 2, 3, 4, 5 상자를 순서대로 넣으면, 뺄 때 순서대로 5, 4, 3, 2, 1 이렇게 되는 구조이다. 여기서 요소를 넣는 것을 Push, 빼는 것을 Pop 이라고 하며, 제일 위에 있는 요소를 Top이라고 한다. ☘️ 자바스크립트에서 스택(stack) 구현 자바스크립트에서 스택을 구현하기 위해 배열(Array)를 사용할 수 있다. 이미 배열에 push와 pop 함수가 구현되어 있어서 보다 편리하다. 그래서 아래 코드와 같이 배열을 사용하여 스택을 구현할 수 있다. 코딩 테스트에서 스택을 사용하는 경우로는 짝을 맞춰야 하는 문..

☘️ 연결 리스트 사용하는 이유 그 전 글에서 배열을 알아보았는데, 배열 같은 경우 원하는 위치에 데이터를 추가하고 삽입하는 경우에 시간 복잡도가 O(n) 으로 크다. 그래서 요소 추가와 삭제가 반복되는 로직 같은 경우는 배열을 사용하지 않고 연결 리스트를 사용하고, 배열은 탐색이 많은 로직에서 사용하면 좋다. 배열 - 탐색 유리 연결 리스트 - 요소 추가, 삭제 유리 ☘️ 연결 리스트란? 연결 리스트 정의 연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조로 각 요소는 노드라고 부르고, 각 노드에는 해당 노드의 값이 있는 데이터 영역과 다음 노드를 가리키는 포인터 영역으로 구성된다. 그리고 첫번째 노드를 헤드(Head)라고 부른다. 연결리스트의 핵심 로직은 요소 찾기 요소 추가 요소 삭제..

☘️ 배열 배열은 연관된 데이터를 연속적인 형태로 저장하는 복합 타입으로, 배열에 포함된 원소는 순서대로 인덱스가 붙는다. 또한 배열은 탐색이 유리한 자료구조이다. 만약 배열의 요소를 추가 및 삭제하면 O(n) 이 소요된다. 그래서 요소의 추가와 삭제가 반복되는 로직일 경우 배열을 사용하지 않는 것이 좋다. ☘️ 배열 생성 자바스크립트에서 배열은 다음과 같이 다양한 방법으로 배열을 생성할 수 있다. 또한 자바스크립트에서 배열은 크기가 고정되어 있지 않고, 필요에 따라 줄이거나 늘릴 수 있다. ☘️ 배열 요소 추가, 삭제 - push, pop, splice push와 pop을 사용할 경우 빅오 표기법이 O(1) 이다. 그러나 splice를 사용하여 중간에 값을 추가하거나, 제거하면 빅오 표기법이 O(n) ..

☘️ 빅오 표기법 빅오 표기법은 시간 복잡도를 표현하기 위해 사용되는 것이다. O (log n) O (n) O (n log n) O (n^2) ☘️ 성능 측정 방법 자바스크립트 Date 객체 이용 다음과 같이 측정하고 싶은 명령어의 앞 뒤로 시간을 구하여 그 시간의 차이를 사용하여 성능을 측정한다. ☘️ 계수 법칙 n이 무한에 가까울 수록 상수 k의 크기는 의미가 없어 생략한다. ☘️ 합의 법칙, 곱의 법칙 빅오 표기법은 서로 더해질 수 있고, 곱해질 수 있다. ☘️ 빅오 표기법 핵심 상수항은 무시 O(4n) => O(n) 가장 큰 항 이외엔 무시 O(n^2 + n) => O(n^2) 해당 게시물은 프로그래머스 - 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 참고하여 작성한 글입니다...

☘️ 자료구조란? 자료구조(data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상 자료형의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다. [출처 - 위키백과] ☘️ 현실 세계에서 자료구조 만약에 영화 예매 소프트웨어를 만든다면 영화 검색(Trie), 고객이 많을 경우 줄을 서야함(Queue), 고..