본문 바로가기

백준/정렬7

백준 12015 c++ "가장 긴 증가하는 부분 수열 2" -PlusUltraCode- https://www.acmicpc.net/problem/12015[필자 코드]먼저 LIS 를 알아야 된다.*가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence)**은 주어진 수열에서 일부 숫자들을 골라내어, 원래 순서를 유지한 채로 증가하는 형태로 만들 수 있는 가장 긴 부분 수열을 찾는 문제입니다.예를 들어, 수열이 [10, 20, 10, 30, 20, 50]라면, 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]입니다.중요한 점은, 수열 내 숫자의 순서를 바꾸지 않는다는 것입니다. 따라서 단순히 숫자를 크기순으로 나열하는 문제가 아닙니다.위 코드는 LIS를 효율적으로 계산하기 위해 **이진 탐색 (Binary Search)**를 활용한 방법을 사.. 2024. 12. 26.
백준 1202 C++ "보석 도둑" -PlusUltraCode- https://www.acmicpc.net/problem/1202 [필자 사고]이 문제는 크게 sort 와 우선순위 큐를 활용하여 문제를 해결 했다. 필자는 우선순위 큐를 처음에 생각 못하여 binary_Search() 를 진행했지만 실패했다. 필자는 다음과 같은 사고 과정으로 문제를 해결했다. 가방의 무게는 오름차순으로 정렬한다.보석 배열은 값어치 순이 아닌 무게 순으로 오름차순으로 정렬한다. while 문을 실행하여 가방을 기준으로 보석들의 무게가 가방의 담을 수 있는지 점검하고 담을 수 있다고 하면우선순위 큐에 넣는다.우선순위 큐에 넣어진 값은 보석의 값어치가 높은순으로 정렬되어 있어매번 하나의 가방을 검사할 때마다 가장 높은 값어치를 꺼내 sum에 더한다. 여기서 필자는 처음 의문이 들었다.다른 .. 2024. 11. 14.
백준 10986 c++ "나머지 합" -PlusUltraCode- https://www.acmicpc.net/problem/10986 [필자 사고]이 문제를 풀기 위해서는 2가지 방법을 알고 있어야 된다. 1. S[i] = S[i-1] + arr[i]     2. a%M + b%M  == (a+b)%M  이라는 공식을 알고 있어야 된다.  3. S[i]%M 으로 나눴을 때 같은 숫자가 나오는 경우가 있다.S[2]%M = 1S[4]%M = 1 인 경우 S[4] - S[2] 를 하게 되면 나머지가 0 으로 바뀌게 된다. 이말은 즉 구간합 2를 제외한 3하고4는 나머지가0 의 합이라는 소리다. 즉 같은 숫자가 나온것들끼리 컴비네이션으로 nC2 를 하게 되어 더해주면 된다. 또한 마지막으로 주의할점은 문제에서 주어지는 숫자들의 크기이다. 상당한 큰 숫자들이 있따. 문제를 잘 .. 2024. 8. 2.
백준 11659 c++ "구간 합 구하기 4" -PlusUltraCode- https://www.acmicpc.net/problem/11659 [필자 사고]구간 합을 구해야 되는 문제이다.문제에서 주어진대로 1~3의 숫자들의 합을 하나씩 구하다 보면 시간초과가 나오게 된다. 그 이유는 O(n^2)의 성능으로 N=10^5이기 때문이다. 필자는 이러한 이유로 아래와 같은 배열을 만들었따. S[i] = S[i-1] + a[i]    (i>=1) 이 배열의 뜻은 i번째 배열은 1,2,3,4,5,....i 의 값들의 합으로 이루어진 배열이다. 즉 1~3의 합을 구하기 위해서는S[3] - S[0]을 하게 되면 된다.[소스 코드] #include #include using namespace std;int N, M;vector arr;vector S;void Input() { cin >> N.. 2024. 8. 1.

티스토리툴바