다이나믹 프로그래밍 이란? 주어진 문제를 여러개의 부분 문제들로 나누어 푼다음, 겹치는 문제의 경우 메모이제이션 기법을 사용하여 주어진 문제를 푼다 기억하며 풀기라고 한다. 사용하는이유 일반적인 재귀와 DP는 매우 유사하다. 차이점은 일반적인 재귀를 사용할 때는 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다. DP는 Memoization 기법을 통해 반복되는 작은 문제들의 결과 값을 저장해 두고 재사용하여 계산 속도를 향상시킨다. 특징 분할가능 -> 큰문제들을 작은 문제로 나눈다. 작게 나눈 문제는 항상 같은 값을 도출해야한다. 부분 문제반복 -> subproblem 들이 겹칠 때 memoization을 통해 필요한 연산 수를 줄일 수 있다 최적 부분 구조 -> subpr..

해쉬란? 해쉬는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 말한다. 다른 말로는 해시 값이라고한다. 사용하는경우 배열의 인덱스위치, 위치, 데이터 값을 저장하거나 검색할때 활용된다. 특징 키(KEY)에 데이터(VALUE)를 매핑할 수 있는 데이터 구조 해쉬 함수를 통해 키의 데이터를 배열에 저장할 수 있는 주소(인덱스 번호)를 계산 장단점 장점 데이터 저장/ 읽기 속도가 빠름 (검색속도가 빠름) 해시는 키에 대한 데이터가 있는지 확인이 쉬움 단점 일반적으로 저장곤간이 많이 필요 여러 키에 해당하는 주소(인덱스)가 동일한 경우 충돌을 해결하기 위한 별도 자료구조 필요 코드 class hashTable{ constructor(size){ this.storage = []; if(size){ this.s..

그리디 알고리즘이란? 최적의 값을 구해야하는 상황에서 사용되는 방법으로 ' 매선택에서 지금 이순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자' 가 모토이다. 비유하자면 마시멜로 실험을 생각하면된다 -> 그리디 알고리즘을 사용한다는것은 당장 눈앞에있는 마시멜로를 먹는것이다. 하지만 이방법을 사용하는것은 기다렸다가 2개를 먹는다라는 최적해를 보장해주지 못한다 사용하는이유 항상 최적의 선택을하기때문에 앞서봤던 깊이우선탐색(dp) 보다 빠른 속도를 낸다 특징 최적부분 구조이다. -> 한번의 선택이 다음선택에는 전혀 무관한 값이며 매순간의 최적해가 문제에대한 최적해야여한다는의미이다. 원리 위의 그림을 보면서 아래 설명의 봐보자. 1. 시작 정점을 7로 설정 (최대값을 구할때) 2. 3과 12중에 하나를 골..

깊이 우선탐색 (Depth-Firtst Search) 깊이우선 탐색이란? 루트노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이라고한다. 즉, 깊게 탐색, 완벽탐색 사용하는경우 모든 노드를 방문 하고자 하는 경우에 이방법을 선택한다. 특징 1. 자기자신을 호출하는 순환 알고리즘의 형태를 가지고있다. 2. 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. 원리 위의 그림을 보면서 아래 설명을 봐보자. 1. 시작 정점을 1로 설정 2. 1번 탐색 시작 1번과 연결되었고 방문 안한 정점이 어디지? 2번이 있네. 2번으로 가자. 3. 2번과 연결되었고, 방문 안한것? 3번이네. 3번으로 가자. 4. 3번은? 4번이 있네. 4번으로 가자. 5. 4번은? 없는데..?? 그러면 3번..

프로젝트를 진행하면서 파일첨부기능을 구현하던중 multipart/form-data 에대한 사용이 필요했다 오늘은 정리할겸 HTTP, multipart/form-data 키워드에대해서 알아보고 그중에서 multipart/form-data 에 대해서 알아보자 http란 HyperText Transfer Protocal 이다. 문서를 전송하기위한 프로토콜 즉 서버와 클라이언트의 사이에서 어떻게 메시지를 교환할지를 정해 놓은 규칙이다. 우리가하용하는 웹브라우저에서 인터넷 주소 맨 앞에들어가는 http://가 바로 이프로토콜을 사용해서 정보를 교환하겠다는 표시이다. 데이터를 교환할때 타입은 두가지가 있다. 요청과 응답이다. 1. 파일 업로드를 구현할 때, 클라이언트가 웹브라우저라면 폼을 통해서 파일을 등록해서 전..

사용자의 로그인 상태를 서버에서 처리하는데 사용할수있는 대표적인 두가지 인증방식이있다. 1. 세션을 기반으로 인증 2. 토큰을 기반으로 인증 1. 세션 기반 인증 시스템 세션을 기반으로 인증 시스템을 만든다는것은 서버가 사용자가 로그인중임을 기억하고 있다는 뜻이다. 직접그려서 글씨체가 이상한건 양해.... 세션 기반 인증시스템에서 사용자가 로그인을 하면, 서버는 세션 저장소에 사용자의 정보를 조회하고 세션 id를 발급한다 발급된 id는 주로 브라우저의 쿠키에 저장한다. 그다음에 사용자가 다른 요청을 보낼때마다 서버는 세션 저장소에서 세션을 조회한후 로그인 여부를 결정하여 작업을 처리하고 응답을 한다 세션 기반 인증의 단점은 서버를 확장하기가 번거로워 질 수 있다는 점이다. 만약 서버의 인스턴스가 여러개가..