성장일기

🍀 URI / URL / URN의 상관관계 URI는 URL과 URN을 포괄하는 개념이다. 모든 URL과 URN은 URI이라는 말이다. Scheme: 리소스에 접근하는데 사용할 프로토콜. 웹에서는 http나 https 사용 Host: 접근할 대상(서버)의 호스트명 Path: 접근할 대상(서버)의 경로에 대한 상세정보 🍀 URI Uniform Resource Identifie = 인터넷상의 리소스 자체를 식별하는 고유한 문자열 시퀀스 Uniform: 리소스을 식별하는 통일된 방식 Resource: URI로 식별이 가능한 모든 종류의 리소스(웹 브라우저 파일 등)을 지칭함 Identifier: 다른 항목과 구분하기 위해 필요한 정보 => 통합 리소스 식별자 ex) google.com, https://googl..

✅ 트라이(Trie)란? 문자열의 집합을 표현하는 트리 자료구조로, 문자열을 검색하는데 최적화된 구조. 루트부터 문자를 하나씩 따라 내려가면서 일치 여부를 확인하면 됨. 📌 구현 아래 코드는 leetcode 208. Implement Trie (Prefix Tree)의 풀이와 같음 // 트라이의 각 노드의 형태 class TrieNode { constructor() { this.children = {}; // 다음 글자들이 TrieNode로 들어가서 이어짐 this.endWord = false; // 여기까지가 단어의 끝인지 여부 } } // 트라이 생성 // ex) ap, ab => {children: { a: {children: {p: {children: {}, endWord: true}, b: {c..

✅ 다익스트라 알고리즘이란? 가중 그래프에서 최적의 경로를 찾을 때 사용하는 알고리즘 다익스트라라는 네덜란드 프로그래머가 20분만에 카페에서 만듬 GPS, 네트워크 라우팅 등 최적의 경로를 찾아야하는 경우에 많이 사용됨 💡 원리 및 실행과정 출발, 도착 노드를 설정 ex) 1 출발 노드부터 연결된 노드의 최소 거리 저장 ex) 1과 연결된 노드가 2, 4 이므로 두 노드에 최소 거리 저장 2(1), 4(2) 방문하지 않은 노드 중에서 가장 거리가 짧은 노드 선택 ex) 2(1), 4(2) 중 비용이 1로 적은 2 선택 선택한 노드와 연결된 노드의 최소 거리 저장 (저장한 값보다 작다면 최소로 갱신) ex) 3(4), 5(3) 3,4번 반복 ⇒ 도착 노드를 뺀 모든 노드까지의 최소 경로 알 수 있음 도착 ..

들어가기 전에... 해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 더 효율적이고 간결하게 수정된 코드이다. ✅ 그래프란? 유한하고 변할 수 있는 꼭지점이나 노드나 점들의 집합으로 구성된 데이터 구조 💡 구성 요소 정점(vertax): 각 노드 간선(edge): 정점을 잇는 선 💡 그래프의 종류 트리: 두 개의 정점이 하나의 경로로 이어져 있는 그래프 유방향/무방향 그래프: 간선의 방향 유무로 구별되는 그래프 가중/비가중 그래프: 간선에 값 부여 여부로 구별되는 그래프 밀집 그래프: 노드 ↓, 간선 ↑ / 희소 그래프: 노드 ↑, 간선 ↓ ex) 구글 맵을 만든다면 => 가중 & 유방향 그래프 (가중 - 위치 사이에 거리가 값으로 부여 / 유방향 - 일방통행, 쌍방..

들어가기 전에... 해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 작성되었으며, 좀 더 효율적이고 간결하게 수정된 부분이 있다. ✅ 이진 힙이란? 이진 트리를 이용해서 만든 자료구조로 완전 이진 트리이고, 가능한 적은 용량을 차지하기 때문에 효율적임 각 노드는 최대 두 개의 자식을 가짐 최대 이진 힙 : 부모의 값이 자식보다 큼 최소 이진 힙: 자식의 값이 부모보다 큼 형제 사이에는 크기 규칙이 없음 왼쪽부터 오른쪽으로 값을 채워야 함 📌 배열을 이용한 구현 인덱스 규칙 왼쪽 자식 = 부모x2 + 1 오른쪽 자식 = 부모x2 + 2 부모 = Math.floor(자식index-1 / 2) 📝 최대 힙 class MaxBinaryHeap { constructor() ..

들어가기 전에... 해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 작성되었다. 📌 BFS (넓이 우선 탐색) 이진 트리 // 노드 형식 class Node { constructor(val) { this.value = val; this.left = null; this.right = null; } } BFS(rootNode) { if(!rootNode) return null; let queue = [rootNode]; let visited = []; let current; while(queue.length) { current = queue.shift(); visited.push(current.value); if(current.left) queue.push(curren..

들어가기 전에... 해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 작성되었다. 수도 코드를 보고 혼자 구현해보고, 이후 강의에서 주어진 코드를 참고하여 수정했다! 강의에 나온 코드를 최대한 효율적이고 수정했기에 강의 속 코드보다 좋은 코드일 것이라 생각한다. ✅ 이진 탐색 트리 노드의 왼쪽에는 노드의 값보다 작은 숫자가 있어야 한다 노드의 오른쪽에는 노드의 값보다 큰 숫자가 있어야 한다 노드의 왼쪽과 오른쪽에 위치한 트리도 이진 탐색 트리여야 한다 => 왼쪽 트리의 모든 값은 노드보다 작아야하고, 오른쪽은 커야 함 📌 구현 - 연결리스트 class Node{ constructor(value) { this.value = value; this.left = null; ..

들어가기 전에... 해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 작성되었다. 수도 코드를 보고 혼자 구현해보고, 이후 강의에서 주어진 코드를 참고하여 수정했다! 강의에 나온 코드를 최대한 효율적이고 수정했기에 강의 속 코드보다 좋은 코드일 것이라 생각한다. 📌 단일 연결 리스트 // 노드 형식 class Node { constructor(val) { this.val = val; this.next = null; } } class SingleLinkedList { constructor() { this.head = null; this.tail = null; this.length = 0; } // 맨 뒤에 노드 추가 push(val) { let newNode = new..

들어가기 전에... 해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 작성되었다. 수도 코드를 보고 혼자 구현해보고, 이후 강의에서 주어진 코드를 참고하여 수정했다! 최대한 간결하고 효율적이도록 만들었으며, 주어진 코드보다 좋은 코드일 것이라 생각한다! 💡 정렬별 시간·공간복잡도 정리 Algorithm Big-O (상한) Big-θ (평균) Big-Ω (하한) 공간 복잡도 버블 정렬 O(n^2) θ(n^2) Ω(n) O(1) 삽입 정렬 O(n^2) θ(n^2) Ω(n) O(1) 선택 정렬 O(n^2) θ(n^2) Ω(n^2) O(1) 합병 정렬 O(n log n) θ(n log n) Ω(n log n) O(n) 퀵 정렬 O(n^2) θ(n log n) Ω(n log ..

1. 주어진 str를 거꾸로 나열하는 함수를 작성하시오. ex) 'awesome' => 'emosewa' 나의 풀이 function reverse(str){ if(str.length === 1) return str; return str[str.length-1] + reverse(str.slice(0,-1)); } 모범 풀이 function reverse(str){ if(str.length true 나의 풀이 function isPalindrome(str){ function helper(str) { if(str.length === 1) return str; return str[str.length-1] + helper(str.slice(0,-1)); } if(str === hel..