해시맵(Hash Map)은 많이 들어본 개념이다 하지만 해시를 이용한 셋(Set)과 트리를 이용한 셋(set)과 맵(Map)은 뭘까?셋(Set)중복되지 않는 원소들의 집합으로, 특정 원소의 존재 여부를 빠르게 확인할 수 있다.맵(Map)키-값(Key-Value) 쌍으로 데이터를 저장하는 자료구조로, 각 키는 유일하며 키를 통해 값에 빠르게 접근할 수 있다.트리를 이용한 Set과 Map트리를 이용한 Set과 Map은 이진 탐색 트리(Binary Search Tree, BST), 특히 균형 이진 탐색 트리(예: 레드-블랙 트리)를 사용하여 구현된다.특징정렬된 데이터: 원소들이 자동으로 정렬된 상태로 저장된다.탐색, 삽입, 삭제의 시간 복잡도: 평균 및 최악의 경우 모두 O(log n)이다다.순회가 용이: 중..

나는 평소 C++을 이용해 알고리즘 문제를 풀고있다. 근데 코딩테스트에서 사용할 수 있는 언어에 C++이 없어서 자바스크립트로 코딩테스트를 봐야한다. 평소 자바스크립트를 하고 있기에 큰 문제가 되지는 않았다. 알고리즘을 위한 자바스크립트 문법을 정리했다. 배열순회Array.prototype.forEachconst arr = [1, 2, 3, 4, 5];arr.forEach((e, i)=>{ console.log(`${i}번째 요소 ${e}`);})문자열 분해String.prototype.split문자열을 구분자를 기준으로 여러개의 문자열로 나누어 배열로 만들어주는 함수const str = "1,2,3,4,5";const ret = string.split(",");console.log(ret) // ["..

문제 개요문제 번호: 3986제목: 좋은단어난이도: 실버 4링크: 백준 3986번문제 설명같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓는다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 좋은단어의 갯수를 찾는 문제선을 그었을 때 교차하지 않으면 좋은 단어이다.선을 그었을 때 교차하면 좋은 단어가 아니다.접근 방법단어를 순회한다스택이 비어있다면 push지금 단어가 스택의 top에 있는 문자와 같다면 pop모든 조건이 다르다면 push단어 순회가 끝났는데 스택이 비어있다면 좋은단어구현 코드#include#include#define endl "\n"using namespace std;int main(){ i..

문제 개요문제 번호: 6198제목: 옥상 정원 꾸미기난이도: 골드 5링크: 백준 6298번문제 설명도시에는 N개의 빌딩이 있다.i번째 빌딩의 키가 h-i이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우 = = = = - = = = = -> 관리인이 보는 방향 = - = = = = = = = = = 10 3 7 4 12..

문제 개요문제 번호: 5397제목: 키로거난이도: 실버 2링크: 백준 5397번문제 설명창영이라는 나쁜 친구가 강산이의 번호를 훔치기위해 키로거를 강산이 컴퓨터에 설치했다. 이 키로거는 강산이가 입력하는 입력 문자와 방향키(), 백스페이스(-)를 추적한다. 한줄에 입력되는 입력을 통해 강산이의 비밀번호를 알아내는 문제다.접근 방법문자열을 입력받아 문자열을 순회하면서 다음과 로직을 만든다1. ': 커서를 왼쪽으로 미룬다. -> cursor--2. '>'인 경우: 커서를 오른쪽으로 미룬다. -> cursor++3. '-'인 경우: 커서 기준으로 왼쪽 문자를 지운다.4. 문자인 경우: 커서 기준으로 오른쪽에 문자를 삽입하고 커서를 오른쪽으로 미룬다.문제 조건에서 문자열 길이가 최대 1,000,000일 수 있다..

RB-Tree의 정의와 특성Red-Black Tree(RB-Tree)는 자가 균형 이진 탐색 트리의 한 종류로, 각 노드에 추가적인 비트(색상)를 저장하여 트리의 균형을 유지한다.주요 특성:이진 탐색 트리의 모든 특성을 만족한다.각 노드는 red 또는 black다.트리의 균형을 유지하여 최악의 경우에도 O(log n)의 시간 복잡도를 보장한다.RB-Tree의 규칙과 속성RB-Tree는 다음 규칙을 만족해야 한다:모든 노드는 red 또는 black이다.루트 노드는 항상 black이다.모든 리프 노드(NIL)는 black이다.red 노드의 자식은 모두 black이어야한다. (red 노드는 연속될 수 없다)임의의 노드에서 그 노드의 자손인 리프 노드에 이르는 모든 경로에는 동일한 개수의 black 노드가 있어..

AVL 트리란?AVL트리는 노드가 추가될 때, 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리이다.주요 특징:모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1자동으로 균형을 유지하여 항상 O(log n) 시간 복잡도 보장균형 인수 (Balance Factor)AVL 트리의 핵심은 '균형 인수(밸런스 팩터)'다.균형 인수 = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이이 값은 항상 -1, 0, 1 중 하나여야 한다.이 범위를 벗어나면 재조정(rebalancing)을 해야한다.AVL 트리 연산1. 검색 (Search)일반 이진 탐색 트리와 동일한 방식으로 수행된다.2. 삽입 (Insertion)일반적인 BST 삽입 수행삽입 경로를 따라 올라가며 균형 인수 업데..

이진탐색 트리(BST)란?모든 노드가 아래와 같은 특정 순서를 따르는 속성이 있는 이진 트리다각 노드는 최대 두 개의 자식 노드를 가진다왼쪽 서브트리의 모든 노드는 현재 노드보다 작은 값을 가진다오른쪽 서브트리의 모든 노드는 현재 노드보다 큰 값을 가진다중복된 노드가 없어야 한다.BST의 주요 연산 (조회, 삽입, 삭제) 및 시간 복잡도조회 (Search)평균 시간 복잡도: O(log n)최악의 경우 (불균형 트리): O(n)삽입 (Insertion)평균 시간 복잡도: O(log n)최악의 경우 (불균형 트리): O(n)삭제 (Deletion)평균 시간 복잡도: O(log n)최악의 경우 (불균형 트리): O(n)BST의 균형과 불균형 문제BST의 성능은 트리의 균형에 크게 의존한다. 균형 잡힌 BST..