솔

위상 정렬이란?위상 정렬은 그래프 알고리즘 중 DAG(Directed Acyclic Graph), 즉 방향성이 있으면서 싸이클이 없는 그래프에서 정점들을 순서대로 정렬하는 방법이다.  위상 정렬은 다음과 같은 상황에서 유용하다.- 작업 스케쥴링- 선수 과목에 대한 문제- 데이터 처리 파이프라인 위상 정렬의 조건위상 정렬을 사용하기 위해선 위에서 언급한 것처럼1. edge(간선) 에 방향이 있어야 한다.2. 비순환 그래프 즉, 싸이클이 없어야 한다. 이 두가지 조건을 만족해야 한다. 위상 정렬은 큐 기반 위상 정렬과 dfs 기반 위상 정렬로 나뉜다.두 방식에 대해 각각 알아보자.큐 기반 위상정렬큐 기반 위상정렬은 다음과 같은 단계를 따른다.1.각 정점의 진입 차수(inDegree)를 계산한다.2.진입 차수..

https://www.acmicpc.net/problem/11689  문제자연수 n이 주어졌을 때, 1~n 의 자연수 중 n 과 서로소인 숫자의 개수를 구하는 문제이다. 접근 방법오일러 파이 함수를 이용해야 한다.이는 1부터 n까지의 수 중에서 n과 서로소인 수의 개수를 계산하는 함수이므로 이 문제를 해결하기에 적합하다.따라서, n의 소인수만 찾으면 효율적으로 계산이 가능하다. 오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다.이렇게, 소수를 찾아서 순차적으로 p[i] = p[i] - (p[i]/2) 연산을 반복적으로 수행해주면 최종 결과는 오일러 피 함수의 결괏값이 배열에 남게 된다. 코드#include #include #include #include // 오일러 파이 함수 구현long long ..

https://www.acmicpc.net/problem/1016  문제 정의min 과 max 가 주어졌을 때, 제곱수로 나누어지지 않는 정수의 개수를 찾아야 한다. 예제 입력 1에서 min=1 , max=10 이 주어졌을 떄, 1보다 큰 제곱수(4,9)로 나누어지지 않는 정수의 개수는 1,2,3,5,6,7,10 으로 7개이다.  위 그림과 같이 2부터 제곱수가 max값을 넘기 전까지 제곱수로 나누어지는 수들을 하나씩 제거해주면 된다.  배열 초기화입력받은 min, max 값에 따라 범위를 설정해주고 배열을 초기화한다.long long range = max - min + 1;std::vector is_power(range, false);  제곱수로 나누어지는 수 순차적으로 탐색i^2 형태의 제곱수를 순회..

https://www.acmicpc.net/problem/1931  여러 시간대가 주어지고, 시간이 겹치지 않으면서 가능한 한 많은 회의실 사용 횟수를 구하려고 한다. 이를 구하기 위해서는, 가장 빨리 끝나는 회의를 찾고, 그 이후에 시작하는 회의 중 가장 빨리 끝나는 회의를 찾고, 이렇게 찾아나가면 될 것 같다. 위와 같이 회의 시간을 찾기 위해서는, 끝나는 시간을 기준으로 정렬되어 있어야 한다.  이를 위해 다음과 같은 구조체와 배열을 만들어 주고,이렇게 끝나는 시간을 기준으로 정렬해주는 cmp함수까지 완성해주면 준비는 끝났다.(끝나는 시간이 같은 경우 시작 시간을 기준으로 정렬)bool cmp(const t& a, const t& b) { if (a.eTime != b.eTime) return a..

https://www.acmicpc.net/problem/1300  이 문제를 풀 때 N의 최댓값이 10^5 이므로 이차원 배열(N x N)을 만들어 문제를 풀면 100억의 메모리가 필요하고, 10^10(log(10^10)) 의 시간이 필요한데 사실상 불가능하다.메모리O(N^2)시간O(N^2 log(N^2))  이 문제에서 요구하는 것은 "정렬된 배열에서 k번째로 작은 값"이다. 만약 어떤 값 x를 기준으로 배열(B) 에서 x 이하의 원소가 몇 개인지만 구하면  “x 이하가 k개 이상이면 → B[k]는 x 이하여야 함”“x 이하가 k개 미만이면 → B[k]는 x 보다 커야 함”위와 같은 기준을 얻을 수 있고, 이분탐색을 이용해 원하는 B[k]를 빠르게 구할 수 있다.   문제를 보면 이론상으론1 이지만,..