목록BOJ (45)
이모저모
해결방법1) 알고리즘 실력 기준으로 정렬한다.2) 순서대로 탐색2-1) d만큼 차이나는 위치를 찾는다.2-2) 해당 구간에서의 알고리즘 갯수를 카운팅한다.2-3) 효율성을 구한 뒤 최대 효율성을 구한다.시간 복잡도 O(NK)단순히 구간만큼의 갯수를 카운팅하면 O(N*N*K)가 될것이다.하지만 이미 구해진 구간을 재활용할 수 있다면. 시간복잡도를 줄일 수 있다.구간을 더하는 최대 갯수가 NK, 빼는 최대 갯수가 NK이므로 O(NK)가 나옴 아래는 소스코드이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#d..
트리문제이다. 나의 해결방법은1) 조건에 따라서 dfs를 이용하여 k-1개의 구슬 만큼을 노드에 셋팅한다.2) 또 다시 dfs하여 구슬이 들어갈 위치를 찾으면 그것이 k번째 들어갈 구슬의 위치가 된다. 전체 시간 복잡도는 dfs의 시간복잡도인 O(V+E)가 된다. 아래는 소스코드이다.조금 더 생각하면 dfs하나로 가능하고 코드의 길이도 줄여줄수 있을 것같다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 922..
bit shift를 활용하는 문제이다.복잡도는 O(MN)이며long long type은 1
단순하게 다 찾아보면 되는 문제이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef long long ll;typedef unsigned long long ull;int main () {freopen("sample.txt", "r", stdin);int n,ret = 0;scanf("%d",&..
버블소트의 성질이 이용하는 문제이다. 처음 LIS를 활용하여 길이 x일 때 n-x+1로 구할라고 했으나 반례가 있었던것 같다. 위 문제는 버블소트의 성질인 (원래 위치 - 정렬 후 위치) 값 이 가장 큰 값만큼 수행하면 정렬된다.왜냐하면 문제의 버블소트는 가장 큰 값을 끝부터 차곡차곡 쌓아가므로작은 값은 한번 루프를 돌 때 한칸 씩만 이동하기 때문에 차이가 가장 큰 값만큼 루프를 돌아야한다. 소스코드 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2..
위상 정렬을 이용해당 노드의 최소시작 학기는 선수과목의 최대 시작학기 + 1이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef pair pii;typedef long long ll;typedef unsigned long long ull; int n,m,out[1001],income[1001]..
약수를 구해서 비교만 하면 끝 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef long long ll;typedef unsigned long long ull; int main () {freopen("sample.txt", "r", stdin);int t,n,sum,limit;scanf("%d",..
그냥 진법 변환한 뒤양 끝을 기준으로 회문 여부를 확인한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef long long ll;typedef unsigned long long ull; int main () {freopen("sample.txt", "r", stdin);int i,t,n,r,..
점화식dp[pos][prev step] : 이전 스텝이 pre step 이고 현재 위치가 pos 일때 최대값dp[p][1] = dp[p-1][2] + data[p]dp[p][2] = max(dp[p-2][1], dp[p-2][2]) + data[p]나는 재귀형태로 그냥 풀었다. 소스코드 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#defi..
테두리에 도달하는 최솟값을 찾는 문제이다. 처음 DP를 생각하였으나 생각이 잘 나지 않아서 4방향으로 연결된 그래프 문제로 다이젝스트라를 이용하여 풀었다.(양의 정수 조건이 붙어 있으므로) 테두리에 도달하면 다이젝스트라의 성질에 의해서 그것이 가장 최솟값이므로 그 값을 출력한다. 아래는 소스 코드이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_..