그냥 하는 노트와 메모장

[개요] 웹 동적 분석을 진행하는데 분석 시간 이슈가 상당히 많다. 검출할 수 있는 취약점이 많으면 많을수록 그 취약점을 검출하기 위해 시간이 걸리기에 결과적으로 분석 시간이 늘어나게 되는데, 이를 줄이기 위해서 생각한 것이 바로 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에서 오른쪽 ..

두 선분이 있을 때 두 선분이 교차하는지는 한 선분을 기준으로 나머지 선분의 끝 각 두 점에 대해서 세 점을 만든 뒤 이 세 점이 이루는 두 선분이 평행 또는 시계, 반시계인지를 판별하여 알 수 있다. 기준 선분과 다른 선분의 점과 관계를 그림으로 나타내면 아래와 같다. 보다시피 교차하는 경우엔 시계 방향이 하나, 반시계 방향이 하나 존재하지만 교차하지 않는 경우엔 둘 다 시계 방향이거나 둘 다 반시계 방향이거나다. 따라서 판별할 때 세 점에 대해서 방향성을 조사할 때 시계 방향과 반시계 방향 하나씩 존재함을 확인하면 된다. 하지만 평행일 경우엔 각별한 주의가 필요하다. 한 선분이 다른 선분을 포함할 수도, 다른 선분의 한 점만 포함할 수도 있기 때문에 기준을 두 선분 모두 둬야한다. 기준 선분에 다른 ..

2차원에서 세 점이 주어졌을 때 이 세 점을 이었을 때 이루는 두 선분의 연결 관계를 평행 그리고 시계, 반시계 방향으로 구분할 수 있다. 단, 두 선분이 존재하기 위해서는 점이 아닌 선으로 있어야하기 때문에 세 점 중 어느 점도 중복되지 않는다는 전제가 필요하다. p1=(x1, y1), p2=(x2, y2), p3=(x3, y3) p1을 시작점으로 두는 세 점 p1, p2, p3가 이룰 수 있는 선분 관계는 아래처럼 정의된다. ※ 이외 세 점이 나올 수 있는 위치에 대해선 뒤 세 가지 경우를 회전 변환하여 똑같이 적용할 수 있기에 따로 작성하지 않았습니다. 판단 방법은 꽤 간단하다. p1과 p2가 이루는 기울기를 A, p2와 p3가 이루는 기울기를 A3라고 할 때 A가 B보다 크다면 볼록, 같다면 평행..

정의는 다음과 같다. 내부 함수가 호출되더라도 외부함수의 지역 변수에 접근할 수 있는 함수의 형태를 클로저(Closure)라고 한다. 실제 구현은 다음처럼 한다. function outerFunction(param1){ var var1 = "ok"; function closure1(){ return var1 + param1; } return closure(); } 위에서 중요한건 outerFunction이 closure1를 호출했다는 사실보단 closure1라는 함수가 내부에 선언되었고, 이 안에 param1이나 var1 등의 outerFunction 컨텍스트에 존재하는 변수에 접근이 가능하단 사실이다. 하지만 외부에서는 closure1에 호출하려고 접근할 수 없다. 이러한 특성때문에 클로저를 특권 함수..

소스 코드 위치: Google Kickstart 2021 Round B A. Increasing Substring 거저 주는 문제.. 이전 값과 비교해서 현재가 크면 이어주고 아니면 끊는다. B. Longest Progression 음? 갑자기 구현이 빡세진 느낌. prefix array, suffix array를 유지하면서 현재 i번째를 바꾸려고 할 경우 i기준 왼쪽과 함께할 것인지 오른쪽과 할 것인지를 결정한다. 이때 양쪽 어디든 합치려고 할 때 그 차이값을 다른 한쪽과 비교하여 이어질 수 있는지도 판단해야 한다. 양끝 처리 때문에 좀 시간이 걸렸던 문제. C. Consecutive Primes Analysis보고 풀었다.. 10^9보다 작은 인접한 두 소수의 차이는 계산할만큼 작다. Prime ga..

