사용 전 배열, vector 오름차순 정렬 필요 1. 직접 구현하기 lower_bound #include using namespace std; #define MAX_N 500000 int n; int arr[MAX_N]; //lower_bound(x) : x보다 같거나 큰 수 중에 가장 왼쪽에 있는 수의 인덱스 int lower_bound(int x) { int left = 0; int right = n - 1; int ret = n; // 같거나 큰 최초의 위치를 찾아야 하므로 최악을 고려해서 n이 초깃값이 되어야 함 while (left = x) { // mid 값이 관심있는 영역이라면 ret = mid; right = mid - 1; //가장 왼쪽에 있는 수의 인덱스를 찾아야 하니깐, 왼쪽 부분을 ..

단절선이란 무방향 그래프에서 해당 간선을 제거했을 때 그래프가 두 개 이상으로 나누어질 때 그 간선을 단절선이라고 합니다. 단절선은 단절점을 구하는 것과 유사합니다. https://seokjin2.tistory.com/87 [알고리즘] 단절점(Articulation Points or Cut Vertices) 단절점이란 무방향 그래프에서 해당 정점을 제거했을 때 그래프가 두 개 이상으로 나누어질 때 그 정점을 단절점이라고 합니다. 먼저 간단하게 생각할 수 있는 방법은 모든 정점에 대해서 정점 seokjin2.tistory.com 정점 A에서 부모 노드를 제외한 자식 노드들이 역방향 간선(backward edge)을 통해서 정점 A에 갈 수 없고 정점 A보다 위에 있는 선조로 갈 수 없으면 정점 A는 단절점..

단절점이란 무방향 그래프에서 해당 정점을 제거했을 때 그래프가 두 개 이상으로 나누어질 때 그 정점을 단절점이라고 합니다. 먼저 간단하게 생각할 수 있는 방법은 모든 정점에 대해서 정점 하나를 삭제해보고 DFS를 돌려서 그래프의 개수를 세보면 됩니다. 이때 시간 복잡도는 정점의 개수를 V, 간선의 개수를 E라고 할 때 O(V * (V + E) )가 됩니다. 그러나 위 방식은 비효율적이고 O(V + E) 시간복잡도로 단절점을 구할 수 있는 방법이 있습니다. 바로 DFS spanning tree를 이용하는 방법입니다. 위와 같은 그래프가 있을 때 DFS spanning tree로 번호를 매겨보겠습니다. DFS spanning tree에서 단절점을 찾는 방법은 정점 A에서 부모 노드를 제외한 자식 노드들이 역..

1차원 배열에서 연속되는 값들을 이용해서 문제를 해결해야할 때 두 개의 포인터를 이용해 원하는 결과를 얻는 알고리즘 대표 문제: https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 위 문제는 배열에서 i ~ j 부분합이 M을 만족하는 모든 경우의 수를 구하는 문제이다. 부분 배열의 시작과 끝을 가리키는 변수 s, e을 준비하고 부분합을 저장할 변수 sum을 준비한다. 다음을 반복한다. while(true) 1. 현재 부분..

에라토스테네스의 체 (시간 복잡도O(N log log N) ) 고대의 그리스 수학자 에라토스테네스에 의하여 개발된 정해진 범위 안의 소수를 찾는 알고리즘 2부터 N까지의 수를 적고 다음을 반복한다. 2부터 시작해 1씩 증가하면서 시작 수가 지워지지 않았다면 시작한 수를 제외하고 그 수의 배수를 모두 지운다. (배수들은 소수가 아니므로 지움) 시작 수를 정할때는 sqrt(N)까지만 보면 됩니다. (N이 소수임을 판별할 때 sqrt(N)까지만 보는 이유와 같음) ( sqrt(N) 소수 판정 알고리즘: https://seokjin2.tistory.com/17) ) 배수를 지울때 시작 수의 제곱인 i*i 시작합니다. 왜냐하면 (2*i), (3*i), .... (i-1)(i)는 각각 2의 배수, 3의 배수, (i..

소수는 1보다 크고 1과 자기 자신으로만 나눠지는 자연수입니다. 자연수 N이 소수임을 판별하는 방법은 2부터 n-1까지의 자연수로 자연수 N을 나눴을 때 나누어 떨어지는지 보면 됩니다. 만약 2부터 n-1까지의 자연수 중에 하나라도 나누어 떨어지면 자연수 N은 소수가 아닙니다. 그런데 이렇데 n-1까지 나누어 보는 방식은 O(N)의 시간 복잡도가 걸립니다. n-1까지 나누어 떨어지는지 다 확인할 필요가 없고 sqrt(N)까지만 나누어 봐도 소수임을 판별할 수 있고 이때 시간 복잡도는 O(sqrt(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 #include using namespace std; bool isPrime(int ..