개발일지

개념 Floyd Warshall (플로이드 와샬) 알고리즘은 정점과 정점 사이의 최단 거리를 구하는 알고리즘이다. 플로이드 와샬 알고리즘의 특징은 모든 정점 사이의 거리를 구할 수 있다. 최단 경로를 찾을 때 중간에 한번 거쳐서 가는 경로 중 가장 가까운 경로로 업데이트 하면서 모든 정검들의 최단 거리를 구하는 알고리즘이다. 시간 복잡도가 O(V^3)이라는 꽤 오래 걸리는 알고리즘 이지만 모든 정점 사이의 최단 거리를 구할 수 있다. 작동원리 1. 중간 정점 K, 시작 정점 I, 도착 정점 J로 삼중 반복문을 순회한다. 2. distance[i][j]가 distance[i][k] + distance[k][j]보다 크면 경로를 업데이트 한다. -> distance[i][k], distance[k][j]가 ..

개념 LIS(Longest Increasing Subsequence)는 배열이 있을 때 일부 원소를 고른 부분 순열 중, 각 원소가 이전 원소보다 크고 그 순열의 길이가 가장 큰 순열을 LIS라 하고 최장 증가 부분 순열이라고 한다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 변형 문제로 LDS, 최장 감소 부분 순열이 있다. 작동원리 1. LIS라는 List를 만든다. 2. List가 EMPTY거나 제일 마지막 원소가 검사하는 원소보다 작은 경우 List뒤에 추가한다. 3. 검사하는 원소가 List 마지막 원소보다 작은 경우 lower_bound를 사용하여 찾은..

개념 충족 가능성 문제 중 하나로써 아래와 같은 형태를 2-SAT 문제라 한다. * 충족 가능성 문제 : Boolean으로 이루어진 식이 있을 때 해당 식이 True인 경우를 찾는 문제 f=(¬x1∨x2)∧(¬x2∨x3)∧(x1∨x3)∧(x3∨x2) 인 경우에 f를 true로 만드는 경우 ¬ : NOT ∨ : OR ∧ : AND 괄호 안의 OR 연산으로 이루어진 것을 절(Clause)이라고 표현하고 AND와 절로 이루어진 식을 CNF(Conjunctive Normal Form)라고 한다. 각 절의 변수의 개수가 2개면 2-SAT이라 하고 N개면 N-SAT이라고 한다. 2개 같은 경우 SCC 알고리즘을 사용하여 쉽게 해결할 수 있지만, 3개 이상의 SAT 문제에서는 NP-Hard 문제이다. 작동원리 1. ..

개념 파란점에서 빨간점까지 탐색한다고 생각할 때 파란점 기준으로 탐색하면 초록색 영역만큼 탐색해야한다. 하지만 파란점과 빨간점을 기준으로 만나는 노란색 점을 탐색하면 탐색해야 하는 불필요한 영역이 줄어든다. 이처럼 기준을 바꿔서 다르게 생각하면 좀 더 연산을 줄일 수 있다. 문제 https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net 코드 #include using namespace std; int n, c; vector input; vector..

개념 CCW 알고리즘을 이용하여 두 선분이 교차하는지 판별할 수 있다. 작동원리 위 예시를 보면 CCW(A, B, C)와 CCW(A, B, D)가 반대방향(곱이 음수)이면 두 선분은 교차한다고 볼 수 있다. 하지만 위 예시와 같은 반례가 존재한다. (직선이 아닌 선분이기 때문에 CCW의 방향이 반대여도 교차하지 않을 경우가 있다.) 그렇기 때문에 CCW(A, B, C)와 CCW(A, B, D)의 방향, CCW(C, D, A)와 CCW(C, D, B)의 방향 두 번을 검사하여 교차하는지 확인할 수 있다. 하지만 두 선분이 같은 직선에 있을 경우 CCW가 0이 나온다. 위와 같은 반례는 CCW(A, B, C) * CCW(A, B, D) == 0 && CCW(C, D, A) * CCW(C, D, B) == 0..

개념 유한 집합의 합집합의 원소의 개수를 세는 기법이다. 작동원리 즉 겹치는 부분이 홀수면 더하고, 겹치는 부분이 짝수이면 뺀다. 시간복잡도 집합의 갯수가 N일 때 O(2^N) 문제 www.acmicpc.net/problem/17436 17436번: 소수의 배수 첫째 줄에 N(1 ≤ N ≤ 10)과 M(1 ≤ M ≤ 1012)이 주어진다. 둘째 줄에는 N개의 소수가 주어진다. 입력으로 주어지는 소수는 100보다 작거나 같으며, 같은 소수가 두 번 이상 주어지지 않는다. www.acmicpc.net 코드 #include using namespace std; using Int = int; using Long = long long; int main() { ios::sync_with_stdio(false); c..

개념 오일러의 피 함수는 N이 주어 졌을 때 1 ~ N의 숫자중 N과 서로소인 숫자의 개수를 찾는 함수이다. 작동원리 1. p가 소수인 경우 소수인 경우 약수가 1과 자기 자신밖에 없으므로 자기 자신을 제외한 모든 수와 서로소이다. 2. 소수 p의 거듭제곱인 경우 소수 p의 거듭제곱과 서로소가 아닌 경우는 p의 배수일 경우이다. 즉 p, 2p, 3p .... p^(k-1) * p => p^k - p^(k-1)이다. 3. n과 m이 서로소인 경우 n과의 서로소의 곱과 m과 서로소의 곱은 n*m과 서로소이다. 결론 n을 소인수 분해했을 때 p1^a1 * p2^a2 * p3^a3 ... pn^an꼴이 나오면 다음이 성립한다. 문제 www.acmicpc.net/problem/11689 11689번: GCD(n,..

개념 위 그림은 911, 91125, 97625 저장했을 때 트리의 예시이다. 트라이는 문자열을 효율적으로 관리하기 위한 트리구조이다. 접두사를 노드에 하나씩 저장하고 접두사를 제외한 문자열을 자식 노드에 저장하는 트리구조이다. (접두사를 저장한다고 해서 Prefix Tree라고도 불림) 작동원리 문자열의 앞부터 차근차근 트리를 탐색하여 문자를 찾기 때문에 검색 속도는 빠르지만 각 노드별로 모든 문자를 저장할 배열이 필요하기 때문에 메모리가 많이 든다. * 메모리 크기 : 포인터 크기 * 배열의 길이(저장하는 문자의 수) * 총 노드의 개수 시간 복잡도 저장 : O(L) 검색 : O(L) 문제 www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 ..