본문 바로가기

전체 글

BOJ)11003 최소값 찾기 문제: icpc.me/11003 구간 n에서 ai-l+1 ~ai의 최솟값을 매번 찍어내는 문제이다. RMQ 문제로 생각하여 세그트리나 multiset을 이용한 풀이를 예전에 제출했지만 n이 너무나도 커서 tle를 맞은 후 잊고 있던 문제였지만 오늘 다른 문제에서 다이나믹프로그래밍을 공부하다가 필요에 의해 다시 풀게 된 문제이다. 이 문제는 deque를 이용하여 해결할 수 있다. 연속 된 시퀀스에서 deque에는 pair형으로 해당 값과 해당 인덱스를 가지고 있을것이다. 우리는 답을 출력할 때 deque에 삽입 되어있는 구간에서 최솟값을 출력해야 하기때문에 앞이나 뒤에 최솟값을 가지고 있어야한다. 일단 deque의 front에 최솟값을 가지고 있다고 해보자. 그러면서 만약 deque의 front의 값의 인.. 더보기
BOJ)1460 진욱이의 농장 문제: icpc.me/1460 n*n 크기의 격자에 씨를 뿌리는 방법이 주어지고 격자에서 임의의 정사각형을 선택하여 정사각형 내부의 점에 서로 다른 씨앗이 최대 2개가 되도록 정사각형을 선택할 때 가장 넓은 정사각형의 넓이를 출력하는 문제이다. 씨앗의 종류인 F의 범위가 0~7인걸 이용하여 F^2+F로 모든 경우의 씨앗을 정한다면 현재 상태에서 해당하는 씨앗이 뿌려져있는 가장 넓은 정사각형을 구하는 문제로 치환하여 풀 수 있다. 이는 다이나믹 프로그래밍을 이용하여 n^2에 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include using namespace std;int res, a[10.. 더보기
BOJ)13548 수열과 쿼리 6 문제: icpc.me/13548 길이가 N인 수열이 주어질 때 구간 i j 사이에 가장 많이 등장한 수가 몇번 등장했는지 출력하는 문제이다. 이 문제를 온라인으로 수행하려고하면 굉장히 힘들어 보인다. 하지만 업데이트가 이루어지지 않기 때문에 오프라인 쿼리 문제로 변형시켜서 풀어볼 수 있다. 따라서 이 문제를 mo's algorithm을 이용하여 풀건데 가장 많이 등장하는 수를 결정해야 하기 때문에 현재까지 가장 많이 등장하는 수를 계속 가지고 있어야하고 각각의 수가 몇번 등장하였나 배열을 a, i번 등장한 수가 몇개 있나 배열을 b에 각각 저장해두면 현재 쿼리의 답이 x면 만약 add로 인하여 추가 된 b가 x보다 크다면 x를 증가시켜주고 erase로 인하여 x만큼 등장한 수가 없어진다면 x를 감소시켜주.. 더보기