나름 개발자의 IT블로그

매트로이드(matroid)란 다음 성질을 만족하는 구조이다. $M =(X, I)$인 매트로이드 $M$이 존재한다고 하자. 1. $X$ 는 유한집합이다. 2. $I$는 $X$의 부분집합이면서 independent set이다. 공집합은 independent set이다. 3. $A, B$가 independent일 때 $|A| < |B|$이면 $x \in B-A$에 대해 $A \cup \{x\}$도 independent인 $x$가 존재한다. 위와 같은 성질을 만족하면 매트로이드라고 한다. 1번은 쉽게 이해할 수 있지만 2, 3번에 나오는 independent가 아직 와닿지 않는다. "어떤 규칙" 정도로 이해하고 넘어가자. 예를들어 $X = \{1, 2, 3, 4, 5\}$이고 $I$의 크기가 3보다 작은 집합이..

이 글에는 지극히 주관적인 내용이 많이 들어있습니다. 분리집합을 구현할 때 보통 가리키는 포인터를 옮기는 방식으로 구현하곤 한다. 하지만 이런 방법은 경로압축도 해야 하고 개인적으로 비직관적이었다. 사실 나는 재귀적인 코드와 작동 과정이 아직 완벽히 이해가 되지 않는다. 그래서 상대적으로 직관적인 smaller to larger(a.k.a 작은거 큰거)를 사용한 분리집합 구현을 소개하고자 한다. (물론 기존 방식보다 느리고 공간도 많이 사용한다.) smaller to larger라는게 애초에 집합을 합치기 위한 연산을 최적화하기 위한 기법이기 때문에 분리집합에도 사용할 수 있다. 기초적인 구조 class DisjointSet { public: vector p; vector ix; int n; } 우선 멤..

Mo's 알고리즘은 중국 알고리즘 대회에서 Mo Tao라는 사람이 사용한 기법으로 유명해졌다. 그래서 컴퓨터공학 다른 곳에서는 찾기 힘든 알고리즘이고 Competitive Programming에서 볼 수 있는 알고리즘이다. 어떤 알고리즘인지 알아보자. 오프라인 쿼리 mo's 알고리즘을 알기 위해 오프라인 쿼리를 알아야 한다. 무방향 가중 그래프가 주어지고 쿼리마다 a, b를 연결하는 간선을 끊고 u, v번 노드가 서로 연결돼 있는지 판정하시오. 위와 같은 문제는 주어지는 쿼리마다 해결하려고 하면 굉장히 어렵다. 하지만 간선을 연결하는 문제라면 분리집합으로 쉽게 해결할 수 있다. 그래서 처음에 쿼리를 모두 저장하고 뒤에서부터 역순으로 쿼리를 수행하면 쉬울 것이다. 이런식으로 여러 개의 쿼리를 주어진 순서대..

Q : N개의 정수 배열에서 a~b까지 합을 구하려면 어떻게 하나요? A : for문을 돌면서 더해요! $O(N)$ Q : 그럼 Q개의 쿼리형식으로 들어온다면요? A : 누적합배열을 사용해요! $O(N+Q)$ Q : 그럼 여기에 업데이트도 있다면 있다면 어떻게 할까요? A : 세그먼트 트리를 쓰면 되죠! $O(Q \log N)$ 위의 모든 답변은 실제로 정답이고 더 어려운 알고리즘이 하위 문제를 해결할 수 있다. 예를들어 누적합으로 1번 문제를 해결할 수 있고 세그먼트 트리로 1, 2번 문제를 해결할 수 있다. 하지만 위 문제들을 제곱근 분할법(a.k.a. 루트질)을 사용해서 해결할 수도 있다! 물론 쉬운 알고리즘을 사용할 수 있다면 그걸 사용하는게 좋겠지만 연습용으로 풀기 좋다. 어떻게 해결할 지 알아..

요즘 Chat-GPT가 핫하다. 이 대화형 인공지능이 알고리즘 문제도 해결한다고 하는데 어디까지 해결할 수 있는지 궁금해서 백준 문제로 실험을 해봤다. 문제가 될까봐 실제 제출은 하지 않았고 정답이 맞는지는 내가 판단했다. 문제는 브론즈 5부터 한단계씩 올라가면서 내가 푼 문제들 중 한국어 문제 기준으로 테스트했다. B5 16394 홍익대학교 B4 16204 카드뽑기 주석까지 적는 여유가 보인다. B3 15917 노솔브 방지문제야!! B2 2954 창영이의 일기장 B1 5533 유니크 입력형식이 올바르지 않아 런타임에러가 났는데 풀이만 놓고 보면 정답이다. 입력형식이 복잡해서 그럴 수 있으니 좀 단순한 문제로 다시 시도했다. B1 1110 더하기 사이클 틀렸다. 표본이 적고 solved 난이도가 개인차에..

