2021.02.06 - 백준 온라인 저지(BOJ) 기능 확장 프로그램 백준 온라인 저지(BOJ) 기능 확장 프로그램 백준 온라인 저지(https://www.acmicpc.net) 사이트의 기능을 보완/확장하는 목적으로 BOJ-Extended를 만들었다. BOJ Extended 백준 온라인 저지(BOJ)를 확장된 기능과 함께 사용해보세요. chrome.google.com 처음.. blog.joonas.io 나만의 기능을 원해서 1월에 작게 개발하고, 2월에 배포하기 시작했던 확장 프로그램이었는데, 다같이 자기가 필요한 기능을 만들어봤으면 좋겠어서 오픈소스로 공개하고 관리한 지 벌써 1년이 지났다. 1.7.7 버전 이후로는 stable한 상태이다. 어느 순간부터 Chrome 정책이 Manifest V3 업데..

백준 온라인 저지(https://www.acmicpc.net) 사이트의 기능을 보완/확장하는 목적으로 BOJ-Extended를 만들었다. BOJ Extended 백준 온라인 저지(BOJ)를 확장된 기능과 함께 사용해보세요. chrome.google.com 처음에는 (원래는 있었지만 잠시 사라진) 프로필에서 문제 제목이 보이도록 하고 싶어서 시작했는데, 이거 하나만을 위한 확장 프로그램은 뭔가 아까워서 기능을 이것저것 붙이다보니 현재의 상태가 되었다. 뭐가 있을까 고민하다가 다크모드(어두운 테마)를 추가해봤고, 그 외에도 문제 타이머, 넓게 보기, 채점 현황과 게시판에서도 문제 제목으로 바로 보기, 채점 결과 텍스트 바꾸기 등 계속 추가하고 있다. 언제 추가될 지 모르겠지만, 업데이트 예정으로는 (미리 저..

https://www.acmicpc.net/problem/11012 문제 2차원 평면에서 점들의 위치가 주어지고, [left, right]×[bottom, top] 으로 그려지는 사각형 내에 있는 점의 개수를 쿼리마다 출력하는 문제이다. 이 문제는 PST(Persistent Segment Tree)로 해결할 수 있다. PST의 이해를 위해서는 Segment Tree를 먼저 알아야한다. 이 글에서는 자세한 설명은 생략하고, 도움이 될 만한 글로 대체한다. 사실 같은 내용을 이 문제에 대해서만 다시 정리하는 것이라 봐도 무방하다. 혼동이 있을 수 있지만, 이 글에서는(필자는) 세로/수직 방향을 \(y\)축으로 가로/수평 방향을 \(x\)축으로 한다. 즉, \((0,~0)\)은 왼쪽 아래를 의미한다. y축을 ..

링크: https://www.acmicpc.net/problem/3640문제가중치가 있는 방향 그래프가 주어지고, 1번 정점에서 V번 정점까지 서로 겹치지 않는 2개의 경로 중 비용이 최소인 경우를 출력하는 문제이다. 겹치지 않는 경로를 찾는 것은 최대 유량으로 해결 가능하고, 그 비용이 최소가 되는 것을 구해야하므로, 네트워크 플로우 유형 중에서 MCMF(Min Cost Max Flow; 최소 비용 최대 유량)인 문제이다. 그래프 문제는 항상 문제 조건을 꼼꼼히 살펴야겠다. 이번에도 "출발과 목적지를 제외하고 같은 중간 지점이나 같은 뱃길을 지나면 안 된다." 에서 정점이 겹쳐서는 안되는 조건을 깜빡해서 계속 틀렸다. 이 조건을 무시하면 틀리는 예외 케이스는 아래와 같다. 최대 유량은 1개이고, 답은 ..

링크: https://www.acmicpc.net/problem/15480문제문제 설명은 간단하다.루트를 r로 하는 트리에서 u와 v의 최소공통조상(LCA)를 출력하는 문제이다. LCA(r, u), LCA(r, v), LCA(u, v) 세 개 중에서 깊이가 더 깊은 노드를 출력하면 된다.증명은 사실 안 했는데, 케이스 몇 개를 두고 해보니까 계속 답이었다..혹시나 싶어서 제출해봤더니 정답코드

링크: https://www.acmicpc.net/problem/9034오랜만의 포스팅. 아마 한동안 문제를 풀 시간은 없을 듯.. ㅠ문제매번 \(i\)번 선수에게 더해지는 점수가 주어지고, \(x\)번째 선수가 몇 등인지 실시간으로 출력하는 문제이다. 먼저 어떤 선수의 등수는 "그 선수보다 점수가 더 높은 사람의 수 + 1"이다.매번 탐색을 하거나, 정렬을 한다면 \(100,000\)명의 선수에 대한 \(200,000\)번의 질의에 대답하기엔 시간상으로 버겁다. 내 등수는 구간 [내 점수 + 1, ∞)에 있는 사람의 수 + 1과 같다. 점수의 합은 최대 \(10^{9}\)이므로, 모든 점수를 압축할 필요가 있다. 이건 좌표압축 문제(BOJ 18870 - 좌표 압축)를 먼저 풀어보기를 권장한다.점수가 더..

링크: https://www.acmicpc.net/problem/18109 문제 한글 두벌식 자판으로 타이핑할 때, 다음 글자의 초성 자음이 이전 글자의 받침으로 미리 작성되는 경우를 구하는 문제이다.자세한 예시는 문제에 자세히 나와있으니 생략한다. 풀이처음에는 영문 모드로 작성한 아무 문자열이 입력으로 들어오는 줄 알았다.그래서 모든 케이스에 대해 고려하다보니, 오토마타를 그리게 되었는 데 아래와 같다. 나중에 다시 보니 항상 "완성형 한글"이 입력되는 꼴만 입력되더라... (모음 'ㅏ'키인 k 가 대문자 K로 적히는 경우도 없었다)여기서 합성모음은 반모음+반모음(ㅘ, ㅝ)와 둘레모음+반모음(ㅞ, ㅙ) 등을 간략히 표현한 것이다. (알맞은 표현을 알려주시면 감사합니다)화살표에서 겹받침은 ㄳ, ㄼ 등으로..

링크: https://www.acmicpc.net/problem/5052문제한 문자열이 다른 문자열의 접두어(prefix)이면 NO, 그런 경우가 없으면 YES를 출력하는 문제이다.풀이 1 (정렬)모든 문자열을 사전순으로 정렬하면, 접두어가 겹치는 문자열끼리 붙어있다.어떤 문자열이 직전 문자열의 부분 문자열인지 확인하면 된다.시간 복잡도는 정렬 + 부분 문자열 확인 시간만큼이므로, \(O(nlogn + n|s_{max}|)\)코드 1 (정렬) 풀이 2 (트라이; Trie)분류에 트라이가 있기도 하고, 트라이를 한번도 구현해본 적 없어서 트라이로 풀어봤다.문자열을 하나씩 확인하며 트라이를 만들어간다.어떤 문자열이 끊긴 지점에 "이 곳이 하나의 단어였다"로 리프 표시를 해두고 넘어간다.다음에 트라이를 만드는..