돌이 코딩하는 방

이번에는 38등을 했다. 한동안 only div2 밖에 없어서 2099에 최대한 근접시키고 한번에 쭉 올라가려고 했는데, 뭔가 이번이 기회인것 같아서 그냥 쭉 올려버렸다. 사실 좀 더 잘했을 수 있었을 것 같은데 비장의 한 방 치고는 조금 아쉬웠던 것 같기도 하다. 사실 한번 2등을 했어서 이제는 성에 안차는 것 같기도... A . Subset Mex 두 개의 그룹으로 나누고 두 그룹에 대한 각각의 Mex 값의 합을 최대화 시켜야 한다. 0부터 보면서 2번 이상 나왔으면 양쪽 모두에 넣을 수 있으며, 1번만 나왔으면, 한쪽 그룹에는 넣을 수 없고, 한 번도 나오지 않으면 양쪽 모두 넣을 수 없다. 따라서 우리가 구하고자 하는 값은 1번 이하로 등장한 가장 작은 수 + 0번 이하로 등장한 가장 작은 수 이..

이번에 소개할 Segment Tree 심화는 HLD이다. 원래는 Euler Tour 이후에 바로 글을 작성했어야 하는데, 대회 준비등의 이유로 다른 내용 관련 글을 계속 쓰다 보니까 계속 미뤄져서 이제서야 글을 쓰게 되었다. 사전 지식 (먼저 읽고 와야하는 글) stonejjun.tistory.com/103 세그 먼트 트리 - euler tour tree 설명글 What is HLD? 그러면 본격적으로 HLD는 무엇일까? HLD는 일단 Heavy - Light Decomposition의 약자이다. 무거운거 - 가벼운거 분해. 즉 Decomposition인데 Heavy Groupr과 Light Group으로 분리한다는 것이다. 그러면 여기서 좀 세부적으로 알아야 할 사항이 생긴다. 1. 뭐를 분리하는 것인..

이 글을 쓰게 된 동기는 굉장히 재미있다. 증명을 원하시는 분이 있었고 누군가가 내 글을 링크해주신 것을 알게 되었지만 그 글에서는 증명이 없었고, 그래서 관심을 가지게 되었다. 어느 정도 생각해본 결과 대충 증명이 된 것 같아서 일단은 빠르게 글을 써보려고 한다. 따라서 증명이 완벽하지 않을 수도 있으며 뇌피셜일 수도, 많이 생략했을 수도 있다. 하지만 오히려 직관적으로 받아들여질 수도 있다. 댓글로 비판과 지적은 언제나 환영한다.이 글을 읽기 전에...로테이팅 캘리퍼스 설명글 stonejjun.tistory.com/42본인은 설명을 굉장히 못하기 때문에 어쩔 수 없이 설명하려면 코드와 함께 설명하는 수밖에 없을 것 같다. 위 글의 맨 마지막에 코드가 있고, 증명과정에서 그 코드를 언급을 하게 될 것 ..

solved 기준 문자열을 너무 안풀었고, 문자열 관련 기초 코딩능력이 딸리는 것 같아서 아래와 같이 검색한 랜덤 문제를 푸려고 한다. 계속 푸는 대로 업데이트 할 예정이다. BOJ 17413 단어 뒤집기 제발 문제 좀 읽자. 1. 전체 뒤집은면 되는 줄 알고 reverse가 끝인줄 알았다. 2. 단어별로 뒤집는 것 인줄 몰랐다. 3. 자잘한 코딩 실수들. 정신좀 차리자. 대회면 망했다. 그래도 줄 입력이 getline(cin,s); 인것은 기억해냈다. 풀이는 입력 종류별로 케이스를 나눠서 뒤집어야 하는 것들은 스택에 담아두면 끝. 닥히 어렵지 않다. 더보기 #include using namespace std; typedef long long int ll; string s; string s2; stack..

문제 링크 : https://www.acmicpc.net/problem/13310 문제 태그 더보기 삼분 탐색, 로테이팅 켈리퍼스, 볼록 껍질 문제 풀이 가장 멀리 떨어진 두 별의 거리가 최소인 날을 구해야 한다. 다시 생각하면 임의의 두 별에 대해서 거리를 구한 후, 그 중 최댓값이 그 날에 대한 수치가 되는 것이다. 문제에서는 각 날별로 두 별의 거리를 구하는 것이지만 일단 관점을 바꿔서 두 별의 거리를 각 날별로 관찰해보자. V자. 이런식으로 나올것이다. 즉, 일정 시점까지는 두 별이 계속 가까워 졌다가, 일정 시점 이후부터는 계속 멀어질 것이다. 혹은 시간 구간 내에서는 계속 감소하거나 계속 증가할 수도 있다. 두 별에 대한 모든 거리 그래프를 겹친 후에 그 중 최댓값을 뽑아낸 그래프 G'를 생각..

