그냥 하는 노트와 메모장

[넓이] 가장 쉬운 삼각형부터 확인해보자. 아래처럼 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보다 크다면 볼록, 같다면 평행..

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

* 강한 연결 요소(SCC, Strongly connected components) - 코사라주(kosaraju)와 타잔(tajan) 알고리즘 이전에 SCC에 포스팅한 적이 있어요. 그 때는 코사라주 알고리즘에 대해서 공부한 적이 없었는데 이번에 CLRS 공부하면서 알게 됐습니다. 또 이 코사라주로부터 타잔 알고리즘을 더 쉽게 이해할 수 있게 되서 제가 이해한 방식으로 포스팅하려고 따로 글 올려봅니다. 먼저 코사라주 알고리즘부터 보겠습니다. * 코사라주 알고리즘 - 알고리즘 순서 1. DFS 한 번 돌며 모든 자식을 다 돌았음을 알리는 종료 시점 f[]를 저장한다. 2. G=(V, E)에 대해 transpose of G = G^T = {(v, u) | (u, v) in G}를 정의한다. 3. G^T에 대..

* 베주의 항등식, 확장 유클리드 알고리즘 [해당 포스팅은 두 정수의 최대 공약수를 구하는 유클리드 알고리즘 지식을 요구합니다.] 확장 유클리드 알고리즘을 설명하기 앞서 베주의 항등식을 통해 확장 유클리드 알고리즘의 (x, y) 해가 반드시 존재함을 보고 넘어가겠습니다. * 베주의 항등식 확장 유클리드 수식과 완전히 동일합니다만, 여기선 (x, y) 해가 반드시 존재함에 포커싱을 두고 있다는 점을 다시 인지하며 명제를 봐봅시다. 0이 아닌 정수 a, b에 대해 d를 a와 b의 최대 공약수라고 하면 수식을 만족하는 해 (x, y)는 반드시 존재한다. 특히 a와 b가 서로소이고 d=1이라면 베주의 항등식에 의해 정수해가 반드시 존재해야 합니다. * 계산 방식 먼저 유클리드 알고리즘을 이용하여 해를 어떻게 구..

* 오일러 피 함수(Euler phi function, ) 서로소 개수를 파악할 때 포함-배제의 원칙을 사용해도 되지만, 더욱 간단한 방법이 있습니다. 바로 오일러 피 함수의 특징을 이용하는 것입니다. 오일러 피 함수의 정의는 다음과 같습니다. =n보다 작으면서 n과 서로소인 수의 개수 * 성질 명제 1) 오일러 피 함수는 곱셈적 함수(Multiplicative function)이다. 즉 gcd(m, n)=1이면 이다. 증명) m X n 테이블이 있다고 해봅시다. 1부터 nm까지 수로 테이블을 열 순서로 채워서 아래처럼 만들어봅시다. 이 테이블에서 r행에 있는 모든 원소를 가져오면 다음과 같은 형태를 띄게됩니다. d=gcd(r, m)이라고 정의한다면 두 가지 경우가 나옵니다. 1. d > 1 d > 1인..

* 페르마의 소정리 다른 이론의 근간 또는 여러 암호학 수학의 기반이 되는 매우 중요한 이론이라 함 알아봤는데, little theorem이라곤 하는데 다방면에 쓰이는 걸 보니 작은 정리이긴한데 매우 큰(?) 개념임을 알 수 있었습니다.. 단 이 포스팅에선 증명을 포함하지 않았습니다. 오일러 정리라던지 다른 개념을 알아야 하기에 나중에 포스팅할 숙제로 남겨놓겠습니다.. 페르마 소정리의 기본 명제는 다음과 같습니다.p가 소수이다. ^ a와 p는 서로소이다. -> 여기서 파생되는 명제 중 하나는 아래와 같습니다. 즉 a의 곰셈 역원는 이다. 이 명제는 modularity에서 수에 대한 매우 큰 승수를 구할 때 사용할 수 있습니다. 보조 정리 1) p와 서로소인 모든 a에 대해 인 1

* 마스터 정리(Master theorem) 마스터 정리는 일반적으로 재귀적으로 호출되는 함수에 대해 시간 복잡도를 알고 싶을 때 사용합니다. 단순 for문 중첩으로는 알 수 없는 것들을 계산해야 하는 경우가 있기 마련이죠. 종만북에서도 다이나믹 프로그래밍 구현을 재귀 형식으로 아주 쉽게 구현, 문제에 접근할 수 있도록 해준답니다. 하지만 시간 복잡도를 계산하지 않고 재귀로 짜다보니 시간초과가 날 것만 같은 것을 증명하지 못하고 코드로 짠 다음 시간 초과를 받고서야 깨닫는 경우가 있어서 정리해봤습니다. 시간 복잡도를 계산하기 위해서는 세 가지 방식이 있는데요.1. 치환법2. 재귀 트리3. 마스터 정리(또는 확장 마스터 정리) 치환법은 점화식을 보고, 직관적으로 점화식 형태를 도출해내고 그것을 증명하는 방..

