unordered_map이 PS하는 블로그

이 문제는 내가 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 현장스케치에 있었던 모습과 비슷했으며, 겨울학교에서 줌으로만 봤던 사람들도 많이 볼 수 있었다. 하지만 친한 친구와도 인사하기 어려울 정도로 방역수칙을 잘 지킨 상태에서 대회가 진행되었다. 그 이전..

총점 : 100/100/0/20=220 (동상, 16.10%, 33위) 1. 뇌절 및 구현장애가 많았던 시험... 2. 코이가 점점 온라인 시험에 적응하고 있다는 생각이 들었음... 감시 & 시스템 철저 bb 3. 문자열 시러 ㅡㅡ 1번 문제 - 헬기 착륙장 헬기 착륙장은 1~k의 반지름을 갖는 k개의 동심원으로 이루어져 있으며, 각각의 원은 빨간색 또는 파란색으로 칠해짐. 반지름 i인 원을 칠하는 데에는 정확히 페인트 i통이 필요함. 빨간 페인트 a통, 파란 페인트 b통이 있을 때 만들 수 있는 헬기 착륙장 종류의 수를 출력하시오! 1번을 보자마자 아무 생각도 나지 않았다. 그래서 고민하다가 내가 1번도 못 푼다는 사실에 금이 간 멘탈에 대충 테이프를 붙이고 2번으로 향했다. 경험상 아무리 쉬운 문제여..

최대 유량 문제 (Maximum Flow) 최대 유량 문제(Maximum Flow)란 방향 그래프에서 각 간선의 용량이 정해져 있을 때, 정해진 출발점에서 도착점까지 보낼 수 있는 최대의 유량을 계산하는 문제를 말한다. 위와 같이 생긴 방향 그래프의 1번 정점에서 7번 정점까지의 최대 유량인 상황은 아래 그림과 같다. 간선에 적힌 a/b는 용량이 b인 간선에 현재 a의 유량이 흐르고 있다는 것을 말한다. 이 경우의 유량은 11이다. 더 이상의 유량이 없다는 것은 어떻게 알 수 있을까? 최소 1의 유량이 흐를 수 있는 출발점에서 도착점까지 가는 경로를 증가경로(Augmented Path)라고 한다. 위 그래프에서 증가경로는 없다는 사실을 눈으로도 쉽게 확인할 수 있으며, 임의의 그래프에 대해서도 DFS/B..