WASD BLOG

최근에 다른 블로그를 따라해보면서 웹 공부를 시작했는데, 자바스크립트와 HTML(pug) 간의 통신에서 주소 값을 잘못 넣어주어 고생을 했고, 혹시 까먹을까봐 다시 정리해보려고 한다. 메인 페이지에서 Upload 버튼을 누르면 비디오를 업로드하는 페이지가 뜨도록 만들기 위해 다음과 같은 코드를 짰다. 비디오 관련 루트들을 연결해주는 videoRouter.js (getUpload와 postUpload는 videoController.js 에서 import 했다.) videoController.js 의 getUpload 함수 - 단순히 videoUpload.pug를 찾아 불러와준다. 메인 페이지의 헤더 부분인데, routes.upload = "/upload" 로 저장되어 있어 위에 videoRouter에서와 똑같아 잘 실행이 될 줄 알았다... 하지만.. 페이지의 연결이 잘못된 건 확실한데 컨트롤러, html 파일, 라우터 등 죄다 건드려봐도 답이 나오지 않았다. 문제는 아예 다른 곳에 있었는데, 여기서 videoRouter를 붙여줄 때 이미 routes.videos = "/videos" 를 붙여주고 시작했었다; 설정된 경로는 "/videos/upload"인데 자꾸 "/upload" 로 가라고 하니까 당연히 되질 않는거였다.. 메인 페이지에서 목적지 경로(?) 를 "/videos/upload" 로 바꿔주니 해결되었다.

HTML 태그 찾기 귀찮을까봐 모아둠. html 선언 (html 5) : <!DOCTYPE html> <html> : HTML 문서의 root 요소를 정의 <head> : <title>, <style>, <meta>, <link>, <script>, <base> 태그 등의 메타데이터를 정의하는 부분 - 웹에는 직접 표시되진 않음 <body> : 웹 브라우저를 통해 보여지는 내용 부분. <h1> ~ <h6> : 6가지 크기의 제목 태그 <p> : 단락 태그(개행 문자 무시, 띄어쓰기는 단 한번만 적용) <br> : 줄 나누기 태그(종료 태그 x) <pre> : 작성된 그대로 웹에 출력되는 태그(font 는 fixed-width로 자동 적용) <hr> : 수평선 태그 <b> : 단순히 글씨만 굵게 해주는 태그 <strong> : 글씨가 굵어지고, 해당 내용이 중요하다는 정보도 포함되는 태그 <i> : 단순히 글씨만 이탤릭체로 보이게 해주는 태그 <em> : 글씨가 이탤릭체로 보이고, 해당 내용이 중요하다는 정보도 포함되는 태그 <makr> : 해당 텍스트에 색을 칠해주는 태그 <del> : 해당 텍스트에 취소선을 그어주는 태그 <ins> : 해당 텍스트에 밑줄을 그어주는 태그 <sup> : 해당 텍스트를 위첨자로 표기하는 태그 <sub> : 해당 텍스트를 아래첨자로 표기하는 태그 <q> : 짧은 인용구, 해당 텍스트 앞 뒤에 큰따옴표가 붙는 태그 <blockquote> : 블록 인용구, 해당 인용구를 별도의 단락으로 구분해주는 태그 <abbr> : 해당 텍스트에 마우스를 올려놓으면...

문제(링크) LCS 알고리즘 응용문제입니다. dp[i][j] = i, j 지점에서 나올 수 있는 최대 유사도 공백을 추가할 때, 현재 유사도가 음수가 되버리면 그 지점부터 다시 시작하는게 이득입니다. 따라서 lcs 알고리즘과 비슷하게 문자가 같지 않다면 왼쪽, 왼쪽 위, 위 값의 최댓값을 현재 값으로 가져오는데 해당 값에 공백을 추가한 값, 즉, -2 를 한 값을 가져오고 최종 값이 음수가 되면 0으로 바꿔줘야 합니다. 문자가 같다면 lcs 알고리즘에서 처럼 +3을 해줍니다. dp 배열을 완성했다면 유사도가 최대인 점을 찾습니다. 최대인 점으로부터 가로, 세로, 대각선을 체크하면서 시작 점을 찾아가는데, 가로, 세로는 +2 , 대각선은 -3 으로 찾아가면서 0이 될때까지 찾아가고, 역으로 시작점부터 끝점까지 출력하면 됩니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> #define pdd pair<double, double> #define pic pair<int, char> #define ll long long #define vi vector<int> #define vl vector<long long> #define vc vector<char> #define vii vector<pii> #define IMAX 2000000001 #define LM...