이번에 건국대학교 교내 알고리즘 대회 KUPC를 개최하게 되었다. 뭐든지 대회를 참여만 해서 개최하고 운영하는건 처음이었는데 좋은 경험을 얻은 것 같다. 운영을 하면서 배운 것과 느낀점, 뒷이야기 등이 많아 기록해두려고 한다. 이번 운영진은 UCPC팀원과 ICPC팀원의 합집합으로 구성되어있다. riroan, aru0504, kth990303, delena0702 개최하게 된 이유 UCPC가 끝나고 알고리즘 문제에 대한 아이디어가 마구마구 샘솟아서 어딘가에 문제를 출제하고 싶었다. 하지만 백준에 출제하려면 적어도 2000문제를 풀어야했는데 아마 몇백문제 남아있었던 것 같다. 그렇게 찾다가 나온 사이트가 누구나 출제할 수 있는 삼성 SW Expert. (문제는 여기) 위에 냈는데 더 많은 사람이 봤으면 하는..

지난 토요일 코드 몬스터 예선을 통과하여 본선을 보러 갔다. (온라인이라고 했는데 오프라인으로 바꼈음) 코드 몬스터는 알고리즘 실력만으로 LG CNS에 입사 기회를 부여하는 대회같은 코딩테스트(?)이다. 알고리즘쪽은 워낙 잘하는 분들이 많아서 여기서 좋은 성적으로 입사 기회는 얻지 못할 것같고(..) 오프라인 대회 체험을 위해 참석하였다. Before Contest 코드 몬스터는 LG CNS가 있는 마곡에서 진행되었다. 아침을 안먹었는데 빵과 먹을 것을 줘서 맛있게 먹었다. 사용하는 노트북은 역시 LG Gram이었다. Main Contest 메인 대회는 프로그래머스에서 진행되었고 외부 IDE나 구글링은 당연히 통제되었다. 문제를 소개하면 안될 것 같아 느낌만 남기려고 한다. 그냥 내 입장에서 문제가 정말..

지난주 토요일 ICPC 2022 Seoul Regional에 참가했다. 올해는 킨텍스에서 진행됐고 금요일 예비소집, 토요일 본 대회로 이틀을 참석했다. (암호학 수업을 빠졌다. ㅠㅠ) Before Contest 교내 대회 개최 준비로 팀 연습을 많이 안해서 전략은 별로 없었다. 대회가 시작되면 한명은 앞에서부터, 다른 한명은 뒤에서부터, 그리고 내가 파일을 만들고 환경을 세팅해놓는 역할을 하기로 했다. vscode를 지원해서 좋아하고 있었는데 아무 확장이 없는 상태라 pycharm, clion을 사용하기로 했다. 본 대회에서 총 4문제를 풀었는데 내가 푼건 0개이다. ㅠㅠ 예비소집날 세종대팀과 같이 저녁을 했는데 양쪽팀 목표가 서로를 이기는 것이었다. ㅋㅋ 00:11 J solve! 대회가 시작되고 전략..

대학생활 마지막 ICPC를 나가게 되었다. 다들 실력이 좋아서 학교 1등으로 본선에 진출할 수 있게 되었다. 팀원 : riroan, aru0504, delena0702 Before Contest 팀명은 UCPC의 "일감호는 우리가 지킨다"를 영어로 적절히 바꾼 "Ilgam Rangers"로 정했다. 옛날엔 안그랬던거같은데 ICPC예선에서 카메라로 영상촬영을 해서 제출을 해야한다고 세명이 같은 장소에서 대회 내내 영상을 찍으라고 했다. 대충 카페같은데서 모여서 보려고 했으나 위와 같은 상황때문에 학교에서 강의실을 하나 빌리게 되었다. 이전 예선 대회들을 분석해보니까 한국어문제가 쉽고 I번문제가 쉬웠던 경향이 있었던 것 같아 이런 문제들을 먼저 공략하기로 했다. (ICPC여서 I가 쉬운거라고 추측했었지만 올..

라운드 2에서 2000등 안에 들면 티셔츠를 준다는 말에 메타(구 페이스북) 해커컵에 참여해봤다. 외국대회라 그런지 시간대가 심상치 않다. (새벽 2시 시작) 다행히 라운드 2에서 2000등 안에 들어서 티셔츠를 얻을 수 있게 되었다 oOvOo 제출 방식 해커컵은 다른 대회와 제출 방식이 다르다. 기본적으로 출력 결과를 제출하는 방식이고 예제를 통과해야 제출할 수 있다. 예제를 통과하면 전체 데이터셋을 압축파일로 제공하는데 이 파일에 암호가 걸려있다. 타이머를 시작하면 암호가 주어지고 프로그램 실행 후 결과를 제출하면 된다. AC는 대회가 끝난 후 초록색으로 표시된다. (Qualification A1 ~ B2) TLE는 타이머 안에 제출할 수 없고 회색으로 표시된다. (Qualification D) WA..