BOJ 13302 고등부 1번 리조트 문제 링크 : https://www.acmicpc.net/problem/13302 문제 태그 더보기 DP 문제 풀이 각 주어진 상황에서 여러가지 조건 중 하나를 선택할 수 있으며, 선택을 통해서 최적의 결과를 얻어내야 하는 문제. -> 아무리 봐도 DP. 각 상태는 DP table에 저장하고, 선택할 수 있는 조건들은 DP 관계식으로써 표현할 수 있다. dp[i][j]를 i번째날 쿠폰을 j개 들고 있을 때, 사용한 돈의 최솟값 이라고 설정하면, 1일권을 산 경우, 3일권을 산 경우, 5일 권을 산 경우, 쿠폰을 쓴 경우에 대해서 각각 일수와 쿠폰 수의 변화를 생각하여 DP식 들을 여러개 만들어 주면 된다. 자세한 것은 아래의 코드를 참고하자. 평가 : 난이도는 확실히..

이번에는 자료구조의 성격을 띄고 있는 STL이 아닌 함수의 성질(?)을 띄고 있는 STL에 대해서 말하려고 한다. 바로 lower_bound와 upper_bound이다. lower_bound를 확실히 정리하려는 이유는 이상, 이하, 초과, 다음이 맨날 햇갈려서 항상 한번 긴가민가 하면서 코딩해보고 수정을 하기 때문이다. 엄청나게 시간소모를 하는것은 아니지만, 답이 틀릴때 마다 lower_bound에 확신이 없어 한 번 검토해야하는 것은 확실히 스트레스이다. ※ 배열은 1-base 기준입니다. lower_bound lower_bound는 범위내의 정렬된 자료들 내에서 원하는 원소보다 같거나 큰 첫 번째 위치를 찾아준다. 예를 들어서 벡터에 2 2 4 5 7 9가 있고, 이 벡터 전체에 대해서 7을 기준으로..

후기는 이글에 대회가 끝나고 나와보니 30분에 다 푼 사람, 35분에 다 푼 사람 38분에 다 푼 사람이 이미 나와 있었다. 그 밖에 나온 사람도 있었고, 마지막 제출을 하고 있었는데 그 바로 전에 짐을 싸고 일어난 사람도 있었다. 그래서 나는 내심 기대는 하면서도 5~6등을 예상했었다. 그리고 justiceHui에게 결과가 나왔다는 메시지를 받고 사이트에 들어가서 확인을 해봤다. 결과는 다음과 같았다.. ?? 결과적으로 4등. 은상을 받았다. 확실히 결과를 알고 있었던 30분, 35분, 38분에 푼 학생들이 각각 1,2,3등으로 대상, 금상, 은상을 받았다. 그래서 상을 보면 결국 38분을 푼 학생과 같은 상을 받게 되었다. 그리고 7등이 장려상인데 1시간 15분도 안되는 시간이었다. 결국 7분만 늦었..

문제 링크 : https://www.acmicpc.net/problem/17613 문제 풀이 일단 문제를 한 번 보자. "만일 점프간격을 2배씩 계속 증가시켜 마지막 점프에서 목표 수 x를 지나칠 것 같으면, 필요한 경우 언제든지 점프 간격을 다시 처음 상태인 간격 1로 되돌아 갈 수 있다. 이것을 재시작이라고 부른다." 라는 문구가 굉장히 중요한 부분이다. 굳이 이 문구를 통해서 유추를 할 필요는 없지만, 풀이를 생각하는 과정에서 이 문장은 풀이의 일부에 확신을 주게 된다. Phase 1 현재 개구리가 $2^i$ 까지 한 번에 뛰었다. 그리고 $2^{i+1}$을 뛸 수 있는 상황이다. 그런데 안 뛸 이유가 있을까? $2^{i+1}$은 1부터 $2^i$까지의 합보다 크다. 1번의 점프로 i번의 점프의 효..

문제 링크 : https://www.acmicpc.net/problem/17612 문제 풀이 딱히 사고의 흐름이라고 할 게 없다. 상황의 형태와 여러가지 조건들을 주어지고 이를 시뮬레이팅 할 수 있는 코드를 짜는 구현 문제이기 때문이다. 고객들이 어떤 순서로 나갈지를 알아내야 한다. 고객들은 번호 순으로 입장하고, 빈 구역이 있으면 바로 입장하며, 각 고객별로 주어진 시간만큼 있다가 퇴장한다. 이때 입장할 구역이 여러군데면 가장 작은 번호로 가며, 나갈 때는 동시에 끝나면 번호가 큰 순서대로 나간다. 정리하면 나가는 순서는 일련의 규칙을 따른다. 일련의 규칙에 따른 정렬 -> 우선순위 큐. 솔직히 따지고 보면 우선순위 큐 연습문제라고 봐도 무방하다. 동시에 자리가 나면 무조건 작은 번호의 구역으로 이동하..