1. LIS (Longest Increase Subsequence, 최장 증가 수열) 보통 수열 내의 가장 긴 오름차순 부분 수열을 찾는 문제. - dp[] 배열(부분 수열 저장 - ArrayList)과 value[] 배열(값 저장)을 만든다. - value[] 배열을 끝까지 돌면서 다음 작업을 수행한다. - 1) dp[] 배열이 비어있다면 그냥 추가. - 2) dp[] 배열의 마지막 값 < value[] 현재값 v -> dp[] 마지막에 추가. - 3) dp[] 배열의 마지막 값 >= value[] 현재값 v ->    dp[] 배열에서 v를 정렬되도록 추가한다.(원래의 값과 바꿈)    선형 탐색 시 (N^2), 이분 탐색 시(NlogN) - 주의할 점 : 최장 증가 수열의 길이는 dp[] 의 크기지만 안의 내용은 다를 수 있기 때문에 최장 증가 수열을 출력하려면 따로 인덱싱을 해주는 배열이 필요하다. - 부분 수열 출력 방법 : 이분 탐색을 이용한 nlogn 방법에선 이분 탐색으로 dp[] 내의 값을 수정할 때 수정한 수의 전까지는 LIS 를 만족하기 때문에 trace[수정한 수] = 바로 이전 값(dp[] 에서) 위와 같이 경로를 만들어 준다.(수정하지 않고 마지막에 추가할 경우도 똑같이 이전 값을 넣어준다, 경로의 끝은 -1로 초기화해준다.) dp[] 배열의 마지막 수부터 trace 배열을 역으로 탐색하면 가장 긴 부분 수열을 출력할 수 있다. 위와 같이 하게 되면 다음과 같은 반례가 나온다 6 1 3 5 7 2 3 답은 4 1 3 5 7 이지만 4 1 2 3 5 7 이 나온다. trace 배열을 모든 value 값에 대해 만들어 주는데, trace[i] 는 value[i] 가 dp[] 에서 어느 인덱스에 있는지를 저장해준다. 그 뒤 trace 배열을 뒤에서부터 탐색하고, dp 사이즈 -1 부터 시작하여 trace[i]의 인덱스 ==...

