일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- Algospot
- BST
- Dag
- DynamicProgramming
- Cycle detecting
- implementation
- dynamic programming
- BOJ
- bitmask
- 백준
- CS Academy
- mathematics
- graph modeling
- Sieve_of_Eratosthenes
- Euler circuit
- Eulerian circuit
- backtracking
- hashing
- POJ
- GCD
- Shortest path
- disjoint-set
- Segment Tree
- scc
- Eulerian path
- flows
- Greedy
- BFSDFS
- graph
- Euler path
- Today
- Total
그냥 하는 노트와 메모장
[개요] 웹 동적 분석을 진행하는데 분석 시간 이슈가 상당히 많다. 검출할 수 있는 취약점이 많으면 많을수록 그 취약점을 검출하기 위해 시간이 걸리기에 결과적으로 분석 시간이 늘어나게 되는데, 이를 줄이기 위해서 생각한 것이 바로 DOM 유사도 분석이다. DOM 유사도 분석을 통해 비슷한 페이지나 이미 분석이 끝난 부분을 분석에서 제외하여 시간을 줄이자는 게 내 아이디어. 개인적으로 연구를 진행했다. 이 포스팅은 특징 벡터 추출하는데에 집중하며, 이 특징 벡터를 어떻게 굽고 삶느냐에 따라 유사도가 바뀐다. 따라서 이러한 설정은 각자 개인이 판단하시길.. [사전에 고려된 구조] 1. 단순 특징 비교 각 서브 트리에서 특징별로 노드를 나열하여 단순 비교한다. 가령 DOM의 경우 태그 이름별로 각 트리에 몇 ..
소스 코드 위치: Google Kickstart 2021 Round C solutions A. Smaller Strings 1. 주어진 문자열(s)의 넘어가지 않도록 첫 문자부터 건설해나가자. 문자 'a'부터 시작해서 문자 'a'+K-1까지 사용한다. 2. i(단, 0 최적 부분 구조, 겹치는 부분 문제 -> 다이나믹 프로그래밍 1.에서 각 날은 독립적이고, 문제에서 주어진 조건에선 어떤 X가 주어지든 답은 반드시 존재하므로 각 날마다 점수의 기대값을 최대로하면 반드시 X보다 크거나 같은 값이 나온다. 따라서 2. 구조를 파악하여 동적 프로그래밍을 구성한다. dp[i][j][k] = i번 rock을 냈었고, j번 scissor를 냈었고, k번 paper을 낸 상태에서 가질 수 있는 점수의 기대값의 최대값..
※ 알림: 이 글은 트라이(Trie)로 자바 패키지 검색 시스템을 구현하는 것을 목적으로 두고 있습니다. 또 왜 트라이로 검색 시스템을 구축할 수 없는지를 다른 자료구조와 함께 실험을 통해 증명합니다. [사전 지식] 기본적으로 자바 패키지는 디렉토리 구조를 가진다. 실제로 자바 프로젝트를 생성해서 패키지를 생성하면 점(.)를 기준으로 디렉토리가 생성되고 그러한 파일 시스템을 가진다. [상황] 각 패키지와 그 패키지에 속한 클래스들을 관리해야 한다. 이제 위 데이터를 접근하기 위해서는 먼저 정의된 패키지에 접근하여 클래스 객체에 접근할 필요가 있다. 패키지에 접근하려면 가장 적합한 자료구조는 무엇일까? 여기서 크게 세 가지 자료구조를 확인하고 성능을 체크하고자 한다. [후보 1] 파일 시스템처럼 리스트로 ..
BOJ 9015 정사각형 [분류 - 기하, 해싱] [풀이 - 정답] 주어진 좌표의 수는 N개이고 사각형을 만들기 위해서 O(N^4)이 먼저 떠오르지만 시간초과를 면치못하니 보다 효율적인 구현이 필요하다. 정사각형을 만들기 위해서 일단 임의의 두 점을 잡고 다른 두 점을 찾는 방식을 생각해보자. 이 때 임의의 두 점이 이루는 선분은 사각형의 한 변이 되는데, 이러면 만들 수 있는 사각형은 반드시 두 개다. 한 방향만 선택하여 보도록하자. 일단 임의의 두 점을 선택하자. 이 과정은 O(N^2)이다. 이 두 점이 이루는 선분은 만들고자하는 정사각형의 한 변이 된다. 이 두 점을 포함하는 가장 작은 직사각형을 만들면 아래처럼 빨간 영역의 직사각형을 만들 수 있다. 이 빨간색 영역을 90도씩 회전하면 영역 내에 ..
1. for ... in for ... in 구문은 대상 객체 안에 있는 프로퍼티에 하나씩 접근한다. 실제값을 가져오는 것이 아니라 프로퍼티를 가져오기 때문에 실질적으로 유용하진 않다. 일반적으로 반복하는 목적은 값이 대상이지 값을 가리키는 프로퍼티가 대상이 아니다. var customerJson = { "name": "anb", "time": 20210510, "nickname": "annnb", tier: { cook: "bad", song: "bad", lol: "good" } }; for(var property in customerJson) { console.log(`${property} : ${typeof customerJson[property]}`); } // expected output //..
[넓이] 가장 쉬운 삼각형부터 확인해보자. 아래처럼 2차원 좌표계에서 세 점이 삼각형을 이루고 있다고 하자. 우리가 원하는 영역은 D 영역이고 이 영역은 이 삼각형을 포함하고 x축과 y축에 평행하는 가장 작은 직사각형 R에서 A, B, C 영역을 빼면 된다. 삼각형을 감싸는 직사각형 R 특성상 반드시 하나 이상의 꼭지점을 공유한다. 좌표에 따라 R = (x3-x2)*(y1-y2) A = (x1-x2)*(y1-y2)/2 B = (x3-x1)*(y1-y3)/2 C = (x3-x2)*(y3-y2)/2 D = R - A - B - C = (x1y1+x2y3+x3y1-x2y1-x3y2-x1y3)/2 [신발끈 공식] 신발끈 공식은 아래처럼 정의된다. 위 그림처럼 모든 좌표를 세로로 나열하고, 한칸씩 x에서 오른쪽 ..
두 선분이 있을 때 두 선분이 교차하는지는 한 선분을 기준으로 나머지 선분의 끝 각 두 점에 대해서 세 점을 만든 뒤 이 세 점이 이루는 두 선분이 평행 또는 시계, 반시계인지를 판별하여 알 수 있다. 기준 선분과 다른 선분의 점과 관계를 그림으로 나타내면 아래와 같다. 보다시피 교차하는 경우엔 시계 방향이 하나, 반시계 방향이 하나 존재하지만 교차하지 않는 경우엔 둘 다 시계 방향이거나 둘 다 반시계 방향이거나다. 따라서 판별할 때 세 점에 대해서 방향성을 조사할 때 시계 방향과 반시계 방향 하나씩 존재함을 확인하면 된다. 하지만 평행일 경우엔 각별한 주의가 필요하다. 한 선분이 다른 선분을 포함할 수도, 다른 선분의 한 점만 포함할 수도 있기 때문에 기준을 두 선분 모두 둬야한다. 기준 선분에 다른 ..