Smallsoft

문제링크문제요약특정 수를 기준으로 왼쪽에 위치한 숫자는 증가하고 오른쪽에 위치한 숫자는 감소하는 형태를 띤 부분 수열을 바이토닉 수열이라고 부른다. 문제에서 수열이 주어질때, 가장 긴 바이토닉 수열을 찾는 문제이다. 풀이LIS를 두번 적용시킴으로써 해결 가능한 문제이다.바이토닉 수열은 처음에는 증가하다 특정수를 기준으로 감소하는 형태이다.LIS를 통해 증가하는 수열에 대한 정보를 dp[]에 담는다.이 배열을 다시 감소하는 수열을 구하는 LIS를 구하면 dp[]에는 증가이후 감소하는 형태의 수열에 대한 길이를 구할 수 있다.소스코드#include using namespace std;/*증가 또는 감소세의 방향이 일직선이 수열을 바이토닉 수열이라고한다.바이토닉 수열을 찾으시오*/int n, ans;int a..

문제링크문제요약n개의 수열(아이들)이 정렬되어있지않은 상태이다.이 수열을 정렬하기위해서 수를 옮겨야하는데 이때 최소한으로 옮기는 수를 출력하는 문제이다.풀이3개의 수열을 여러가지 형태로 가정해보겠다.[1, 2, 3] 이 수열은 0번 움직이면 정렬된다.[1, 3, 2] 이 수열은 3을 뒤로 보내서 1번에 정렬된다.[3, 2, 1] 이 수열은 총 2번을 움직여야 정렬된다.이 규칙을보면 LIS를 구하는것과 연관이 있어 보인다.[1, 2, 3]은 최장 증가 부분 수열이 [1, 2, 3]이고,[1, 3, 2]은 [1, 2]가 나온다.[3, 2, 1]은 [1] 하나만 나오게된다.풀이를 정리하면위치를 옮기지 않아도 되는 아이들은 이미 오른차순을 만족하는 부분 수열이다.이 중 가장 긴 오름차순 부분 수열을 찾고, 이를..

문제링크문제요약이 문제는 최장 증가 부분 수열 알고리즘에 관한 문제이다.해당 알고리즘의 대표적인 예시이기 때문에 따로 이 문제를 못풀겠다면 해당 알고리즘을 공부해야한다.소스코드#include #include using namespace std;int n;int board[1005];int dp[1005];int ans;int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i > board[i]; dp[i] = 1; for (int j = 0; j board[j]) dp[i] = max(dp[i], dp[j] + 1); } a..

문제링크 문제요약나선형 모양으로 삼각형이 계속해서 추가될때, n번째 삼각형의 변의 길이를 구하는 문제이다.풀이나선형모양의 삼각형이 계속 추가된다해서 어렵게 생각할 필요없다.문제에서 P(10)의 예시를 주어지는데 이 수열이 어떻게 증가하는지 찾고 DP로 해결 하면되는 문제이다.삼각형의 변의 길이는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9씩 증가한다.증가하는걸 자세히보면 n번째는 (n - 2) + (n - 3) 만큼 증가한다는걸 알 수 있다.처음 P(4)까지의 값을 세팅하고 이를 통해 P(100)까지 값을 구한뒤 P(n)을 출력해주면된다.소스코드#include #include using namespace std;long long dp[105];int n;int main() { cin >> n..