* n번째 문자열에서 k번째 문자 찾아가기 튜토리얼 이따금씩 n번째 문자열에 대해 n-1번째 또는 그 이전의 문자열과의 관계가 주어지고, n번째 문자열의 k번째 문자를 출력하라는 문제가 등장합니다. 가령 1번째 문자열 = "ffx" n번째 문자열 = "abcde" + n-1번째 문자열 + "fghijk" + n-1번째 문자열 처럼 점화식이 있는 상태에서 n번째 문자열의 k번째 문자를 출력하라는 겁니다. 보통 이런 문제는 실제 n번째 문자열을 직접 구성해서 거기서 k번째를 가져오도록 못하게 메모리 또는 시간제한을 둡니다. 즉, 문제를 접근했을 때 직관적으로 떠오르는 풀이는 틀리게 문제를 구성한다는 거죠. 따라서 문자열을 빌드업하며 계산하는 방식은 사용할 수 없습니다. 문제) 베이스 : = "abc" 점화식..

이진 탐색 트리(BST)[ Introduction to Algorithm Chap 12 연습문제 풀이 ] Section 1)12.1-1) 이진 검색 트리 조건을 만족하도록 아무거나 만들면 된다. 12.1-2) 이진 탐색 트리는 현재 노드에 대해 왼쪽 서브 트리보단 크거나 같고, 오른쪽 서브 트리보단 작거나 같다는 것으 보장하지만, 최소힙은 모든 자식 중에서 가장 작은 값만을 보장한다(왼쪽 오른쪽 구분이 없다). 따라서 정렬된 데이터를 얻고 싶을 경우, 최소힙은 선형 시간을 가진다고 보장할 수 없다. 12.1-3) [ TODO ] 12.1-4) PREORDER-TREE-WALK(x) if x != NIL print(x) PREORDER-TREE-WALK(x.left) PREORDER-TREE-WALK(x...

* 이진 탐색 트리(BST, Binary search tree) 이진 트리에서 사용할 수 있는 이진 탐색 트리 개념과 단점 그리고 그 개선안에 대해 작성하고자 한다. - 이진 탐색 트리에서 사용하는 구조체에 쓰이는 데이터는 아래와 같다. 1. left - 왼쪽 자식 포인터. left.key = key를 만족한다. 3. key - 비교 대상 데이터. 4. satellite data - 부속 데이터. 5. p - 부모 노드 포인터. - 정렬된 데이터 얻기 1. y가 x의 왼쪽 서브 트리의 한 노드라면 y.key = x.key를 만족한다. 따라서 중위 순회 결과(Inorder)는 정렬된 데이터를 얻을 수 있음을 알 수 있다. * 기능1. 검색 딱 맞는 키가 있거나 그 값이 NIL이면 해당 노드 포인터를 반환한..

* Bellman-ford algorithm(벨만 포드) - 단일 출발점 최단 경로 알고리즘 흔히 다익스트라와 비교되며, 다익스트라는 음의 사이클을 판단할 수 없지만, 벨만 포드는 완화(Relax) 절차를 이용하여 음의 사이클을 감지하여 최단경로가 존재할 수 없음을 알아낼 수 있다. 따라서 PS에서 음의 사이클이 존재할 가능성이 있고 단일 출발점 최단 경로를 구해야 한다면 다익스트라가 아니라 벨만 포드를 사용해야 한다. * 수식 표현 1. 델타(u, v) : u에서 시작해서 v까지의 최단 경로 길이 2. : v0에서 vk로 가는 방문 정점을 담은 경로 3. v.d : 단일 출발점 s에서 시작해서 v까지의 계산된 경로의 길이 * 완화(Relax) 특징 1. 삼각 부등식 임의의 간선 (u, v) ㅌ E에 대..

* 강한 연결 요소(SCC, Strongly connected components) 문제들 Topological sort, dynamic programming, DSU 등 다양한 알고리즘과 연결하여 풀 수 있는 문제들을 Random하게 소개해 보겠당. 1. 백준 온라인 저지 1-1. Strongly connected component(https://www.acmicpc.net/problem/2150) 기본적인 SCC 문제다. 모든 SCC를 저장하고 이를 정렬하여 출력하면 된다. - 코드 #include #include #include #include using namespace std; int min_v(int a, int b) { return a < b ? a : b; } vector adj; int ..

* 강한 연결 요소 (SCC, Strongly connected components) 방향 그래프 상에서 두 정점 u와 v에 대해 양 방향으로 가는 경로가 모두 있을 때 두 정점은 같은 SCC에 있다고 말한다. if vertex u has paths to vertex v and also v has paths to u, either u and v are involved in same SCC. 이 SCC 집합은 하나의 component 내에 여러개가 생길 수 있다. 아래 그림을 보면 하나의 component에 대해 3개의 SCC가 있음을 직관적으로 알 수 있다. SCC의 특성 중 하나는 SSC 간의 방향 그래프를 그려보면 DAG가 나온다는 것이다. 이는 연역적으로 정리가 가능하다. 1. 현재 구성할 수 있는..