그냥 하는 노트와 메모장

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..