문제링크문제요약n개(2 이 트리를 둘로 나누었을때 두개의 트리가 가지고있는 노드의 수를 최대한 비슷하게 짤랐을 때, 두 트리의 노드 수 차이를 출력하면된다. 풀이처음에는 규칙성을 찾아보려했지만, 트리의 특별한 형태가 정해져있지않아 규칙을 찾기가 쉽지않았다. 결국 완전탐색을통해 wires를 하나씩 제거해가며 노드의 수를 계산해주었다. 노드의 수를 계산하는건 dfs로 계산하였다.소스코드#include #include #include using namespace std;vector v[105];bool vist[105];int recursion(int cur) { int count = 1; vist[cur] = 1; for (const auto &e : v[cur]) { if (v..

문제링크문제요약숫자로 이루어진 문자열 number가 주어진다. 주어진 숫자 문자열로 만들 수 있는 모든 순열 조합에서 소수를 찾아 그 개수를 반환하면된다. 제약조건number의 길이는 1이상 7이하이다.number는 0부터 9까지의 숫자로 구성되어있다.풀이에라토스테네스의 체 알고리즘을 이용해서 1e8까지의 소수를 구한뒤,number를 dfs로 완전탐색을 돌리며 소수가 몇개인지 구하면된다.소스코드#include #include using namespace std;bool arr[10000000];int ans;bool vist[10];void primenum() { arr[0] = false; arr[1] = false; for (int i = 2; i

문제해결문제요약갈색 타일은 카펫의 외곽 부분을 차지하고, 노란색 타일은 내부를 자치한다.노란색 타일과 갈색 타일이 주어질때 가로와 세로의 길이를 반환하는 문제이다.풀이얻을 수 있는 정보를 종합해서 어떻게 풀어야할지 계획을 세워야했던 문제였다.노란타일 + 갈색타입 = width * height문제의 조건에 따라 width >= height 이다.중앙에는 노란타일이 있으니, (width - 2) * (height - 2) = yellow위 3가지 정보를 바탕으로 height를 통해 width를 얻고, height를 늘려가면서 조건에 만족하는 가로, 세로를 찾으면된다.소스코드#include #include using namespace std;/*중앙에 위치해야하는 노랑외곽에 위치해야하는 갈색노랑과 갈색 수를 ..

문제링크문제요약수포자 1,2,3 은 다음과 같은 패턴을 반복한다.수포자 1 = [1, 2, 3, 4, 5 ...]수포자 2 = ['2, 1' , '2, 3' , '2, 4' , '2, 5' , ...]수포자 3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5 ...정답배열 answers 가 주어졌을때 수포자 1, 2, 3 중 가장 점수가 높은 사람을 리턴하면된다. 풀이 딱히 풀이라고 할것도 없이 완전탐색을 돌리면된다. answers를 0부터 answers.length()까지 돌리면서 수포자의 점수를 체크하면된다.  소스코드#include #include using namespace std;/*1번 - 12345 ...2번 - 21 22 23 24 25 ...3번 - 33 11 22 44 55 ...

문제링크비슷하지만 조금 더 쉬운 문제문제요약강의실을 사용해야하는 강의 n에 대해 시작시간과 끝나는 시간을 입력으로 준다. 문제에서는 강의 번호에 대한 정보가 주어지지만 이 입력은 쓸모없는 정보이기에 안써도된다. 강의 n개가 입력으로 들어왔을때 필요한 최소 강의실의 수를 출력하면된다. 풀이겹치는 강의들이 최소한의 강의실로 배치될 수 있도록 효율적으로 관리해야한다. 효율적으로 관리하기위해서 시작시간을 기준으로 정렬한뒤 종료시간에 대한 정보를 자료구조에 넣고 이를 관리해서 강의실 재사용이 가능한지 판단하면 된다. 자료구조에따른 시간복잡도처음에는 종료시간에 대한 정보를 vector에 넣고 이 백터를 처음부터 끝까지 봤는데 이건 시간복잡도가 꽤 길게나온다. 종료시간중에 가장 먼저 끝나는 종료시간만 알면되는 부분이..

문제링크문제요약지문자체가 조금 길고 난해한 감이있다.결국 지문에서 요구하는건 n개의 센서가 주어지고 이것들을 k숫자만큼 그룹을 만들것인데 이걸 최적화해서 그룹을 지으라는것이 요구 사항이다.풀이n개의 평면에서 k개로 그룹짓기 위해서는 k - 1만큼 자르면 k개가 그룹지어진다.그럼 k - 1개 만큼 잘라야하는데 어떤것을 자르면 각각의 그룹 짧은 거리로 묶일것인가를 생각해야한다. 문제에서 요구하는건 짧은거리끼리 묶여야하니 n개의 센서들 간의 거리를 얻고 여기서 k - 1 만큼 큰 거리들을 지워주면 된다. 예시로 1, 3, 6, 6, 7, 9 를 2개의 그룹으로 나누려면3-6이 가장 멀리 떨어져있는 거리니까 [1, 3], [6, 6, 7, 9]로 그룹을 만들면된다. 각각 노드가 떨어진 거리를 배열로 만들면 [2..