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개(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 ...

문제링크문제요약문제의 요구 사항은 다음과 같다.레벨 점수가 배열로 주어진다.각 레벨의 점수는 다음 레벨보다 작아야한다.점수를 수정하는 동작은 1번동작할때 1점씩 감소한다.수정동작을 최소한으로 해야한다.즉, 점수 배열을 오름차순으로 정렬하기 위해서 수정동작을 거쳐야하는데 이때 이 수정동작을 최소로 하는 경우의 수를 요구는 문제이다.풀이이 문제는 그리디문제이다. 명제를 세우고 명제가 맞는지 확인하고 맞다면 그대로 풀면된다. 명제레벨의 점수를 뒤에서부터 순차적으로 비교하며, 현재 레벨의 점수가 다음 레벨의 점수 이상인 경우, 최소한으로 점수를 낮추어 조건을 만족시키면 전체 최소 감소 횟수를 보장할 수 있다.소스코드#include using namespace std;/*레벨을 난이도 순으로 배치했지만 잘못된 점..

문제링크문제요약알파벳이 담겨있는 문제열을 두가지 방법에 따라 배치해 사전순으로 가장 빠른순으로 정렬하는 문제이다.방법카드를 가장 오른쪽에 놓는다.카드를 가장 왼쪽에 놓는다.풀이그리디로 해결하는 문제이다. 그리디는 '명제'를 만들고 그 명제가 타당한지 확인하는 과정이 중요하다. 명제현재 문자열과 새로 추가할 카드의 비교:새로 추가할 카드가 현재 문자열의 첫 번째 문자보다 사전순으로 앞서면 왼쪽에 추가한다.그렇지 않으면 오른쪽에 추가한다.그리디 선택의 정당성문자열을 점진적으로 만들 때, 각 단계에서 사전순으로 가장 작은 선택을 하면 최종 결과도 사전순으로 가장 앞서는 문자열이 된다.이전 선택이 현재 선택에 영향을 주지 않으므로, 그리디 방법이 올바르게 작동한다.소스코드#include #include usin..

문제링크문제요약목표로 하는 n마리의 고양이수가 주어진다.처음 고양이의 수는 0마리에서 시작하고 고양이를 늘릴 수 있는 방법은 2가지이다.1마리를 생성한다.고양이 k마리가 존재할 때 0~k마리중 원하는 만큼 복제할 수 있다.과정처음에는 bfs로 접근했다. 목표하는 n마리만큼 최단거리로 도달하려면 bfs 알고리즘이 적절할 것이라 생각하고 시작했다. 하지만 목표 고양이의 수가 최대 1e12 까지 주어지므로 시간초과와 메모리 문제로 bfs로는 풀 수 없다. 이 문제를 간단한 수학적으로 접근해야했다 고양이를 복제를 0부터 k마리만큼 복제할 수 있는데 굳이 0부터 1씩 늘려서 체크할 필요가 없다k만큼 늘린 다음 이 수가 n보다 작으면 다시 k만큼 늘리고 n을 넘어간다면 그 즉시 멈추고 여태까지 연산 횟수를 출력하면..