Algorithm/BOJ (19) 썸네일형 리스트형 [백준 7662] 이중 우선순위 큐 우선순위 큐 문제 www.acmicpc.net/problem/7662 programmers.co.kr/learn/courses/30/lessons/42628 해당 문제와 동일합니다. [문제 풀이] kangwlgns.tistory.com/35 [소스 코드] C++ / 이중 우선순위 큐 구현 #include #include #include #include #include #include using namespace std; typedef long long ll; template class dual_priority_queue { priority_queue maxq; priority_queue minq; unordered_map maxdel, mindel; public: dual_priority_queue() .. [백준 12899] 데이터 구조 세그먼트 트리 문제 www.acmicpc.net/problem/12899 www.acmicpc.net/problem/1168 해당 문제의 응용문제입니다. 위 문제도 같이 푸는 것을 권장합니다. [문제 풀이] 2번 쿼리마다 k번째 수를 반환하는 문제입니다. 1번 쿼리는 자연수를 추가하는 역할입니다. 쿼리의 개수가 심상치 않습니다. 쿼리의 개수를 보니 매 쿼리를 logn정도로 처리해야 시간 초과가 걸리지 않을 것 같습니다. 세그먼트 트리로 접근해 봅시다. 이 문제를 처음 세그먼트 트리로 생각해보면 상당히 막막합니다. 약간의 팁을 드리면 대부분의 세그먼트 트리 문제는 구간 합, 최소, 최대를 생각하고 접근하는 것이 좋습니다. 세그먼트 트리라고 생각은 들지만 평소에 풀던 세그먼트 트리와는 조금 다른 형태입니다... [백준 11501] 주식 그리디 문제 www.acmicpc.net/problem/11501 [문제 풀이] N개의 주가가 주어졌을 때, 최대 이익을 내는 문제입니다. N의 제한이 1,000,000입니다. 테스트 케이스까지 존재하므로 무조건 $O(N)$의 시간 복잡도로 해결해야 합니다. 우선 최대 이익을 내는 방법을 생각해보겠습니다. 주식을 계속 사들인 다음에 최대 가치일 때 한 번에 팔아버리면 당연히 최대로 이익을 얻을 수 있습니다. 예를 들어 주가가 1, 5, 10일 때, 1을 사고 굳이 5에 팔기보다, 10에 파는 것이 이득입니다. 즉, 현재 구입하는 시점 이후에서 가장 비쌀 때 팔아버리면 되고 현재 구입하는 시점이 가장 비싸다면 사지 않는 것이 이득입니다. 문제는 현재 구입하는 시점 이후에 가장 비싼 때가 언젠지 모른다는 것.. [백준 20500] Ezreal 여눈부터 가네 ㅈㅈ 다이나믹 프로그래밍 문제 www.acmicpc.net/problem/20500 친숙한 문제입니다. [문제 풀이] 1과 5로만 주어진 N자리 자연수 중 15의 배수의 개수를 찾는 문제입니다. 15의 배수라고 하니 별다른 특징을 찾기가 힘듭니다. 조금 형태를 바꿀 필요가 있어 보입니다. 15는 3의 배수이면서 5의 배수입니다. 3과 5는 배수를 구할 때 상당히 익숙한 수입니다. 그러므로 15의 배수인 수를 구하기 위해 3의 배수이면서 5의 배수인 수를 구해보겠습니다. 우선 3의 배수는 모든 자리의 수를 전부 더하고 3으로 나눴을 때 나누어 떨어지는 성질이 있습니다. 그리고 5의 배수는 1의 자릿수가 0이거나 5입니다. 이 문제에서는 1과 5로만 수가 이루어져 있으므로 1의 자릿수가 5입니다. 그러므로 15의.. [백준 20149] 선분 교차 3 선분 교차 판정 문제 www.acmicpc.net/problem/20149 www.acmicpc.net/problem/17387 해당 문제의 기본형 문제입니다. 위 문제를 먼저 푸는 것을 권장합니다. [문제 풀이] 두 선분이 주어졌을 때 두 선분의 교차 여부와 교점을 찾는 문제입니다. 교차하지 않거나 교차하는 점이 무수히 많다면 교점을 출력하지 않습니다. 우선, 다행히도 한 선분을 이루는 두 점은 겹치지 않습니다. 두 점이 겹쳤다면 문제가 상당히 귀찮아집니다. 선분 교차 2의 풀이에서 더 귀찮아진 형태입니다. 테스트 케이스도 상당히 견고해서 집중하고 코드를 짜야합니다. 설명하기에 앞서, 선분 교차 2를 완벽히 이해했다는 가정 하에 설명하겠습니다. 또한 네 점을 p1, p2, p3, p4라고 하고 CCW(.. [백준 2217] 로프 그리디 문제 www.acmicpc.net/problem/2217 [문제 풀이] N개의 로프를 사용하여 들 수 있는 최대의 중량을 구하는 문제입니다. N개의 로프를 사용하여 들 수 있는 중량의 모든 경우의 수를 구한다면 $O(N^2)$이 걸리게 됩니다. N의 최대 제한이 100,000이므로 당연히 시간 초과가 발생합니다. 그러므로 단순하게 전부 구하는 방식 말고 다른 방식을 찾아야 합니다. 이 문제를 어떻게 접근하는지 잘 생각해봅시다. 우리가 구해야 하는 것은 로프가 버틸 수 있는 최대 중량입니다. 사용할 수 있다면 튼튼한 로프를 사용하는 것이 좋아 보입니다. 또한 상대적으로 튼튼하지 않은 로프를 버리고 튼튼한 로프만 사용하여 물체를 들어 올리는 것도 좋아 보입니다. 튼튼하지 않은 로프를 버리는 과정에서,.. [백준 16975] 수열과 쿼리 21 세그먼트 트리 응용문제 www.acmicpc.net/problem/16975 www.acmicpc.net/problem/2042 구간 합 세그먼트 트리를 처음 접한다면 위 문제를 먼저 푸는 것을 권장합니다. [문제 풀이] 수열이 주어지면 최대 100,000개의 쿼리를 처리하는 문제입니다. 쿼리는 두 종류입니다. 1. 특정 범위에 k를 더함 2. 수열의 특정한 위치의 값 출력 1번 쿼리 때문에 느리게 갱신되는 세그먼트 트리 문제처럼 보입니다. 실제로 느리게 갱신되는 세그먼트 트리로 풀 수 있습니다. 하지만 2번 쿼리를 잘 보면 구간의 합을 구하는 것이 아닌 특정한 값을 찾는 문제입니다. 2번 쿼리마저 구간의 합을 구하는 문제였다면 이 문제는 빼도 박도 못하고 느리게 갱신되는 세그먼트 트리 문제였겠지만, 2.. [백준 2629] 양팔저울 다이나믹 프로그래밍 문제 www.acmicpc.net/problem/2629 www.acmicpc.net/problem/5557 위 문제와 접근 방식이 비슷하므로 위 문제를 먼저 해결할 것을 권장합니다. [문제 풀이] 추가 N개 주어져 있을 때, 각 구슬에 대해 양팔저울의 수평을 맞출 수 있는가에 대한 문제입니다. 굳이 모든 추를 사용하지 않아도 되고, 구슬과 추의 위치에 대한 제한은 없습니다. 추의 개수가 30이고, 구슬의 개수가 7개이므로 제한이 작아 보입니다. 지금부터 구슬은 무조건 왼쪽으로 고정시킨다고 생각하겠습니다. 수평을 맞춰야 하므로 오른쪽에 추를 올리는 경우는 왼쪽의 무게를 -시키는 과정이라 생각할 수 있고 왼쪽에 추를 올리는 경우는 당연히 왼쪽의 무게를 +시키는 과정이라 생각할 수 있습니.. 이전 1 2 3 다음
