unordered_map이 PS하는 블로그

세그먼트 트리 응용을 막 시작한 사람들에게 추천하는 문제이다. 세그먼트 트리 배우고 얼마 지나지 않아서는 최댓값/최솟값/구간 합 말고는 세그먼트 트리를 떠올리기 어려운데, 더 심화된 응용의 세그먼트 트리를 쓰려면 이런 간단한 응용들로부터 시작하여야 한다고 생각한다. 문제 요약 길이 10만 이하의 수열 A에서 2가지 쿼리를 수행한다. 1 i v : A[i]를 v로 바꾼다 2 l r : l1; init(l,mid,node

멀다고 느꼈던 다이아2에 생각보다 금방 올라왔다. 2학년 2학기 때 내신을 챙기느라 PS를 거의 못하였고, 참고 있던 것들이 봇물 터지듯이 폭발하면서 종강 이후 미친듯이 PS를 했다. 물론 3학년 1학기 내신을 챙겨야할 시기이기 때문에 적당히 조절하고 있지만, 지금도 하루에 1시간~2시간 정도는 시간 내서 하려고 한다. 1월 1일~1월 9일 : 센트로이드 분할과 DnC Opt를 공부한 후 연습문제를 풀며 티어가 많이 올랐다. 당시 100문제 중 최저 티어가 P3이었는데, 센트로이드 분할 문제는 D5~D4, DnC Opt 문제는 P1 정도에 티어가 형성되어 있어 문제를 풀 때마다 레이팅이 올랐다. 그리고 CLASS 8을 따려는 마음은 없었는데, 어느새 14문제가 풀려 있어 6문제만 더 풀면 딸 수 있다는 ..

이 문제는 내가 N달 동안 고민한 문제로, 자구충이라면 다4 수쿼 정도는 풀 수 있어야하지 않을까 싶어서 업솔빙도 안했다. 그리고 최근에 다시 고민을 하다가 문제를 푸는데에 핵심적인 아이디어를 떠올려 풀 수 있게 되었다. vector의 몇 안되는 다이아 이상 자력솔 중 하나이다. 문제 요약 길이 10만 이하의 수열 A, B에서 다음 쿼리를 수행한다. i j k : i

https://unorderedmap.tistory.com/12 수열과 쿼리 16 [BOJ 14428] https://unorderedmap.tistory.com/11 수열과 쿼리 15 [BOJ 14427] 오늘부터 1일 1수쿼 도전을 하려고 한다. 안 풀었던 수열과 쿼리 문제 중 하나를 풀거나, 푼 수열과 쿼리 문제 중 하나의 풀이를 작성하는 것 unorderedmap.tistory.com 수열과 쿼리 15, 16과 거의 같은 문제이다. 단, 최솟값의 인덱스가 아니라 최솟값만을 구한다는 점에서 조금 다르다. 문제 요약 길이 10만 이하의 수열에서 2가지 쿼리를 수행한다. 1 i v : i번째 값을 v로 바꾼다. 2 i j : 수열의 i번째 원소부터 j번째 원소까지 중에서 최솟값을 출력한다. https:..

수쿼란? - "수열과 쿼리"의 줄임말 - BOJ에는 "수열과 쿼리 1"부터 시작하여 "수열과 쿼리 40"까지 다양한 수쿼 문제가 있다. ("수열과 쿼리 0", "수열과 쿼리 1.5", "수열과 시프트 쿼리", "하이퍼 수열과 하이퍼 쿼리" 등 다양한 뇌절과 쿼리들도 있다.) - 보통 다양한 종류의 세그먼트 트리를 사용하며, 가끔 mo's나 다른 알고리즘을 사용하는 문제도 있다. 개인적으로 자료구조 공부하는 데에 많은 도움이 되었다. - PS에서 많은 문제들이 주요 아이디어 혹은 부수적인 도구로 세그먼트 트리를 사용하기에, 다양한 수쿼 문제들을 통해 문제에서 어떤 상황에 세그먼트 트리를 적용할 수 있는지 판단하는 능력을 기를 수 있다고 생각한다. - TMI : boj.kr/seqquery##이라고 URL에..

https://unorderedmap.tistory.com/11 수열과 쿼리 15 [BOJ 14427] 오늘부터 1일 1수쿼 도전을 하려고 한다. 안 풀었던 수열과 쿼리 문제 중 하나를 풀거나, 푼 수열과 쿼리 문제 중 하나의 풀이를 작성하는 것 중 하나를 매일 할 것이다. (할 수 있을까...?) 문제 요 unorderedmap.tistory.com 수열과 쿼리 15와 거의 같은 문제이나, 조건 하나가 추가되었다. 문제 요약 길이 10만 이하의 수열에서 2가지 쿼리를 수행한다. 1 i v : i번째 값을 v로 바꾼다. 2 i j : 수열의 i번째 원소부터 j번 원소까지 중에서 가장 작은 값을 가지는 인덱스를 출력한다. 단, 최솟값이 여러 개일 경우 가장 작은 인덱스를 출력한다. https://www.a..

오늘부터 1일 1수쿼 도전을 하려고 한다. 안 풀었던 수열과 쿼리 문제 중 하나를 풀거나, 푼 수열과 쿼리 문제 중 하나의 풀이를 작성하는 것 중 하나를 매일 할 것이다. (할 수 있을까...?) 문제 요약 길이 10만 이하의 수열에서 2가지 쿼리를 수행한다. 1 i v : i번째 값을 v로 바꾼다. 2 : 수열에서 가장 작은 값을 가지는 인덱스를 출력한다. 단, 최솟값이 여러 개일 경우 가장 작은 인덱스를 출력한다. https://www.acmicpc.net/problem/14427 사용 알고리즘 세그먼트 트리 풀이 pair을 담는 세그먼트 트리를 잡자. first에는 해당 구간의 최솟값, second에는 해당 구간에서 최솟값을 가지는 가장 작은 인덱스를 저장한다. pair은 크기 비교 시 first가..

어느덧 코포를 시작한지도 열 달, 26번째 코포를 치르게 되었다. 6개월 가까이 블루-퍼플을 반복하며 많이 지친 상태였고, IOI 국대 선발고사 전날이라 할지말지 많은 고민을 했다. 그래도 선발고사가 아침이 아닌 낮 1시에 시작하고, 방학 이후로 한 번도 빠지지 않고 제 시간에 코포를 했던 기록도 깨고 싶지 않아서 참여하게 되었는데, 안 했으면 후회했을만한 기록이 나왔다. 그래서 평소에 안 쓰던 코포 후기를 써보려고 한다. 결과 : 7문제 중 6솔, 전체 7등(Carrot 기준 퍼포 2679, 델타 +210) 레이팅 변화 : 1878 -> 2088 이 날은 딥1이 함께 있는 날이어서 언레로 참여하는 오렌지 이상의 유저들과 레이티드 퍼플 유저들이 모두 딥1으로 갔고, 이에 따라 딥2에는 블루 이하만 남게 ..

결과 : 2위 (7솔,시간페널티 922분) 나코더 송년대회는 경기과학고등학교의 PS 동아리 '나는코더다'에서 주최하는 연례 행사이다. 카카오, 넥슨 등의 후원을 받아 진행되어 상품도 푸짐하여 경기과학고등학교의 많은 학생들이 참가하며, 이후에 열린 오픈 콘테스트에도 재학생이 아닌 분들이 많은 관심을 가지고 참여해주신 것으로 알고 있다. 이 대회를 준비해주신 출제진, 검수진, 그리고 후원자분들께 감사드린다. 필자가 속한 팀은 "본선도 좋은 결과가 있으면 좋을 것 같습니다"라는 팀으로, 팀명은 우리 팀원 중 한 명이 NYPC2020 현장스케치에서 인터뷰했던 대사를 그대로 활용하였다. (궁금하면 유튜브에 영상을 찾아보길 바란다.) 팀은 다양한 대회에서 준수한 성적을 거두며 유력한 국가대표 후보로 지목받고 있는 ..

결과 : 173점(100/54/15/0/4) / 특별상(레벨업상) NYPC 2021 예선대회에서 1414점을 받고 본선에 진출하였다. 원래 갈 실력이 아닌데 꼭 본선에 진출하고 싶었던 대회라서 예선 기간동안 정말 열심히 문제를 풀었고, 동점자 가르기 용도의 Output Only 12번 생존신호에서 만점을 받은 것도 진출에 한 몫을 한 것 같다. 본선대회는 NEXON 사옥에서 진행되었으며, 1214 부문의 12명과 1519 부문의 28명을 합친 40명보다 더 많은 수의 카메라와 스탭이 있었던 것 같다. 2020 현장스케치에 있었던 모습과 비슷했으며, 겨울학교에서 줌으로만 봤던 사람들도 많이 볼 수 있었다. 하지만 친한 친구와도 인사하기 어려울 정도로 방역수칙을 잘 지킨 상태에서 대회가 진행되었다. 그 이전..