알고리즘 모음(C++)

문제 링크입니다. 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 이기에 모든 경우를 탐색한다면 시간 초과가 생길 것입니다. 한번 생각을 해보면, 어떤 편의점에서 출발을 하든 어떤 자취방에 먼저 도착하는 곳이 있다면 해당 편의점이 해당 자취방과 가장 가까운 곳이라는 것이 됩니다. 그렇다면, 모든 편의점에서 동시에 출발해서 각각의 자취방까지 도..

문제 링크입니다. https://www.acmicpc.net/problem/31848 도토리를 구멍이 있는 분류기에 굴렸을 때, 몇번 째 구멍에서 빠지는지 구하는 문제입니다.못빠지는 분류기를 지날 때마가 도토리의 크기는 1씩 작아집니다. 따라서 먼저 뒤에 있는 분류기에 위치 값을 더해주면서 어느 정도의 도토리까지 통과할 수 있는지를 구했습니다. 구멍의 크기를 갱신했으면, N번 째 도토리의 크기까지 몇번 째 구멍에서 먼저 빠지는지를 저장해줬습니다. 도토리의 크기를 입력 받았으면, 이전에 저장해두었던 값을 통해서 몇번 째 구멍에서 빠지는지 출력해줍니다.(이분 탐색도 가능합니다.)  자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #inc..

문제 링크입니다. https://www.acmicpc.net/problem/31846 문자열이 하나 주어지고, 범위가 주어졌을 때, 주어진 범위를 잘 접어서 최대로 겹치는 문자 수를 구하려고 합니다. 먼저, 문자열의 길이와 주어지는 범위의 수가 적기에 모든 경우를 확인해봐도 시간초과가 되지 않습니다. 따라서, 문자열을 하나만 뒤집었을 때, 2개만 뒤집었을 때, 3개만 뒤집었을 때, ... N개를 뒤집었을 때를 전부 확인해봐서문자가 얼마나 겹치는지를 직접 확인해주면 됩니다.  자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace st..

문제 링크입니다. https://www.acmicpc.net/problem/31845 딜러와 카드를 주고 받을 때 얻을 수 있는 최고 점수를 구하는 문제입니다. 플레이어는 원하는 카드를 주고 받을 수 있기 때문에 항상 최고 점수 카드를 받고 최저 점수 카드를 주는 것이 최고입니다.따라서 먼저 정렬을 통해 카드의 점수를 정렬해줍니다. 순서대로 최고 점수 카드를 더하고, 최저 점수 카드를 없애면서, 각 턴들의 최고 점수들을 저장합니다. 마지막에 저장된 점수들 중에서 가장 큰 점수를 출력해주면 됩니다.  자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include usin..

문제 링크입니다. https://www.acmicpc.net/problem/31844 박스를 옮길 수 있는 조건을 찾아서 해결하는 문제입니다. 박스를 옮길 수 있는 조건은 2가지입니다. 1. 로봇 -> 박스 -> 도착점2. 도착점  해당의 경우가 아니라면 전부 -1을 출력해주면 되고해당 경우를 만족한다면 로봇과 도착점까지의 거리를 구해주면 됩니다.   자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;string arr;int st, fin, box;void solve() { if (st > arr; for (int i ..

문제 링크입니다. https://www.acmicpc.net/problem/14438 세그먼트 트리를 이용한 문제입니다.  자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include #include #include #define INF LLONG_MAXusing namespace std;int N, M;long long Index[100001];vector Tree;long long segment_tree(int st, int fin, int node) { if (st == fin) return Tree[node] = st; int mid = (st + fin) /..

문제 링크입니다. https://www.acmicpc.net/problem/14428 세그먼트 트리를 이용한 문제입니다.  자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include #include #include #define INF LLONG_MAXusing namespace std;int N, M;long long Index[100001];vector Tree;long long segment_tree(int st, int fin, int node) { if (st == fin) return Tree[node] = st; int mid = (st + fin) /..

문제 링크입니다. https://www.acmicpc.net/problem/1725 세그먼트 트리를 이용해 풀었습니다. N개의 직사각형의 높이가 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제입니다. 직사각형의 높이가 다를수 있기에, 붙어있는 직사각형들의 가장 높은 높이는 가장 직사각형의 높이가 될 것입니다.따라서, 이를 이용해 세그먼트 트리로 풀었습니다. 먼저, 트리에 가장 작은 높이의 위치를 저장해줬습니다.예를 들어, 자식 노드가 (2, 1)이라면, 1이 작은 높이이니 해당 노드는 높이가 1인 위치가 저장될 것입니다. 이렇게 트리에 작은 높이들의 위치가 저장이 되었다면,  (0 ~ N-1) 범위에서 가장 넓이가 넓은 직사각형을 찾습니다.방법은 주어진 범위에서 가장 낮은 높이의 위치..

문제 링크입니다. https://www.acmicpc.net/problem/6549 세그먼트 트리를 이용해 푸는 문제입니다. N개의 직사각형의 높이가 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제입니다. 직사각형의 높이가 다를수 있기에, 붙어있는 직사각형들의 가장 높은 높이는 가장 직사각형의 높이가 될 것입니다.따라서, 이를 이용해 세그먼트 트리로 풀었습니다. 먼저, 트리에 가장 작은 높이의 위치를 저장해줬습니다.예를 들어, 자식 노드가 (2, 1)이라면, 1이 작은 높이이니 해당 노드는 높이가 1인 위치가 저장될 것입니다. 이렇게 트리에 작은 높이들의 위치가 저장이 되었다면,  (0 ~ N-1) 범위에서 가장 넓이가 넓은 직사각형을 찾습니다.방법은 주어진 범위에서 가장 낮은 높이의..

문제 링크입니다. https://www.acmicpc.net/problem/12837 세그먼트  트리를 이용한 문제입니다.세그먼트 트리를 이용해 푸는 문제입니다. p일에 수입/지출이 계속 주어졌을 때, 원하는 날까지의 합을 구하는 문제입니다. N의 범위가 10^6까지이기에 일반적인 방법으로 더한다면 시간 초과가 생깁니다.  자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include #include #define INF 987654321using namespace std;int N, Q;long long Index[1000001];vector Tree;long lon..