Study (16) 썸네일형 리스트형 SCC 구하기 개요 SCC(강결합 컴포넌트)란 Strongly Connected Component의 약자로, 방향 그래프에서 서로 연결되어 있는 정점들의 집합을 의미합니다. 여기서 말하는 연결은 같은 집합 내 모든 정점들이 서로를 방문할 수 있는 상태를 의미합니다. 영문 위키피디아의 그림을 참고해보면 쉽게 이해할 수 있습니다. 아래 그림을 보면 { a, b, e }는 하나의 집합으로 묶여 있으며, 각각의 정점에서는 같은 집합에 포함된 정점으로 방문할 수 있습니다. 이렇게 방향 그래프을 서브 그래프로 나눈 것을 의미합니다. 그럼 SCC는 어디에 사용할 수 있을까요? SCC를 활용하여 그래프를 서브 그래프로 나누면 우리는 SCC를 정점으로 하는 DAG(Directed Acyclic Graph)를 만들 수 있으며, 이 과정.. 람다식을 활용한 중첩 반복문 탈출( BOJ 20410 ) 참고 : https://gall.dcinside.com/mgallery/board/view/?id=ps&no=24138&exception_mode=recommend&page=1 중첩 for문 탈출시 람다 함수 활용하는 예시코드 - PS 마이너 갤러리 문제를 풀다보면 위와 같은 코드를 작성할 일이 종종 생기는데 매 for문 마다 덕지덕지 탈출 조건 달아주는것이 꽤나 지저분함 이게 3중 이상의 for문이면 아주 짜증나게 됨 이걸 goto문을 사용하 gall.dcinside.com 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include int M, Seed, X1, X2; int xx1, xx2, a, b; int mai.. 모듈로 곱셈 역원_팩토리얼 계산( BOJ 13977 ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #include #include #define NMAX 4000001 #define MOD 1000000007 using namespace std; typedef long long int lint; typedef pair PAIR; int M, N, K; lint ret; lint fac[NMAX]; lint gcd(lint a, lint b) { if(a == 0) return b; else if(b == 0) return a; else return gc.. 정렬 시간 비교 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 #include #include #include #include #define SWAP(a,b,t)(t=a,a=b,b=t) using namespace std; vector i.. 소수 판별법(밀러-라빈 소수판별법) 알고리즘 설명 연습 문제 : https://www.acmicpc.net/problem/5615 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include #define NMAX 7 #define lint uns.. 순열 알고리즘 [ 알고리즘 ] 1. 배열 P에서 P[X] < P[X+1]을 만족하는 가장 큰 인덱스 값 X 구하기 ( 만약 X가 없다면 탐색 종료 ) 2. 배열에서 P[X] < P[Y]를 만족하는 가장 큰 인덱스 값 Y 구하기 3. P[X]와 P[Y]의 값 교환하기 4. P[X+1] ~ P[N]까지의 값 뒤집기 [ 소스코드 ] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 boolean nextOrder() { int x, y; // 1. Find largest x such that P[x] Manacher's Algorithm 일반적으로 문자열 속에서 팰린드롬(회문)을 찾는 알고리즘은 다음과 같이 O(n2)의 시간복잡도를 가지고 있습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include #define NMAX 35 int len, cnt; char inp[NMAX]; bool check(int l, int r) { while(l> 자신이 속한 팰린드롬 안에서 대칭점이 가진 팰린드롬의 반지름 구하기 if(i =0 and i+m[i]+1 Fenwick Tree( BIT ) 펜윅 트리 개요 펜윅트리 갱신 1 2 3 4 5 6 7 void update(int pos, int val) { while(pos 1 2 3 4 5 6 7 8 9 10 11 12 void update(int x, int y, int val) { int pos; // 2D Fenwick Tree while(x0) { ret += BIT[pos]; pos -= (pos & -pos); } } cs 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int search(int x, int y) { int pos, ret; // 2D Fenwick Tree ret = 0; while(x>0) { pos = y; while(pos>0) { ret += .. 이전 1 2 다음
