Smallsoft

문제링크문제요약지문자체가 조금 길고 난해한 감이있다.결국 지문에서 요구하는건 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..

필요성프로젝트를 진행하면서 실제 배포 서버와 유사한 환경에서 동작하는 테스트 서버의 필요성을 느끼게 되었다, 꽤 다양한 이유가 있었지만 크게는 다음과 같은 점에서 필요성을 느끼게 되었다.끊기는 흐름프론트, 백엔드 개발자가 완성한 코드를 검증하기 위해 배포 서버에 업데이트를 적용해야 했는데 이 적용 시간이 너무 오래 걸렸다. 이는 협업과정이 비효율적으로 이루어지게 된 큰 요인이 되었다.클라우드 개발자 이슈클라우드 환경에서 배포를 처음 진행했기에 여러 작업들이 익숙하지 않아 시간이 소모되었고나의 작업이 완료되기 전까지 제대로 된 배포 환경을 제공하기 어려웠다.협업의 비효율성완성된 하나의 배포 환경이 없고, 클라우드 개발자인 내가 배포환경에 모니터링, 로그 수집등 여러 요소를 추가하는 중에도 프론트엔드, 백..

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

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

문제링크문제요약2원과 5원짜리 동전만 가지고있을때 거스름돈 n이 나오고 이 n에 만족하는 최소의 동전수를 구하는 문제 풀이동전이 최소가 되기 위해서는 당연히 5원 위주로 거슬러 줘야한다. 5원 위주로 거슬러주려면 어떻게 해야할까 고민하다 그냥 5로 나눴을때 0일 될때까지 2를 뺐다. 그리고 거슬러 줄 수 없을때는 -1을 출력해야하는데 거슬러 줄 수 없는 경우는 낮은 숫자에서만 나타날꺼라고 생각하고 문제를 풀었다.  소스코드#include using namespace std;int n, ans;int main() { cin >> n; while (n % 5 != 0) { n -= 2; ans++; } if (n == 0) cout

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

문제링크문제요약3차원의 토마토박스가 주어지고 탐색을하는 문제이다. 익은 토마토는 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 총 여섯 방향의 토마토에 영향을 미친다. 이때 토마토가 다 익는 최소날짜를 구하는 문제이다.어떻게 풀어야 할까문제 자체는 배열을 탐색해서 최소일수를 구하는 bfs 문제이다. 다만 3차원이기 때문에 방향이 2차원일때와 다르게 두곳을 더 갈 수 있다. 조금 귀찮지만 2차원 bfs를 잘했다면 못할 문제도 아니다. 다른 문제점은 시작지점이 여러군대 일 수 있는건데, 그냥 이 모든 시작점을 큐에 넣고 bfs를 돌리면된다. 시작점이 여러 개일 경우, 모든 시작점을 동시에 큐에 넣고 bfs를 수행하면 모든 시작점에서 동시에 확산하는것 처럼 작동하기때문에 시작점을 고민할 필요는없다.  소스코드#incl..

문제링크문제요약시작점 1번 에서 부터 시작하여 단방향 그래프를 더 이상 진행할 수 없을때 까지 탐색한다.이때 탐색과정에서 특정노드(팬클럽)을 만나게되면 "YES"를 출력 아니라면 "yes"를 출력하는 문제이다.어떻게 풀어야 할까그래프를 탐색해야하는데 이때 시작지점에서 끝지점까지 쭉 진행해야한다.즉, 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘 dfs를 사용하는 문제이다.팬클럽을 만났을때를 제외하고 stack에 넣으면서 dfs를 하면된다.해당 분기를 끝났다는것은 vector에서 다음 간선이 없는 경우를 분기가 끝났다고 판단하였다.이 문제는 팬클럽을 안만는 "yes"의 경우를 찾는것이 핵심이니 단 한번이라도 팬클럽을 만나지 않는 순간 "..

문제링크문제요약단방향 그래프에서 시작지점 x를 주고 x에서 k만큼 떨어진 노드를 전부 출력하는 문제이다.k까지의 최단거리를 찾는것이니 dfs를 돌린후 거리가 k만큼 나오는것을 출력하면된다. 문제자체가 DFS의 대표문제이니 수도코드나 해결법에대해 따로 적지는 않았다.문제가 이해가 안간다면 dfs를 공부하고오는것이 좋다.소스코드#include #include using namespace std;/*단방향 그래프가 주어질때 거리계산bfs로 풀린텐데시간 복잡도는 괜찮을지 의문*/vector v[1000005];int vist[300005] = {0,};int n, m, k, x;int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >>..

[문제링크][https://www.acmicpc.net/problem/7562]문제요약체스판이 주어지고 나이트의 시작점과 목표하는 도착 지점이 주어진다. 나이트가 목표지점까지 도달하는 최소거리를 구하는 문제이다. bfs개념이 없다면 어떻게 풀어야 할지도 이해할 수 없을 것이다. 반면 bfs개념이 있다면 bfs를 사용하면 바로 해결되는 대표적인 dfs문제이다.어떻게 풀어야 할까2차원배열에서 나이트의 시작점을 큐에 넣고 dfs를 돌리면 해결된다. bfs 개념을 아는데 어떻게 해야 할지 잘 모르겠다면 코드를 보면서 이해하는 것도 좋은 방법이다.수도코드체스판을 2차원배열에 담는다.나이트는 8방향으로 움직일 수 있다. 8방향에 움직임에 대한 배열을 적어놓는다.방문을 기록하는 배열과 최단 거리를 적을 배열을 준비한..