곽민성

와 시험 전날. 오늘은 어려운 문제를 풀고 싶은 기분이어서 수쿼 하나 잡고 열심히 조졌다. 30분 정도 코딩하고 넣으니까 TLE떠서 결국 풀이를 보고 말았다. 참고한 블로그는 여기이다. BOJ 13546 수열과 쿼리 4 개어렵다. 처음 생각했던 풀이는 쿼리 구간 내 sub배열의 값에 따른 index를 정렬된 형태로 저장하는 deque를 관리하고, 각 k(배열

시험기간이라서 문제 스택만 이어가고 있다. 이번에 푼 문제는 어제 푼 문제랑 똑같이 Mo's Algorithm을 쓴다. 어제 문제랑 거의 똑같고, 계산만 조금 달라서 할 말은 없다. 이제부터 문제 풀 때 시간을 재 볼려 한다. 이 문제는 이해 ~5min / 코딩하는데 25m 21s 걸렸다. 얼마 정도 걸리는게 보통인지는 모르겠으나,  코딩이 꽤 느린 거

간단히 한 문제 풀었다. BOJ 13547 수열과 쿼리 5 문제가 꽤나 어려웠는데, 수열을 주고 i~j 인덱스에 서로 다른 수의 개수를 출력하는 문제다. 처음 보고 뭐지 했다. 우선 하나의 쿼리를 처리하려고 생각했을 때, 값이 1~1,000,000 사이니까 i~j까지 돌면서 값 인덱스에 1씩 더하면서 서로 다른 것의 개수를

시험기간이니만큼 쉬운 문제 하나 풀었다. BOJ 1450 냅색문제 이 문제는 단순히 생각했을때 모든 물건을 넣었다 뺐다 하는 경우를 모두 고려해서 O(2^n)으로 해결할 수 있다. 하지만 그렇게 풀기에는 n=30, 너무 크다. 내가 생각한 해법은 n/2로 나눠서 모든 경우를 다 계산하고, 각 경우를 정렬해서 투포인터로 해결할 수

시험 공부 중 한문제 슬쩍 풀었다. BOJ 16978 수열과 쿼리 22 PST로 풀린다고 해서 풀어볼려 했는데, 오프라인 쿼리로 풀릴 거 같아서 느낌 그대로 조져 보았다. 그냥 합 연산인데 오프라인 쿼리를 곁들인? 쿼리1,2를 저장해서 쿼리 2를 정렬하고, 쿼리 1을 순차적으로 해결해 나가면 된다. EZ #include #define ppiipii pair, pair > using

중간고사 6일 남았는데 미쳤다고 이러고 있네 BOJ 1920 수 찾기간단한 이분탐색 문제. 머지 소트랑 이분탐색 감을 살리려고 한번 풀었다. //BOJ 1920 수 찾기 #include using namespace std; int arr[(int)1e5 + 7], tmp[(int)1e5+7]; void merge_sort(int s,int e) { //printf("%d %d\n", s,e); if(