JavaScript

백트래킹 모든 경우의 수를 탐색하는 알고리즘 DFS나 BFS를 이용할 수 있다 가지치기(Pruning) : 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것 자바스크립트는 재귀 효율이 나쁘게 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다 탐색에서 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다 핵심은 가지치기 !!! 백트래킹 로직을 어떻게 작성할 것인가? 우선 모든 경우의 수를 찾을 수 있도록 코딩 이후 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머지는 탐색하지 않도록 조건문을 작성 즉, 절대로 답이 될 수 없는 문제는 탐색을 종료한다 동적계획법 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식 그리디(Greedy)나 백트래킹처럼 특정 알고리즘이 아닌 문제 해결..

너비 우선 탐색 (BFS) 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘 BFS의 특징 Queue를 이용하여 구현할 수 있다 시작 지점부터 가까운 정점부터 탐색 V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V + E)다 깊이 우선 탐색(DFS) 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘 DFS의 특징 Stack을 이용하여 구현할 수 있다 시작 정점에서 깊은 것부터 찾는다 V가 정점의 수, E가 간선의 수일 때, DFS의 시간복잡도는 O(V + E)다 그리디 (Greedy) 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘 최적해를 보장해주지 않는다 그리디 알고리즘의 특징 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다 크..

큐 (Queue) First In First Out(FIFO)라는 개념을 가진 선형 자료구조 Linear Queue(선형 큐) 와 Circular Queue(환형 큐)가 존재 큐의 가장 앞에 있는 원소의 인덱스(위치)는 front로 나타내며, 가장 뒤에 있는 원소의 인덱스(위치)는 rear라고 한다 Linear Queue (선형 큐) Array(배열)로 구현 class Queue { constructor() { this.queue = []; this.front = 0; this.rear = 0; } enqueue(value) { this.queue[this.rear++] = value; } dequeue() { const value = this.queue[this.front]; delete this.qu..

네트워크 기초 브라우저에 URL을 입력하면 무슨일이 발생할까?? 1. URL을 해석한다 url 구조 : scheme://:@:/ 2. DNS를 조회한다. DNS(Domain Name System) : 도메인 주소와 IP 주소를 서로 변환해준다 브라우저는 DNS로 요청은 보내기 이미 해당 도메인을 알고 있는지 찾아보고 없으면 local 컴퓨터의 host 파일 참조 3. 해당 IP 서버로 이동을 한다 라우터를 이용한다 동적 라우팅을 통해 이동 4. ARP를 이용하여 MAC 주소 변환을 합니다 ARP(Address Resolution Protocol) : 논리 주소인 IP주소를 물리 주소인 MAC 주소로 변환하는 프로토콜 네트워크 내에 ARP를 Broadcasting하면 해당 IP 주소를 가지고 있는 기기가 ..