본문 바로가기

분류 전체보기204

[백준] 2150번: Strongly Connected Component (코사라주 알고리즘) | C++ 2150번: Strongly Connected Component첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정www.acmicpc.net 정답코드이론 공부한 거로 직접 구현해서 최적화된 코드가 아닐 수도 있습니다. 1. 정방향 그래프와 역방향 그래프 입력 받기 2. 첫 번째 정방향 DFS 수행 3. 노드 리스트 얻음 4. 두 번째 역방향 DFS 수행 5. SCC 출력 #include #include #include #include #include #define MAX 10001 #define fse(A,B,C) for(int i.. 2023. 6. 4.
[알고리즘] 강한 연결 요소 Strongly Connected Component | 코사라주 알고리즘, 타잔 알고리즘 강한 결합 방향 그래프의 모든 노드에서 다른 모든 노드로 가는 경로가 있는 경우, 이 그래프가 강하게 연결되어 있다고 한다. [1,2,5], [3,4,8], [6,7]이 강하게 결합된 컴포넌트(이하 SCC)이다. 1에서 출발해 2, 5에 도달할 수 있고, 2에서 출발해도 1, 5에 도착할 수 있고, 5에서 출발해도 1, 2에 도달할 수 있다. 하지만 강결합되지 않은 1과 3을 보자. 1에서 출발하면 3에 도달할 수 있다. 하지만 3에서 출발하면 1에 갈 수 없다. SCC를 찾는 알고리즘 SCC를 구하는 알고리즘은 크게 두 가지가 있다. 코사라주 알고리즘 강결합 컴포넌트를 찾는 유용한 방법이다.이 알고리즘에선 두 번의 DFS를 거친다. 첫 번째 탐색에서 그래프에 따라 노드 리스트를 만들고, 두 번째 탐색에.. 2023. 6. 3.
2. 최근 진행 상황 그동안 글은 안 썼지만 잘 되어가고 있었습니다. 1. 하드웨어 관련 실제 동작하는 데모까진 개발하고 싶어 하드웨어 내가 책임지고 하겠다 주장해서 개발하기로 했다. 하드웨어 부품 신청까지 완료한 상황이다. 라즈베리파이를 사용하려고 했는데 os까지 다룰 필요는 없어보여 아두이노로 진행한다. 하드웨어는 아주 가볍게 개발할 것이다. 2. 알고리즘 설계가 잡혀가고 있다. 프로젝트를 시작하기 전엔 단순하게 사용량이 줄면 위험하다 판단하면 되겠다! 라고 생각했는데, 파고 들수록 제약 조건이 많았다. 전화, 전력, 수도, 가스 데이터를 하루에 몇 번 입력받느냐, 어떤 정보를 입력받느냐, 어떻게 조건을 매치시킬 것이냐, 외출 또는 그냥(?)의 이유로 사용량이 확 줄게 되면 어떻게 처리할 것이냐, 지역마다 사용량 차이는 .. 2023. 6. 2.
[기하] 스윕 라인 알고리즘(교차점, 가까운 점, 볼록껍질) | 모르면 절대 못 품 먼저 2차원 거리 측정 함수로 맨해튼거리(택시거리), 유클리드 거리 두 가지가 있다는 것을 알아두자. 교차점의 개수 세기선분이 N개 있을 때, 교차점의 개수를 세는 문제이다. 이때 각각의 선분은 수평 선분이거나 수직 선분이다. O(N^2)으로 쉽게 풀 수 있지만 스윕 라인 알고리즘과 구간 질의 자료 구조를 사용하면 O(NlogN) 시간에 풀 수 있다. 선분이 시작하는 점과 끝나는 점을 가지고 이벤트 처리하는 것이라고 생각하면 된다. 가장 가까운 점 쌍 찾기점 N개가 있을 때 유클리드 거리가 최소인 두 점을 찾는 문제이다. 이 문제도 스윕 라인 알고리즘으로 O(NlogN) 시간에 해결할 수 있다. 점들을 왼쪽에서 오른쪽 순서로 살펴보면서 d라는 값을 관리해 나간다.d는 현재까지 구한 두 점 사이의 최소 거.. 2023. 6. 2.
[알고리즘] 고오급 알고리즘 키워드 *블로그 주인만 알아볼 수 있음 주의* 삼진탐색으로 최솟값 찾기 함수의 최솟값이 x구간 [a,d] 구간 안에 있다고 하자. 구간을 같은 길이 [a,b], [b,c], [c,d]로 나누고 f(b)>f(c)가 성립함을 보인다. (미분) 합 최소화 abs(a1-x)+abs(a2-x)+ ... +abs(an-x) 의 최솟값으로 만드는 x의 최적해는 중앙값이다. 배열 원소가 짝수개라면 두 중앙값 사이 모든 값이 최적해가 된다. 트리의 지름 임의의 노드 a 선택, a에서 가장 먼 노드 b, b에서 가장 먼 노드 c를 구하면 b-c가 트리의 지름 트리 k번째 조상 찾기 ancestor(n,k) : n번 노드의 k번째 부모 가장 쉬운 방법은 k번 거슬러 올라가는 것인데 비효율적이다. k가 2의 거듭제곱인 모든 경우에 .. 2023. 6. 1.
[기하] C++의 복소수 클래스 complex 기하 문제를 풀 때 c++의 복소수 클래스 complex를 사용할 수 있다. 이 클래스를 이용하면 점과 벡터를 복소수 형태로 표현할 수 있고, 클래스의 기능을 이용하여 점과 벡터를 다룰 수도 있다. typedef long long C; // 정수 좌표를 써도 되는 경우 // typedef long double C; // 정수 좌표를 쓸 수 없는 경우 typedef complex P; #define X real() #define Y imag() 정수 계산이 정확하기 때문에 정수좌표를 사용하는 것을 권장한다. 함수 complex 클래스에는 기하 문제를 풀 때 활용할 수 있는 함수를 제공한다. long double 자료형임을 주의하자. abs(v) 벡터 v={x, y}의 길이를 계산하는 함수이다. sqrt(x.. 2023. 6. 1.
[기하] 벡터와 외적의 활용 외적 기하문제에서 요긴하게 사용되는 외적을 이용해 알고리즘을 공부하자. 외적 배운 지 까마득 하지만.....🤣 우선 두 벡터의 외적 값 자체의 해석을 알아보자. 1. a x b > 0 : b는 왼쪽으로 회전한다. 2. a x b = 0 : b는 회전하지 않는다 또는 180도 회전한다 (a와 b가 평행하다.) 3. a x b < 0 : b는 오른쪽으로 회전한다. 점의 위치 판별하기 외적을 이용하면 어떤 점이 직선의 왼쪽 혹은 오른쪽 중 어느 곳에 있는지를 판별할 수 있다. 직선이 두 점 a, b를 지난다고 가정하자. 이때 방향이 a, b를 향하고 있고, 주어진 점은 p라고 하자. (p - a) X (p - b)를 구하면 p의 위치를 알 수 있다. 외적이 양수라면 p가 선분 왼쪽에 있는 것이고, 외적이 음수.. 2023. 5. 31.
[알고리즘] 분할정복으로 거듭제곱 최적화하기 프로그래밍에서 거듭제곱을 구하는 방법은 크게 세 가지이다. pow 내장함수 사용하기 double 실수 자료형을 사용해 거듭제곱을 반환하는 방법이다. 하지만 지수가 매우 클 때 정확성의 문제가 발생한다. 그 문제는 아래 글에서 확인 가능하다. C++ 기준 pow에 관한 글이다. 2023.04.30 - [TIL] - [C++] pow함수 double 형의 정확성 문제 [C++] pow함수 double 형의 정확성 문제 https://www.acmicpc.net/problem/1740 1740번: 거듭제곱 3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다. 이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 oozoowos.tis.. 2023. 5. 30.

티스토리툴바