알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/30802 나누기와 나머지 연산을 통해서, 티셔츠와 펜의 필요한 개수를 구하는 문제입니다.  자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;long long N;long long shirt[7];long long T, P;long long Tshirt;int main() { cin.tie(0); cout.tie(0); cin >> N; for(int i = 1; i > shirt[i]; cin >> T >> P; for(int i = 1; i ..

문제 링크입니다. https://www.acmicpc.net/problem/14268 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N, M;long long Tree[100001 * 4];long long left_tree[100001 * 4], right_tree[100001 * 4];long long lazy[100001 * 4];vector connect[100001];void make_order(int node, int &cnt){ left_tree[node] = ++cnt; for(int i = 0;..

문제 링크입니다. https://www.acmicpc.net/problem/14245  해당 문제를 풀기 위해선 XOR의 기본적인 특징을 하나 알아야합니다. 예를 들어, 10011 ^ 11100을 한다면 01111이 나옵니다. 이때, 11100을 다시 XOR을 한다면 01111 ^ 11100 = 10011이 됨으로 다시 원래대로 돌아옴을 알 수 있습니다.->  "같은 수를 짝수번 XOR 한다면, 원상태로 돌아온다"가 됩니다. 그러므로, 구간의 값을 가진 트리에 XOR을 한다면 구간의 길이를 통해서 XOR 여부를 확인해주면 됩니다. 쿼리의 개수가 크니, 느리게 갱신되는 세그먼트 트리를 사용하고, 이때 사용되는 lazy 배열에 해줘야하는 XOR 값을 계속 XOR 해주면, 0 또는 XOR 값으로만 남아 있을 ..

문제 링크입니다. https://www.acmicpc.net/problem/12844  해당 문제를 풀기 위해선 XOR의 기본적인 특징을 하나 알아야합니다. 예를 들어, 10011 ^ 11100을 한다면 01111이 나옵니다. 이때, 11100을 다시 XOR을 한다면 01111 ^ 11100 = 10011이 됨으로 다시 원래대로 돌아옴을 알 수 있습니다.->  "같은 수를 짝수번 XOR 한다면, 원상태로 돌아온다"가 됩니다. 그러므로, 구간의 값을 가진 트리에 XOR을 한다면 구간의 길이를 통해서 XOR 여부를 확인해주면 됩니다. 쿼리의 개수가 크니, 느리게 갱신되는 세그먼트 트리를 사용하고, 이때 사용되는 lazy 배열에 해줘야하는 XOR 값을 계속 XOR 해주면, 0 또는 XOR 값으로만 남아 있을 ..

문제 링크입니다. https://www.acmicpc.net/problem/1395 느리게 갱신되는 세그먼트 트리를 이용한 문제입니다.  처리할 일의 개수가 10^5이기에 모든 경우를 계속 갱신한다면 시간 초과가 생길 것입니다.따라서, 바꾸는 정보를 기억해 놨다가 나중에 바꿔주는 느리게 갱신되는 방법을 사용해야 합니다. 단체로 바꿨을 때, 켜지는 전구의 수는 '해당 구간 전체 전구 수 - 현재 켜진 전구 수' 입니다. lazy 배열의 값이 홀수일 때만, 전구의 상태를 바꿔주면 된다는 것을 유의해주면 됩니다.   자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #inclu..

문제 링크입니다. https://www.acmicpc.net/problem/16975 느리게 갱신되는 세그먼트 트리를 이용한 문제입니다. 주어지는 쿼리의 수가 많기에 일반적으로 값을 바꾸는 세그먼트 트리를 사용한다면 시간초과가 생길 가능성이 높습니다.따라서, 느리게 갱신되는 세그먼트 트리를 이용해 주시면 됩니다.   자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N, M;long long Index[100001];long long Tree[100001 * 4];long long lazy[100001 * 4];l..

문제 링크입니다. https://www.acmicpc.net/problem/1849 이분 탐색을 이용한 세그먼트 트리 문제입니다.  자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N;int Tree[100001 * 4];int remake[100001 * 4];int Rank[100001 * 4];int ans[100001 * 4];void make_tree(int node, int st, int fin){ if(st == fin) { Tree[node] = 1; return; } int left = nod..

문제 링크입니다. https://www.acmicpc.net/problem/10999 느리게 갱신되는 세그먼트 트리를 이용한 문제입니다.느리게 갱신되는 세그먼트 트리는 해당 링크를 참조해주세요. https://www.acmicpc.net/blog/view/26 느리게 갱신되는 세그먼트 트리를 사용할 수 있다면 바로 구할 수 있는 문제였습니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N, M, K;long long Index[1000001];vector Tree;vector lazy;long long se..

문제 링크입니다. https://www.acmicpc.net/problem/2465 세그먼트 트리를 이용한 문제입니다. 수열이 하나 주어지고, 해당 수열에서의 키 순서가 주어질 때, 키 순서에 맞는 수열을 찾는 문제입니다. 먼저, 자신보다 키가 작거나 같은 학생을 알기 위해서 오름차순 정렬을 해줍니다. 오름차순 정렬을 해줬으면, 자신이 어디에 들어가야 할지를 뒤에서부터 확인을 해줍니다.(키 순서가 0 1 0 0 3 2 6 7 4 6 9 4 이니 4에서부터 채워줍니다.) 뒤에서 부터 채우는 이유는 앞에서 부터 채울 경우 0을 채워야 하는데, 해당 값이 정확하지 않기 때문입니다.반대로 뒤에서 부터 채울 경우, 값이 0이 아닌 것부터 채우기 때문에 어떤 값을 먼저 채워야할지 명확해지기 때문입니다. 어떤 값이 ..

문제 링크입니다. https://www.acmicpc.net/problem/13711 두개의 수열이 주어졌을 때, LCS를 구하는 문제입니다.  두개의 수열이 주어졌을 때, 두 수열의 최장 공통 부분 수열을 구하는 문제입니다.N의 값이 10^5이기에 반복문을 통해서 전부  확인해본다면 시간 초과가 생깁니다. 문제를 봤을 때, 각 수열은 1부터 N까지 숫자가 1개씩만으로 주어진다는 것을 알 수 있습니다.그렇다면, 하나의 문자열을 기준으로 잡고, 다른 문자열의 숫자가 몇번 째로 나오는지를 저장만 해준다면,이는 가장 긴 증가하는 부분 수열의 문제로 바뀐다는 것을 알 수 있습니다. 예를 들어보겠습니다.문자열 1 : 1 2 4 7 8 9 6 3 5문자열 2 : 2 4 6 8 1 3 5 7 9-> 해당 수열의 LC..

문제 링크입니다. https://www.acmicpc.net/problem/31854 어떤 알고리즘을 사용해야 되는지 파악하는 하는게 중요한 문제입니다. 각 좌표들의 부등호가 주어질 때, 이를 통해서 올바른 퍼즐을 구하는 문제입니다. (X, Y)  좌표와 (X, Y + 1), (X + 1, Y)의 관계가 주어지는데, 이때 어느 쪽이 큰지, 작은지를 알 수 있기에 이는 방향성이 있는 그래프로 생각할 수 있습니다. 또한, 가장 작은 곳부터 순서대로 채워나가면 되기에, 자기보다 큰 좌표가 있다면 해당 좌표의 값을 하나씩 증가시키면서 나중에 채워나가면 된다는 생각을 할 수 있습니다. 위의 2개를 합치면 위상 정렬이 되기에 위상 정렬의 조건에 맞춰서 구현해주시면 됩니다.  자세한 것은 코드를 참고해주세요.#def..

문제 링크입니다. https://www.acmicpc.net/problem/31849 BFS를 이용한 문제입니다. 편의점의 위치와 자취방의 위치가 주어졌을 때, 편의점과 자취방의 가장 가까운 거리를 구하는 문제입니다. 거리를 구하는 수식 -> 자취방에서 편의점까지의 거리 * 월세 입니다. 문제를 풀기 위해서는 모든 자취방과 편의점 사이의 거리를 구하면 된다라는 생각을 할 수 있습니다.하지만, 방과 편의점의 최대 개수가 5*10^5 이기에 모든 경우를 탐색한다면 시간 초과가 생길 것입니다. 한번 생각을 해보면, 어떤 편의점에서 출발을 하든 어떤 자취방에 먼저 도착하는 곳이 있다면 해당 편의점이 해당 자취방과 가장 가까운 곳이라는 것이 됩니다. 그렇다면, 모든 편의점에서 동시에 출발해서 각각의 자취방까지 도..