Smallsoft

문제링크문제요약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

*카카오테크 부트캠프 1기로 교육과정중 경험했던 크램폴린에 대한 글입니다.쿠버네티스 환경을 처음 공부해보고 이를 크램폴린에 적용하면서 겪은 여러 문제들을 두서없이 적은 글이다. 여러 문제들이 있었지만 결국 원하는 방향으로 테스트 서버를 구축하였다. 나중에 누군가 도움이 되었으면해서 글을 남긴다. 1. 배포는 어떻게?크램폴린 공식 사용 설명서처음 쿠버네티스 환경을 접하면서 어떻게 사용해야되는지 몰라서 꽤나 해맸다. 다행히 공식 가이드에서 풀스택 배포 설명 및 실습을 위한 레포도 준비되어있었다. 나 같은 경우는 카테부에서 지급해준 쿠버네티스 책과 크램폴린을 실습하며 공부하였다. 그래서 최소한의 배포를 위해서 무엇이 필요하냐 물을 수 있다. 아래 체크리스트로 정리해보았다.  소스코드와 Dockerfile 쿠버..

문제해결문제요약갈색 타일은 카펫의 외곽 부분을 차지하고, 노란색 타일은 내부를 자치한다.노란색 타일과 갈색 타일이 주어질때 가로와 세로의 길이를 반환하는 문제이다.풀이얻을 수 있는 정보를 종합해서 어떻게 풀어야할지 계획을 세워야했던 문제였다.노란타일 + 갈색타입 = 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..