(2,4) Tree 란? BST(Binary Search Tree)와 비슷하게 In-Order 의 순서로 값이 정렬되는데, 각 노드들의 Entry가 1개~3개인 Multi-Way Tree 의 한 종류이다. 각 Entry에 INF Entry를 더해 총 2개~4개가 되어 (2,4)라고 불린다. 각 Entry는 자식 노드를 하나 가지는데 자신의 값 이하의 노드와 연결된다. Insertion BST처럼 왼쪽, 오른쪽 값들을 비교해가면서 자기 값의 자리를 찾아간다. 찾은 자리에 공간이 남는다면 (Entry가 2개 이하라면) 그 자리에 들어가면 되지만 오버플로우가 발생할 수도 있다. 추가 후에 Entry가 4개가 되어 오버플로우가 발생하면, 왼쪽부터 두 개의 Entry, 오른쪽부터 한 개의 Entry로 쪼개고, 남는 중간 하나의 Entry는 부모 노드로 올려준다. 그 Entry의 왼쪽, 오른쪽이 먼저 쪼갠 두 개의 노드가 된다. 부모 노드로 Entry를 올려주게되면 부모 노드에서도 오버플로우가 발생할 수 있는데, 계속 전파하면된다. 만약 root 노드까지 오버플로우가 발생해 더 이상 올려줄 부모 노드가 없게 되면, 새로운 root노드를 만들어 올려준다. Deletion BST에서처럼 자식 노드가 없다면 그대로 삭제 자식 노드가 하나라면 자식 노드의 부모를 자신의 부모로 바꿔주고 삭제 자식 노드가 여러 개라면 In-Order 순서로 자신 다음 혹은 자신 바로 전 순서의 값과 바꾼 뒤 삭제 위 방식을 그대로 사용한다. 하지만 삭제 시에 노드의 Entry가 0개가 되는 언더플로우가 발생할 수 있다. 언더플로우 발생 시 1. 가까운 형제 노드(깊이가 같은 노드) 의 Entry가 2개 이상인 경우 (Entry를 줘도 언더플로우x)  - 형제 노드의 부모 Entry 값을 자신에게 가져오고, 형제 노드의 Entry는 부모 노드로 올린다. 2. 가까운 형제 노드(깊이가 같은 노드) 의 Entry가 1개인 경우(Entr...

AVL Tree의 Insertion, Remove 시 동작 Insertion - 기본적으로 BST의 Insertion 방식을 사용하고, 어떤 노드의 자식 노드들의 height 값의 차가 1보다 커지면 Trinode Restructuring 을 수행한다. 1. Insert된 노드부터 부모 노드를 찾아가면서 균형이 깨진 노드를 찾는다. 2. 찾으면, 현재 경로까지 노드 중 최근 3 가지 노드를 선택한다. ( 밑에서 부터 x, y, z 로 놓는다.) 3. Inorder 순서로 a, b, c 로 놓는다. 총 4가지 경우의 Rotation이 있다. 1) 왼쪽 Single Rotation 트리의 왼쪽에서 b = y -> 트리가 일렬로 있을 때 Y 노드를 잡고 올려주는 모습이다. 그림에는 나오지 않았지만 당연히 Z의 부모 노드는 Y의 부모 노드가 된다. 2) 왼쪽 Double Rotation 트리의 왼쪽에서 b = x -> 트리가 한 번 꺾일 때 X 노드를 잡고 Y 와 Z 사이로 올리는 모습이다. 마찬가지로 Z의 부모 노드가 X의 부모 노드가 된다. 3) 오른쪽 Single Rotation 트리의 오른쪽에서 b = y -> 트리가 일렬로 있을 때 왼쪽일 때에서 In-order의 순서만 바뀌고 거의 유사하다. 4) 오른쪽 Double Rotation 트리의 오른쪽에서 b = x -> 트리가 한 번 꺾일 때 왼쪽일 때에서 In-order의 순서만 바뀌고 거의 유사하다. De letion - Insertion과 마찬가지의 조건에서 Trinode Restructuring을 수행한다. 단, 한 번 수행해도 더 위의 노드가 균형이 깨질 수 있으므로 균형이 깨진 노드를 찾지 못 할 때까지 Restructuring을 수행해야 한다. 1. Delete된 노드부터 부모 노드를 찾아가면서 균형이 깨진 노드를 찾는다. 2. 찾으면, 올라온 반대 방향 으로 3칸 내려간다. ( 밑에서 부터 ...

문제(링크) 세그먼트 트리 레이지 프로퍼게이션 문제였습니다. TF[now] = 현재 구간에서의 왼쪽->오른쪽 방향의 최장 수열 길이 TB[now] = 현재 구간에서의 오른쪽->왼쪽 방향의 최장 수열 길이 c4[now] = 현재 구간의 4의 개수 c7[now] = 현재 구간의 7의 개수 현재 노드의 최장 수열의 길이를 구하려면 max((왼쪽 노드의 최장 수열 길이 + 오른쪽 노드의 7의 개수), (오른쪽 노드의 최장 수열 길이) + (왼쪽 노드의 4의 개수)) 가 됩니다. 왜냐하면 왼쪽에서 최장 수열의 길이를 이미 구했다고 가정하고, 오른쪽에 7의 개수만 세어주면 되는데, 오른쪽에 4가 오는 경우는 두 번째 조건에서 찾게 됩니다. 즉, 오른쪽에 4가 오는 경우는 (오른쪽 노드의 최장 수열 길이)에 포함되어 있습니다. 마찬가지로 오른쪽 최장 수열 길이를 이미 구했다면 왼쪽에 올 수 있는 건 4밖에 없습니다. 위에서 TF를 구했고, TB는 반대로만 해주면 됩니다. 위 방법만을 이용하면 결과는 TF[1](Root) 에 저장되지만, 시간 초과가 나므로 레이지 프로퍼게이션을 적용해야 합니다. 774 777 위 두개를 자식노드로 하고 있다고 가정해 봅시다. 774의 TB는 3입니다. 4->7->7 이므로 774를 뒤집으면, TF는 3이 나옵니다. 4->4->7 이므로 즉, 뒤집은 다음의 TF는 뒤집기 전 TB와 같습니다. 따라서 774777의 TF를 구하려면 (774의 TB + 777의 4의 개수)와 -- 4의 개수? = 4가 뒤집히면 7이 되므로 같은 방식으로 (777의 TB + 774의 7의 개수) 중 큰 값을 구하면 됩니다. 이제 어떤 노드 n 에 대하여 n의 구간을 모두 뒤집을 때 TF의 값을 구할 수 있었습니다. 같은 방식으로 TB도 구할 수 있습니다. 물론 자신의 c4, c7의 개수도 서로 바꿔 줍니다. 지금까지 구한 게 레이지 프로퍼게이션 중 일부인데, 이제 자식...