티스토리

unordered_map이 PS하는 블로그
검색하기

블로그 홈

unordered_map이 PS하는 블로그

unorderedmap.tistory.com/m

unordered_map 님의 블로그입니다.

구독자
10
방명록 방문하기
공지 PS/수학 과외합니다 모두보기

주요 글 목록

  • HLD (Heavy Light Decomposition) https://justicehui.github.io/hard-algorithm/2020/01/24/hld/ : 이 글이 이론의 전반적인 이해에 큰 도움이 되었다. GOAT. 오일러 투어 테크닉, LCA 등의 쉬운 트리 이론은 트리 문제 하나로 전부 정리된다고 생각한다. 해당 문제를 풀 수 있으면 심화 트리 이론을 공부할 수 있는 것이고, 해당 문제를 풀 수 없다면 기초부터 다시 다지고 올라와야한다. 여기서 쉬운 트리 이론과 심화 트리 이론을 당당하게 나누어 말할 수 있는 이유는 난이도 차이가 실제로 매우 크기 때문이다. 심화 트리 이론의 첫 단계라고도 말할 수 있는 HLD는 쉬운 트리 이론은 물론이거니와 세그먼트 트리까지 완벽하게 장착하고 있어야 이해할 수 있는 이론이다. 반대로 말하면, 쉬운 트리 이론.. 공감수 1 댓글수 0 2024. 10. 8.
  • 1일 1트리 기록장 1일 1트리란?- 고등학교 2학년에서 3학년으로 넘어가는 겨울방학에 1일 1수쿼 프로젝트를 진행하여 하루에 수열과 쿼리 문제를 하나 이상 해결하거나 풀이를 정리하는 과제를 스스로에게 부여하여 1달 조금 넘게 진행하였다. 당시의 기억이 행복하게 남아있기도 하고, PS를 거의 2년간 쉰 지금 아직도 수쿼 관련된 자구들은 기억에 남아있는 것을 보아 학습효과도 상당히 좋았던 것 같다.- 이를 이어 오늘부터 1일 1트리를 진행하려고 한다!- 는 아니고... 사실 지금 학기 중이고 곧 시험기간이라 많이 바쁘다. - 아직 PS를 본격적으로 공부해보지 않은 친한 친구들과 팀을 꾸려 ICPC에 나가게 되었다. 나도 PS를 오래 쉬었으니 인터넷 예선을 통과하여 리저널을 찍먹하는 것이 목표이다.- 팀원 중 한 명이 원래 수.. 공감수 6 댓글수 0 2024. 10. 2.
  • 2023 SCPC 2차 예선 후기 + 본선 진출 컷 분석 총점 : 100/200/90/180/60 = 630 [본선 진출] 1. 동아리의 아주 중요한 일정과 겹쳐 대회를 정상적으로 치지 못했다. 2. 1/2번이 쉬웠고 4/5번의 최대 서브태스크가 자명이었는데, 3번과 4번의 점수에 따라 갈릴 것 같다. 3. 본선 진출 컷은 630점 또는 585점의 상위권 어딘가 될 확률이 높다. [실제로 585에서도 본선 진출 소식이 들려왔다] 이 블로그에 게시글이 올라오는 빈도가 줄어든 것으로도 알 수 있듯이, 대학 진학 후 PS를 거의 손에서 놨다. 친구들과 많이 놀러다니기도 하고, 동아리 활동도 열심히 하면서 세상에서 제일 한가하다는 새내기의 삶을 맘껏 체험했다. 그럼에도 PS는 앞으로 과외를 위해서라도 아예 놓을 수는 없었고, SCPC와 같이 상금이 큰 대회를 위해서라.. 공감수 2 댓글수 1 2023. 8. 24.
  • 2022 나코더 송년대회 후기 결과 : 2위 (6솔, 시간페널티 803분) https://unorderedmap.tistory.com/9 2021 나코더 송년대회 후기 결과 : 2위 (7솔,시간페널티 922분) 나코더 송년대회는 경기과학고등학교의 PS 동아리 '나는코더다'에서 주최하는 연례 행사이다. 카카오, 넥슨 등의 후원을 받아 진행되어 상품도 푸짐하여 경기과 unorderedmap.tistory.com 작년에는 온라인으로 진행되었던 나코더 송년대회가 학교 강당에서 오프라인으로 진행되었다. 많은 친구들이 강당에 모여서 피자도 먹고 코딩도 하니 대회보다는 축제 분위기에 더 가까웠던 것 같다. 출제를 해준 mathking1021, jbkmath48128, donghwa722, ftkbrian, sciencepark은 모두 같은 기수 .. 공감수 0 댓글수 0 2023. 1. 4.
  • 한국정보올림피아드(KOI 2022) 2차 시험 후기 총점: 100/100/14/34=248 (동상, 13.37%, 25위) 1. 1, 2번이 쉽지만은 않았던 시험 2. 마지막 득점 시간 "2시간 24분" 3. TC35에서 TLE 보통 KOI 2차 시험에는 1번, 2번에 조금의 노력만으로 100점을 받을 수 있는 문제가 나오고, 3번, 4번에 변별력 있는 서브태스크들을 가진 문제가 나온다. 그래서 수상권에서의 등수는 3번, 4번에서 부분점수를 얼마나 긁었느냐에 따라 결정된다. 그런데 최근 들어 1번, 2번의 문제 난이도가 심상치 않다. 물론 조금 고민하면 풀 수 있는 문제이긴 하지만, 문제를 처음 읽고 나서 조금 당황하게 되는 수준이다. 이에 따라 나는 집중력이 가장 높은 초반부에 3번, 4번 서브태스크들을 잡고, 조금 집중력이 떨어진 시기에 1번, 2번을.. 공감수 2 댓글수 2 2022. 7. 17.
  • 아시아 태평양 정보올림피아드(APIO 2022) 후기 총점 : 14 + 60 + 93.7 = 167.7 (한국 기준 10등, Unofficial 동상) 1. 2번과 3번은 변별력이 크지 않아서 1번 점수에 따라 시험의 성패가 갈렸다. 2. 그런데 1번이 딱히 좋은 문제인지는 모르겠다... 3. 작년보다 쉬운 난이도로 숨통은 좀 트이는 시험이었다. APIO 2021에서 5시간 동안 머리를 싸매고 얻은 결과가 40점대였기에, APIO라는 시험에 대해 그렇게 좋은 기억이 있지는 않았다. 또한 한국 6등까지만 수상이 가능한데 수많은 계절학교 모의고사 및 선발고사에서 한 셋 기준으로 6등 안에 들어본 기억이 없기에, 참가에 의의를 두고 즐겁게 참여했다. 원래는 KMO 다음 날 보려고 했는데, KMO를 생각보다 잘 봐서 머리 컨디션이 좋다고 판단하고 당일 밤에 응시하.. 공감수 4 댓글수 0 2022. 5. 30.
  • 한국수학올림피아드(KMO 2022) 고등부 가우스부 1차 시험 후기 총점 : 1교시 46 + 2교시 40 = 86 (상위 5%, 금상) 1. 문제들이 쉬워서 금컷을 90점대로 예상한다. 2. 계산 실수를 하지 않아서 준비를 안했음에도 점수가 잘 나왔다. 3. 6점은 다 맞혔지만 4점은 하나 틀렸다... unordered_map이 PS하는 블로그 이지만 나는 중학교 때까지 수올러였다. (이 블로그의 첫 글인 소개 글을 보면 알 수 있다.) 3년 동안 수올에 손을 놓고 있다가, 문득 이번이 수올을 볼 마지막 기회라는 걸 깨달았다. 그래서 준비 단 1분도 하지 않고, 오로지 참가에 의의를 두고 마지막 수올을 응시했다. 그렇게 부담 없이 봐서 그런지 계산실수도 하나도 안했고, 점수가 생각보다 잘 나와서 2차에는 갈 것 같다. 상의 색은 7월 4일에 결과가 발표하는 대로 이 글 .. 공감수 4 댓글수 1 2022. 5. 30.
  • 한국정보올림피아드(KOI 2022) 1차 시험 후기 총점 : 1교시 139 + 2교시 213 = 352 (가채점 결과 3.467%, 77등, 은상) 1. 1교시가 어려웠다. 2. 2교시가 많이 망한줄 알았으나 생각만큼 망한건 아니었다. 3. 2교시 3번은 Dumae와 거의 같은 문제이다. 작년에 플5짜리 문자열 문제를 못 풀고 1차 탑골드를 놓쳐 많이 아쉬웠다. 비버챌린지는 196.xx점이어서 실수한 소문제 2개에서만 감점이 있었기에, 이번에도 2교시가 지난 해와 비슷한 난이도로 나오면 만점에 가까운 점수로 탑골드를 노릴 수 있다고 생각하고 시험에 들어갔다. 1교시. 비버챌린지형(200점) - 킬러 문제 및 배점이 큰 문제에는 굵은 글씨를 해두었다. 총평 - 단답형 12번이 어려웠고, 시뮬레이션형 문제 17, 19, 20번 난이도가 작년 기준 가장 어려운.. 공감수 8 댓글수 1 2022. 5. 16.
  • solved.ac 다이아1 달성 후기 다이아2가 된지 한 달 정도 후에 다이아1에 올라왔다. 사실 학기 시작 전에 달성했는데 글 작성하는 것을 까먹어서 작성을 안하고 있었다. 학기가 시작한만큼 앞으로는 PS에 투자할 시간이 거의 없을 것 같다. 브론즈 풀면서 스트릭 유지나 해야할 것 같다. 레이팅 상승 요인은 PST + PBS + Splay Tree로 요약할 수 있겠다. 특히 스플레이 트리에 큰 흥미를 느껴 거의 10문제 정도 푼거 같은데, 스플레이 트리 기본 티어가 D3이라 레이팅이 빠르게 올랐던 것 같다. 앞으로 루5를 찍을 일이 있을지조차 모르겠다. 여름방학에 PS를 하더라도 새로운 알고리즘을 배우고 어려운 문제를 풀기 보다는 랜덤 디펜스를 할 것 같다. 곧 있을 국대 선발고사 2차 준비나 잘 해야할 것 같다. 공감수 1 댓글수 0 2022. 3. 7.
  • Codeforces Master 달성 후기 최근 7시에 진행되었던 딥1-딥2 분리형 코포를 제외하고 방학 내내 모든 코포에 참여하였고, 그 대가로 이름표를 주황색으로 칠할 수 있게 되었다. 아마 학기 중 코포는 웬만하면 참여하지 않을 것 같고, 참여하더라도 아직 블루인 부계정으로 참여할 것 같다. 위의 표에서 알 수 있듯이 이번 방학에 레이팅의 진폭이 많이 컸다. 01.22 +210을 기록했던 Round 767은 처음으로 저렇게 높은 점수를 기록했다는 사실에 감격하여 글로 남겼었다. (https://unorderedmap.tistory.com/10 참고) 이 때까지만 해도 오렌지까지 12만 남은 상황이었고, 곧 오렌지에 갈 수 있을 줄 알았다... 01.30~31 그 희망은 산산조각 났다. 사실 30일 코포에는 그냥 내 실력보다 조금 안 나온 정.. 공감수 5 댓글수 0 2022. 2. 28.
  • 수열과 쿼리 13 [BOJ 13925] Lazy propagation을 여러 가지 쿼리를 통해 전파하는 경우 어떤 것을 먼저 전파할지 결정하는 것이 매우 중요하다. 하지만 이 문제에서는 3개의 쿼리가 어떤 하나의 쿼리의 일부가 된다. 이를 인지하면 구현량도 많이 줄일 수 있어 실수도 덜 나오고 빠르게 풀 수 있다. 그리고 이 문제가 D5가 박혀있지만 플래 기여가 상당히 많고, 이제 플래로 내려올 때가 된 것 같다. D5 티어에 쫄지 말고 아이디어를 잡기 위해 노력해보자. 문제 요약 길이 10만 이하의 수열 A에 대해 다음 4가지 쿼리를 수행한다. 1 x y v : 구간 [x, y]에 속한 모든 i에 대해 A[i]=(A[i]+v)%MOD 적용 2 x y v : 구간 [x, y]에 속한 모든 i에 대해 A[i]=(A[i]*v)%MOD 적용 3 x.. 공감수 0 댓글수 1 2022. 2. 28.
  • 수열과 쿼리 39 [BOJ 19651] 수쿼 스타일의 문제를 보다보면 특정 구간에 등차수열을 더하거나, 피보나치 수열을 더하는 등의 문제를 볼 수 있다. 이 문제를 통해 등차수열에 관한 쿼리는 어떻게 처리하는지 익혀보길 바란다. 그리고 다이아라고 되어있긴 한데 왜 다이아인지 전혀 모르겠다. 플1 정도가 적당해보이고, 사람에 따라 더 내려서 생각할 수도 있을 것 같다. 푸른색 티어에 겁먹지 말고 도전해보자. 문제 요약 길이 10만 이하의 수열 A에서 다음 2가지 쿼리를 수행한다. 1 i j x y : 구간 [i, j]에 초항이 x이고 공차가 y인 등차수열 더하기 2 i j : 구간 [i, j]에 포함되는 등차수열인 구간 [l, r] 중 가장 긴 것의 길이를 출력 사용 알고리즘 금광 세그 풀이 태그에 레이지가 달려있긴 한데 사실 레이지가 필수적이.. 공감수 0 댓글수 0 2022. 2. 24.
  • 수열과 쿼리 7 [BOJ 13550] 수열과 쿼리 0과 수열과 쿼리 4와 같은 문제이다. 정확히는 수열과 쿼리 0에서 mod K만 씌우면 된다. 수열과 쿼리 0의 풀이 링크로 이 문제의 풀이를 대체한다. https://unorderedmap.tistory.com/34 수열과 쿼리 0 [BOJ 13545] 수열과 쿼리 4와 수열과 쿼리 7과 같은 문제이다. 수열과 쿼리 4가 가장 기본형 문제이므로 수열과 쿼리 4를 풀면 이 문제도 자연스럽게 풀린다. 수열과 쿼리 4의 풀이 링크는 아래에 있다. https://u unorderedmap.tistory.com 코드 더보기 #include #define SIZE 100003 typedef long long ll; using namespace std; struct Query { int id, s, e.. 공감수 0 댓글수 0 2022. 2. 22.
  • 수열과 쿼리 0 [BOJ 13545] 수열과 쿼리 4와 수열과 쿼리 7과 같은 문제이다. 수열과 쿼리 4가 가장 기본형 문제이므로 수열과 쿼리 4를 풀면 이 문제도 자연스럽게 풀린다. 수열과 쿼리 4의 풀이 링크는 아래에 있다. https://unorderedmap.tistory.com/33 수열과 쿼리 4 [BOJ 13546] 수열과 쿼리 0과 수열과 쿼리 7과 같은 문제인데, 이 문제가 가장 기본형인 것 같다. 수열과 쿼리 6의 응용 버전이기도 하다. 이 문제의 풀이를 모르겠다면 수열과 쿼리 6을 먼저 풀어보기 바란다. unorderedmap.tistory.com 문제 요약 1과 -1로만 이루어진 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. i j : 구간 [i, j]에 포함되는 구간 중 구간합이 0인 가장 긴 구간의 길이 출.. 공감수 0 댓글수 0 2022. 2. 22.
  • 수열과 쿼리 4 [BOJ 13546] 수열과 쿼리 0과 수열과 쿼리 7과 같은 문제인데, 이 문제가 가장 기본형인 것 같다. 수열과 쿼리 6의 응용 버전이기도 하다. 이 문제의 풀이를 모르겠다면 수열과 쿼리 6을 먼저 풀어보기 바란다. 아래는 수열과 쿼리 6 풀이 링크이다. https://unorderedmap.tistory.com/31 수열과 쿼리 6 [BOJ 13548] 티어가 하나 낮은 수열과 쿼리 5의 풀이를 확장한다. 수쿼 5를 아직 안 풀었다면 이 문제와 같이 푸는 것을 추천한다. 아래는 수열과 쿼리 5의 풀이가 담긴 링크이다. https://unorderedmap.tistory.com/28 unorderedmap.tistory.com 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. (단, 수열의 각 원소는 10.. 공감수 0 댓글수 0 2022. 2. 22.
  • 수열과 쿼리 11 [BOJ 13704] 재밌는데 고려할게 많아서 조금 귀찮다. 처음 풀 때는 12번만에 맞았고, 다시 풀 때도 한 번 틀렸다. 디테일한 구현을 많이 해보지 않았다면 한 번에 AC를 받기에는 어려울 수도 있는 문제이기에 비슷한 난이도의 아이디어를 가진 문제들보다 더 높은 티어를 받은 것 같다. 문제 요약 길이 10만 이하의 수열 A와 100만 이하의 수 K에 대하여 다음 쿼리를 수행한다. l r : 구간 [l, r]에 포함되는 구간 [i, j] 중 A[i]^A[i+1]^...^A[j]=K인 구간의 수를 출력 사용 알고리즘 Mo's Algorithm 풀이 XOR의 성질에 따라 어떤 구간의 XOR 값은 누적 XOR을 통해 O(N)에 전처리하여 O(1)에 구할 수 있다. B[i]를 A[1]^...^A[i]라고 하면, A[i]^...^.. 공감수 0 댓글수 0 2022. 2. 20.
  • 수열과 쿼리 6 [BOJ 13548] 티어가 하나 낮은 수열과 쿼리 5의 풀이를 확장한다. 수쿼 5를 아직 안 풀었다면 이 문제와 같이 푸는 것을 추천한다. 아래는 수열과 쿼리 5의 풀이가 담긴 링크이다. https://unorderedmap.tistory.com/28 수열과 쿼리 5 [BOJ 13547] 서로 다른 수에 대한 쿼리를 다루는 문제 중 쉬운 문제로, 어려운 아이디어 없이도 해결할 수 있다. 이게 왜 P2일까...? 더 많은 풀이가 존재한다고 하는데, 필자의 풀이는 쉽다고 생각하여 P4를 기 unorderedmap.tistory.com 문제 요약 길이 10만 이하의 수열 A에 대해 다음 쿼리를 수행한다. i j : 구간 [i, j]에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다. 사용 알고리즘 Mo's Algorithm .. 공감수 0 댓글수 0 2022. 2. 19.
  • 수열과 쿼리 1.5 [BOJ 17410] 수열과 쿼리 18과 완전히 같은 문제이다. 아래 링크에는 수열과 쿼리 18에 대한 설명이 있다. https://unorderedmap.tistory.com/27 수열과 쿼리 18 [BOJ 14504] 수열과 쿼리 3 문제는 머지 소트 트리를 이용해 해결할 수 있다. 아직 안 풀어봤다면 수열과 쿼리 3을 꼭 먼저 풀고, 수열과 쿼리 18에서 업데이트 쿼리를 어떻게 적용할 수 있을지 생각해보자. 여 unorderedmap.tistory.com 공감수 0 댓글수 0 2022. 2. 19.
  • 수열과 쿼리 38 [BOJ 18917] 실버도 문제다! 문제 요약 처음에 0이 하나 포함되어있는 배열 A에서 다음 4가지 쿼리를 수행한다. 1 x : 수열 맨 뒤에 x 추가 2 x : 수열에서 가장 앞에 있는 x 하나 제거 3 : 수열 원소 합 출력 4 : 수열 원소 XOR 출력 사용 알고리즘 없음 풀이 XOR의 성질에 따라 a^b^c^...^z에서 a^b^c^...^y를 구하고 싶으면 (a^b^c^...^z)^z를 하면 된다. XOR은 교환법칙과 결합법칙이 모두 성립하기 때문이다. 따라서 1, 2번 연산을 하면서 수열 원소 합/수열 원소 XOR을 관리해줄 수 있고, 출력만 하면 된다. 1번 쿼리에서 '맨 뒤에 추가', 2번 쿼리에서 '가장 앞에 있는 것 하나 제거'와 같은 내용은 문제를 거창하게 만들기 위한 도구이니 가볍게 무시해주자. 코드.. 공감수 0 댓글수 0 2022. 2. 18.
  • 수열과 쿼리 5 [BOJ 13547] 서로 다른 수에 대한 쿼리를 다루는 문제 중 쉬운 문제로, 어려운 아이디어 없이도 해결할 수 있다. 이게 왜 P2일까...? 더 많은 풀이가 존재한다고 하는데, 필자의 풀이는 쉽다고 생각하여 P4를 기여했다. 풀고 난 뒤 다른 사람 코드를 보며 이 문제를 푸는 다른 방법에 대해 찾아보는 것도 재미있다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. i j : 구간 [i, j]에 존재하는 서로 다른 수의 개수를 출력 사용 알고리즘 Mo's Algorithm 풀이 Mo's Algorithm을 사용하여 쿼리를 처리할 것이고, 새로운 배열 B[]와 변수 result를 관리할 것이다. B[i]는 해당 구간에 들어있는 숫자 i의 개수, result는 해당 구간에 들어있는 서로 다른 숫자의 개수이.. 공감수 0 댓글수 0 2022. 2. 17.
  • 수열과 쿼리 18 [BOJ 14504] 수열과 쿼리 3 문제는 머지 소트 트리를 이용해 해결할 수 있다. 아직 안 풀어봤다면 수열과 쿼리 3을 꼭 먼저 풀고, 수열과 쿼리 18에서 업데이트 쿼리를 어떻게 적용할 수 있을지 생각해보자. 여담으로, 이 문제는 수열과 쿼리 1.5와 완전히 같은 문제이다. 문제 요약 길이 10만 이하의 수열 A에서 다음 2가지 쿼리를 수행한다. 1 i j k : 구간 [i, j]에서 A의 원소 중 k보다 큰 것의 개수를 출력 2 i k : A[i]=k로 업데이트 사용 알고리즘 제곱근 분할법 풀이 k보다 큰 원소의 수를 lower_bound나 upper_bound를 이용하여 구하겠다는 발상까지는 머지 소트 트리와 같다. 하지만 업데이트 쿼리가 들어온다면 기존의 머지 소트 트리에서 O(logN)개의 정렬된 vector를.. 공감수 1 댓글수 0 2022. 2. 16.
  • 수열과 쿼리 23 [BOJ 16979] 수열과 쿼리 8, 9와 함께 풀면 좋은 문제이다. 아직 안 풀었다면 함께 풀어보는 것을 추천한다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. s e : 구간 [s, e]에 존재하는 iAj인 (i, j) 쌍의 수를 출력 사용 알고리즘 펜윅 트리 Mo's Algorithm 풀이 어떤 수열에 대해 쿼리 1 N을 처리해보자. 이를 처리하는 것은 어렵지 않다. 처음 원소부터 하나씩 세그먼트 트리에 넣으면서, 이미 들어간 원소 중 자신보다 큰 원소의 수를 쿼리로 세주면 된다. 시간복잡도는 O(NlogN)이다. 이를 통해 우리는 쿼리를 처리하기 위해서 어떤 구간의 모든 수를 담고 있는 세그먼트 트리가 있어야한다는 사실을 알 수 있다. 그렇다면 이를 Mo's Algorithm으로 쿼리와 쿼리 사.. 공감수 0 댓글수 0 2022. 2. 13.
  • 수열과 쿼리 20 [BOJ 16903] 수열에서 XOR 쿼리를 처리할 때 많이 사용하는 테크닉으로, 알아두면 좋다. 이 방법에 대해 조금 더 연습하고 싶다면 https://www.acmicpc.net/problem/20919 문제도 추천한다. 수열과 쿼리 20이 P2, 소개한 20919 문제가 P3로 되어있는데, 개인적으로 이 문제가 20919의 하위호환이라고 느껴 이 문제에는 P4를 기여했다. 그만큼 어려운 문제가 아니니 상위 플래 티어를 보고 쫄지 말고 스스로 고민하여 풀어보자. 문제 요약 0이 하나 포함되어 있는 배열 A에 다음 쿼리들을 20만 번 이하로 수행한다. 1 x : A에 x를 추가 2 x : A에 x를 제거(여러 개 있으면 하나만 제거) 3 x : A의 원소 A[i]들 중에서 A[i]^x의 최댓값을 출력 사용 알고리즘 트라이를.. 공감수 0 댓글수 0 2022. 2. 11.
  • 수열과 쿼리 3 [BOJ 13544] 수열과 쿼리 1과 정확히 같은 문제이지만 쿼리 정렬을 할 수 없다는 점만 다르다. 머지 소트 트리를 필수적으로 구현해야하는 문제이다. 수열과 쿼리 1을 머지 소트 트리로 풀었다면 그대로 제출하면 된다. 따라서 별도의 풀이는 적지 않고, 아래에 수열과 쿼리 1 풀이 링크를 걸어두겠다. 아직 수열과 쿼리 1을 풀지 못했다면 쿼리 정렬을 사용해서는 어떻게 풀 수 있는지 고민해보기 바란다. 수열과 쿼리 1 풀이링크 https://unorderedmap.tistory.com/23 수열과 쿼리 1 [BOJ 13537] 수쿼 시리즈의 화려한 도약을 알리는 매우 재미있는 문제이다. 머지 소트 트리 기본 문제이면서도, 이 문제는 머지 소트 트리 외에 별해가 존재한다. 개인적으로 별해의 아이디어가 상당히 의미 unorde.. 공감수 0 댓글수 0 2022. 2. 9.
  • 수열과 쿼리 1 [BOJ 13537] 수쿼 시리즈의 화려한 도약을 알리는 매우 재미있는 문제이다. 머지 소트 트리 기본 문제이면서도, 이 문제는 머지 소트 트리 외에 별해가 존재한다. 개인적으로 별해의 아이디어가 상당히 의미 있다고 생각한다. 아래 풀이에 별해와 관련된 내용은 모두 가려놓았으니, 최소 30분 정도는 별해에 대해 고민해보는 것을 추천한다. ** 수열과 쿼리 3 풀다가 오신 분들은 머지 소트 트리에 대한 풀이인 풀이 1만 읽으면 수열과 쿼리 3을 풀 수 있다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. i j k : 구간 [i, j]에서 k보다 큰 원소의 수를 출력한다. 사용 알고리즘 풀이 1) 머지 소트 트리 풀이 2) Hint : 오프라인 쿼리라는 점을 이용 더보기 스위핑 + 세그먼트 트리 풀이 풀이 .. 공감수 0 댓글수 0 2022. 2. 9.
  • 수열과 쿼리 8 [BOJ 13553] Mo's Algorithm과 세그먼트 트리가 완전히 체화되어 있다면 쉽게 풀 수 있는 문제이지만, 그게 아니라면 아이디어를 떠올리기 조금 힘들다. 그래서 별 다른 아이디어 없이도 P1의 티어를 받은 것 같다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. l r : 구간 [l, r]에 있는 i, j(i 공감수 0 댓글수 0 2022. 2. 7.
  • 수열과 쿼리 10 [BOJ 13557] 금광 세그를 연습하기에 매우 좋은 문제이다. 개인적으로 처음에는 아이디어 떠올리는 것이 어려웠기 때문에 풀이를 조금 읽다가 아이디어가 잡히면 남은 풀이는 혼자 완성해보는 것을 추천한다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. x1 y1 x2 y2 : 구간 [x1, y1]에 속하는 모든 i와 구간 [x2, y2]에 속하는 모든 j(>=i)에 대해서 수열의 [i, j] 구간합의 최댓값을 출력한다. 사용 알고리즘 금광 세그 풀이 금광 세그를 구현하면 임의의 구간 [i, j]에서 수열의 prefix 최대합, suffix 최대합, 부분 최대 합, 전체 합을 O(logN)에 구할 수 있다. 각 값을 구간의 left, right, ans, all이라고 하자. ① [x1, y1]과 [x2, .. 공감수 0 댓글수 0 2022. 2. 6.
  • 수열과 쿼리 22 [BOJ 16978] '쿼리를 정렬'한다는 것은 세그먼트 트리를 처음 배우는 입장에서 쉽게 떠올릴 수 있는 것은 아니다. 하지만 해당 문제처럼 쿼리의 순서가 무의미할 때나 업데이트가 없는 오프라인 쿼리일 때는 매우 자주 이용하며, Mo's Algorithm의 기둥 중 하나가 되기도 한다. 또한 퍼시스턴트 세그먼트 트리로 조금 더 어렵게 풀 수 있기 때문에 퍼시스턴트 세그먼트 트리를 처음 배우는 사람들에게도 매우 좋은 문제이다. 현재는 쿼리 정렬 풀이만 올려놓았는데, 나중에 기회가 되면 퍼시스턴트 세그먼트 트리를 이용한 풀이도 업로드할 예정이다. 문제 요약 길이 10만 이하의 수열 A에서 다음 2가지 쿼리를 수행한다. 1 i v : A[i]=v로 update 2 k i j : k번째 update 쿼리까지 적용되었을 때 수열 A.. 공감수 0 댓글수 0 2022. 2. 4.
  • 수열과 쿼리 21 [BOJ 16975] 레이지 세그를 구현할 수 있는지를 테스트하는 문제이다. 문제 요약 길이 10만 이하의 수열 A에서 다음 2가지 쿼리를 처리한다. 1 i j k : 수열 A의 구간 [i, j]에 k를 더한다. 2 x : A[x]를 출력한다. 사용 알고리즘 Lazy propagation을 이용한 세그먼트 트리 풀이 Lazy propagation을 이용한 세그먼트 트리를 그대로 구현해주면 된다. 나도 처음에는 구현하기 힘들었는데, 구현이 힘들어도 너무 좌절하지 말고 계속 구현해보는 것을 추천한다. 초반에는 다른 사람의 코드를 거의 따라치다시피 해도 좋으니 정상적으로 작동하는 코드를 완성하는 것에 의의를 두는 것이 좋다. 한 번 이해하기 시작하면 활용도가 매우 높아 PS할 때 많은 도움이 된다. 코드 더보기 더보기 #inclu.. 공감수 0 댓글수 0 2022. 2. 4.
  • 수열과 쿼리 37 [BOJ 18436] 세그먼트 트리 기초 문제이다. 이 문제를 보고 풀이를 떠올리지 못했다면 세그먼트 트리에 대한 기초를 다시 공부하기를 추천한다. 문제 요약 길이 10만 이하의 수열 A에서 3가지 쿼리를 수행한다. 1 i x : A[i]를 x로 update 2 l r : 구간 [l, r]에 존재하는 A[i] 중 짝수의 개수 출력 3 l r : 구간 [l, r]에 존재하는 A[i] 중 홀수의 개수 출력 사용 알고리즘 세그먼트 트리 풀이 2번 쿼리와 3번 쿼리 중 하나만 해결하면 나머지 쿼리도 해결할 수 있다. 홀수의 개수를 알면 구간에 있는 전체 수의 개수에서 홀수의 개수를 빼서 짝수의 개수를 계산할 수 있기 때문이다. 우리가 알아야하는 것은 구간에 존재하는 '홀수의 개수'의 구간합이기 때문에, 각 수를 2로 나눈 나머지를 .. 공감수 0 댓글수 0 2022. 2. 2.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.