소스 코드 위치: Google Kickstart 2019 Round C A. Wiggle Walk A 치고 너무 복잡하게 푼 느낌이 든다.. 행과 열에 대해서 DSU를 따로 관리한다. 다음에 이동하는 위치가 (ny, nx)라면 인접한 4방향에 대해서 이미 방문한 칸이 있다면 merge해준다. 이 때 DSU에서 관리하는 데이터는 left와 right로 두 변수가 있고, 각각 행 또는 열에서 이미 방문한 칸들에 가장 가까운 작은 값과 큰 값을 말한다. 위와 같이 행과 열 각각 DSU를 관리하면서 상하좌우 이동해주면 된다. B. Circuit Board i번째 행 j번째 열을 구성하고자하는 사각형의 우측 하단 꼭지점에 위치한다고 치자. i행만 쓴다면 i행에서 최대값과 최소값의 차이가 K를 넘어서지 않는 좌표가..

소스 코드 위치: Google Kickstart 2019 Round B A. Building Palindromes 쿼리 (L, R) 마다 L과 R 사이에 있는 문자들을 재배열하여 팰린드롬을 만들 수 있는지를 묻는 문제다. 사용되는 문자가 26밖에 없으므로 prefix array를 정의하여 L과 R 사이의 i번째 문자가 출현하는 수가 홀수면 1, 짝수면 0으로 두고 이러한 홀수의 수가 2 이상이면 팰린드롬을 구성할 수 없다고 계산하면 된다. B. Energy Stones [시간] 모든 에너지 스톤을 먹었을 때 가능한 가장 긴 시간은 10000까지다. [Lossless] L이 0인 에너지 스톤은 L이 1 이상인 스톤을 모두 먹고난 뒤 처리하는 것이 이득이다. [Ordering] L > 0인 에너지 스톤만 가..

아쉽다.. 4번 플로우 문젠줄 알고 그래프 그리다가 시간이 끝나버렸다 ㅠ 소스 코드 위치: [Google Kickstart 2021 Round A] A. K-Goodness String 양 끝에서 한 칸씩 이동하면서 같은 문자의 수(c)를 셈한다. 같아야 하는 문자의 수가 정확히 K이어야 함으로 abs(K - c)를 답으로 내면된다. B. L Shaped Plots 2차원의 각 좌표는 L의 꺽이는 위치의 후보가 된다. 모두 순회해봐야 하니 이 과정은 O(N^2)이 걸린다. 동서남북 4방향 0을 만나기 전까지 연속된 1의 길이를 각 방향에 대해 구한다. 이 때 for문을 한 번 더 돌려서 구하지않고 prefix sum을 구해서 계산하도록 한다. 방향이 4방향이니 4개의 prefix sum 배열을 사용한다...

BOJ 10538 빅피처 [분류 - 아호코라식] 풀이) 2차원 문자열 매칭이다. 주어진 hp x wp 크기를 가지는 그림의 행을 패턴으로 보자. 그러면 총 hp개의 패턴이 존재한다. 이 hp개의 패턴을 아호코라식 트라이 A에 저장하자. 각 패턴을 넣을 때 마지막 노드엔 패턴 끝이라는 정보를 행 인덱스로 저장하자. 여기서 이 노드에 행 인덱스가 여러 개 있을 수 있다; 그림에서 i번째 행과 j번째 행이 같다는 소리다. 이건 Union-Find로 합쳐주자. 이후에 '걸작'을 순회하자. '걸작'의 행들을 각각 탐색 대상 문자열로 보자. 행을 순회할 때마다 방문 노드를 A의 루트로 되돌리며, 매칭되는 패턴을 찾는다. i번째 행 j번째 열을 순회할 때 A에서 어떤 패턴을 찾았다면 이 정보를 2차원 배열 row_d..

아호 코라식(Aho-chorasick) 여러 문자열 패턴이 있고, 특정 문자열에 어떤 패턴이 어디에 존재하는지 확인하고 싶을 때 쓰는 알고리즘입니다. 기술적으로는 prefix와 suffix를 가지고 노는 문자열 탐색 알고리즘이라고 말하고 싶네요. KMP도 마찬가지지만 이 알고리즘 역시 매칭 실패했을 때 지금까지 사용한 데이터를 그대로 활용해서 효율적으로 탐색하고 싶어합니다. 아시다시피 그 동작을 실패 함수(Failure function)라고 합니다. [사전 지식] * 트라이(trie) - prefix 문자열을 저장하는 자료구조. 만약 검색 대상 문자열이 패턴과 정확히 일치해야만 한다면 적절한 자료구조입니다. * BFS - 아호코라식 자료구조를 동적으로 건설해나가는데, 여기서 실패함수 구조에 의해 BFS를..