Smallsoft

문제링크비슷하지만 조금 더 쉬운 문제문제요약강의실을 사용해야하는 강의 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..

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

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