https://www.acmicpc.net/problem/2879 가능한 많이 그룹을 묶어 탭을 편집해야 한다.그룹을 묶는 조건은 나와 같은 편집 방법(추가 or 삭제)인 연속된 줄들만 묶을 수 있다.개별적으로 남은 줄들은 어쩔 수 없이 남은 편집 횟수만큼 그대로 편집해줘야 한다. 따라서, 앞에서부터 자신의 줄이 올바를 때까지 다음 과정을 반복한다.나부터 시작해서 그룽으로 묶을 수 있는 마지막 줄의 위치까지 그룹으로 묶는다.그룹 내에서 가장 적은 편집 횟수로 올바르게 되는 줄의 편집 횟수를 찾는다.그룹을 다 같이 편집할 때, 하나라도 완성이 되면 그룹을 다시 재구성해야 하기 때문해당 편집 횟수만큼 그룹을 모두 편집한다.이러면 그룹 내에서 최소 한 개의 줄은 완성이 되므로 다시 그룹을 재구성해야 함.편집 ..
그리디
https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 한다.이 말은 즉, 그리디로 풀라는 얘기와 같다. 각 이동 방향 문자를 사전 순으로 나열하면, 아래[d] -> 왼[l] -> 오[r] -> 위[u] 순서가 된다.즉, 목표 위치로 가는 경로를 구할 때, 다음과 같은 규칙이 생긴다.가장 아래로 많이 간다.아래로 갈 수 없다면, 왼쪽으로 간다.왼쪽으로 갈 수 없다면, 오른쪽으로 간다.오른쪽으로 갈 수 없..
https://www.acmicpc.net/problem/1202 가방은 오름차순으로 정렬한다.가장 가벼운 가방으로 들 수 있는 보석들은 이후 모든 가방으로도 들 수 있기 때문이다. 보석은 무게를 기준으로 오름차순으로 정렬하되, 무게가 같은 경우, 가격순으로 내림차순으로 정렬한다.훔칠 수 있는 보석 가격의 합의 최댓값을 구해야 하기 때문이다. 가방을 모두 순회하며 해당 가방의 무게로 들 수 있는 보석들을 우선순위 큐에 저장한다.우선순위 큐는 무게와 상관없이 가격순으로 내림차순 정렬이 되도록 한다. 현재 가방 무게로 가장 비싼 보석을 더하고, 큐에서 제거한다.#include #include #include #include using namespace std;bool Cmp(const pair& a, con..
https://www.acmicpc.net/problem/2457 처음에 우선순위 큐를 사용해서 시간초과가 나서 안 쓰고 풀었다. 문제에서 주의해야 할 점은, 3월 1일에 피고 11월 30일에 지는 꽃은 11월 29일까지만 유효하다는 것이다.따라서, 문제에서 11월 30일까지 꽃이 피어있어야 하니, 심어야 하는 꽃은 최소 12월 1일 이상에서 져야 한다.(때문에 End를 1201로 지정) 다음으로, 1, 3, 5...월은 31일까지 있고, 나머지는 30일까지 있는 규칙을 굳이 따져야 하나 싶었다.따라서 그냥 3월1일이면 301로 저장했다. (12월 31일 -> 1231)이렇게 저장해도 어차피 순서는 같아서 무관하다. 로직은 다음과 같다.112 28 8 166 18 7 99 5 10 254 22 8 255..
https://www.acmicpc.net/problem/3109 파이프를 연결하는 방향이 무조건 X가 증가하는 방향으로만 있다. (오른 대각 위, 오른쪽, 오른 대각 아래)DFS를 사용해 풀이를 한다. 한 파이프를 연결할 때, 이후에 다른 파이프들의 연결에 최대한 지장을 주면 안 된다.따라서, 항상 위쪽으로 먼저 DFS 탐색을 해야 한다. 한 번 탐색한 위치에서 파이프 연결이 실패했다면, 해당 위치로는 파이프 연결이 불가능하다는 의미이기 때문에, 꼭 방문 처리를 해줘야 한다. 어차피 방문 처리를 하나, 해당 좌표가 'X'이거나 같으므로, 방문 처리를 해당 위치를 'X'로 초기화하는 것으로 한다.#include #include using namespace std;// 방향 [오른 대각 위, 오른쪽, 오른..
https://www.acmicpc.net/problem/17420 사용하려는 날보다 이전 날에 사용한 기프티콘의 유효 기간보다 커야 한다는 점을 유의한다.기프티콘 사용 계획을 오름차순으로 정렬하여, 먼저 사용하는 순서대로 로직을 설계한다. 다음 예시를 통해 설명한다.424 2 3 29 // 기프티콘 유효 기간25 30 30 30 // 사용하려는 날 ans: 6 남은 기프티콘의 유효 기간이 짧은 순서대로 사용해야 한다하지만, 30일에 사용하는 2, 3, 24의 경우, 아직 25일이 지나지 않았기 때문에, 사용하지 못한다. 그러면 사용하려는 날을 기준으로 계산해 보자.사용하려는 날을 오름차순으로 정렬한다. 25일을 보자.현재 날짜가 25일이면, 사용할 수 있는 기프티콘으로는 24가 있다.기프티콘..
https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 먼저, 모든 작업을 처리한, 총 ms를 구한다.(기저사항, 모든 작업이 끝났는지 확인하기 위함) 요청은 무조건 먼저 들어오는 순으로 받아야 하기 때문에, 요청 시간을 기준으로 오름차순으로 정렬한다.현재 시간과 현재 처리 중인 요청을 저장할 변수를 선언한다.더 처리할 요청이 남아있고, 현재 시간에 요청이 있을 경우, 큐에 { 수행 시간, 요청 시간 }으로 넣는다.이러면, 새 데이터가 들어오면 우선순위 큐에서 수행 시간을 기준으로 오름차순으로 정렬..
문제: https://www.acmicpc.net/problem/1781 최대 데드라인을 초과하지 않는 범위에서 가장 많은 컵라면을 얻는 문제이다. ex)7 1 9 1 100 2 300 2 99 3 100 5 100 5 999 다음 예시에서, Day1에서는 1~5 데드라인의 문제를 모두 풀 수 있다.그리고, Day5에서는 5 데드라인의 문제만이 풀 수 있다. 따라서, 이 문제는 마지막 날부터 역순으로 계산하는 것이 핵심인 문제이다. 데드라인을 하나씩 줄여가며, 각 날짜에 풀 수 있는 문제들을 우선순위 큐에 넣는다.(우선순위 큐는 그러면 계속 풀 수 있는 문제 후보군들이 남아있다)각 날마다 우선순위 큐 안에서 보상이 가장 큰 문제를 선택하여 정답에 더하고, 큐에서 뺀다.#include #include #i..
