정리와기록 블로그

문제 : programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 접근: deque에 데이터를 담고, 최소 - 최대를 유지하게 한다. 삽입 시에만 정렬을 수행한다. d 1 연산은 pop_front, d -1 연산은 pop_back으로 처리한다. 코드: #include #include #include #include using namespace std; deque nums; vector solution(vector operations) { for (auto& s : operations) { if (s == "D 1") { if (nums.size() > 0) nums.pop_back(); } else if (s..

문제: programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린�� programmers.co.kr 접근: 큐에서 하나씩 빼보면서 남은 원소에 더 높은 등급이 있을 때와 아닐때로 행동을 달리해주면된다. location-- 해주는데, 만약 location location = Q.size() - 1 (마지막에 삽입) 2) 남은 우선순위가 없었다면 (출력할 차례) -> return answer 해..

보호되어 있는 글입니다.

문제: www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 접근: 회의실을 끝나는 순서대로 정렬합니다. (이때 같은 시간에 끝난다면 시작 시간이 빠른 순서대로 정렬합니다) 정렬한 배열을 순회하면서 '이전 회의 시간이 끝나는 시간' > N; for (int i = 0; i > temp.first >> temp.second; rooms.push_back(temp); } sort(rooms.begin(), rooms.end(), comp); int cnt = 0; long last = -1; for (int i = 0; i < N; i..

문제: www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 접근: DP의 접근법은 1) 완전 탐색으로 풀 수 있을지 본다. 2) 중복되는 부분을 cache로 메모이제이션을 해준다. 입니다. 해당 논리로 접근했습니다. 1) 완전 탐색은 물건을 빼거나 / 넣거나 하면 2^100 만큼의 경우를 만들어낼 수 있고, 이 때 겹치는 부분에 대해서만 cache 처리해주면 된다고 생각했습니다. 재귀로 도전했는데..

문제 : programmers.co.kr/learn/courses/30/lessons/42578# 코딩테스트 연습 - 위장 programmers.co.kr 초기 접근: 중복되는 옷이 한 개도 없기 때문에, 경우의 수로 풀면 될 것 같다는 느낌을 받았습니다. 초기 접근은 선택하고, 안하고를 반복하여 전체 부분 집합을 만든 다음, answer를 부분 집합의 곱으로 구해주었습니다. 해당 접근으로 풀었을 때, 케이스1에서 오답이 발생했고 극단적인 경우를 생각해보았을 때, 2^30 - 1 > 10억이므로 안된다는 것을 알게 되었습니다. 실패 코드(일부): void PickSum(const int& n, int i, int subSum) { if (i == n) // 0부터 시작 { answer += subSum;..

문제: programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 �� programmers.co.kr 접근: 처음에는 숫자의 수열 순서대로 하나씩 비교해서 정렬하려 했으나, 이내 틀리고 산탄총 식 코딩을 하다가 이건 아니다 싶어서 답을 찾아보았습니다. 꽤나 직관적이고 간단하게 정렬 함수는 다음과 같이 앞뒤 순서를 바꾼 결과를 비교하면 되는 것이었습니다. (true일 경우 sort시 우선순위가 높아집니..

문제: programmers.co.kr/learn/courses/30/lessons/42584?language=csharp 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 접근: prices 배열의 원소를 하나씩 순회하면서, 주식이 떨어질때(prices[j] < prices[i]) 시간을 그만세고 다음 원소로 넘아가는 로직이면 됩니다. int time = 0부터 시작해야 마지막 원소의 시간을 처리할 수 있습니다. using System; public class Solu..