구사과

Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던 옛 시간은 이젠 안녕. 이제는 백트래킹 짜고 하드 코딩해서 넣으면 끝난다. 이 글은 알고리즘의 구현법, 동작 원리나 증명에 대해서 거의 설명하지 않는다. 그 이유는 내가 구현법과 동작 원리, 증명을 모르기 때문이다. 알고리즘 구현은 여기에서 복붙해서 사용하면 된다. 이론적 배경지식이 상당히 깊지만, 그 활용도가 매우 높기 때문에, 일단 이해하지 말고 작동법부터 제대로 깨우친 후, 나중에 다시 돌아와서 방법을 이해하는 것을 추천한다. 1967년 이 알고리즘을 개발한 수학자 Elwyn Berlek..

(So, 1986)가사

뭐 했는지만 대충 알 수 있는 수준의 짧은 요약글로 정리하려고 한다. 다 쓰면 너무 길다.Day1 A: NEERC 2018 B랑 매우 비슷한 General Matching. D: 특수한 그래프에서 weighted bipartite matching을 빠르게 계산하는 문제. weighted bipartite matching은 가중치가 큰 순서대로 에지를 추가하면서, 최대 매칭을 증가시키는 것만 넣어주는 식으로 계산할 수 있다. 이렇게 가중치를 없에고 최대 매칭 문제로 환원하면, ARC076F / POI Ice Skates 에 나온 유형처럼, 홀의 결혼 정리 + Segment Tree 로 해결 가능. 사실 생략한 아이디어들이 이것저것 있는데 다 적으면 너무 길어지니 생략. E: planar graph에서 ra..

블로그에 글을 쓰다 보면 캡처를 할 일이 정말 많다. 옛날에는 캡쳐를 하면 바로 파일이 생겨서 올릴 수 있었지만, 언젠가부터 캡쳐 후 저런 식으로 우하단에 썸네일을 띄워주기 시작했다. 썸네일 물론 좋으나, 썸네일이 10초동안 계속 화면에 남아 있고, 썸네일이 사라지기 전에는 파일 생성이 안된다. 저거 때문에 짜증난게 한 두번이 아닌데, 마침 얼마전에 이를 없애는 방법을 찾아서 공유하고자 한다.Cmd + Shift + 5를 누르면 캡쳐 툴이 뜬다. Shift + 3/4에 익숙한 사람들은 처음 보는 화면이 뜬다. 모하비 업데이트로 생긴 듯 하다. 옵션 -> 미리보기 썸네일 표시 를 해제한다.답답한 사람들이 많았을 것 같다. 이 팁으로 그동안 쌓인 스트레스가 다 해소되었으면 좋겠다.

practice_ptzbf 1월 22일 연습 오후: ARC 064 CDEF ainta (guest)36:3549:3343:4434:33tncks01212:4823:389:2359:19koosaga3:3097:5631:58- 실제 연습 환경에서 한 게 아니라 변동 사항이 있을 수 있다. (아인타는 약간 늦게 합류했고, 집중할 수 있는 상황이 아니었고, 등등..)하지만 내가 문제를 못 푼 건 그래서가 아니었다. 일단 D의 풀이를 보는데 한 30분 정도를 사용했고, F를 보고 풀 수 있다고 생각하고 너무 과도하게 달려들었던 것도 참패 요인이다. F는 내가 보통 거르고 보는 약수 포배 유형이다. 풀이를 들었는데 웬만큼 잘 생각하지 않았으면 못 풀었을 문제인 것 같다. 그런데 그런 유형인지를 모르고 E를 푼 이후..

관련 내용이 이 블로그에도 매우 잘 나와 있으니 같이 보면 좋을듯. 이 글에서는 LP에 대한 정의를 안다는 것을 가정하기 때문에, 정의를 모른다면 링크한 블로그를 참고해야 한다. 직관 다음과 같은 LP 문제를 생각해 보자. $\text{Maximize: } 4x + 4y$ $\text{Subject to: } x + y \leq 3,x, y \geq 0 $ 이 문제의 답은 굉장히 자명하다. $(x+y) \leq 3$ 이라는 조건이 있으니, $4(x+y) \leq 12$ 를 만족한다. 그 외에 다른 제약 조건은 $x, y \ge 0$ 뿐이니 답은 간단히 12로 결정된다. 이를 조금 더 어려운 예시로 바꿔보자. $\text{Maximize: } 4x + y $ $\text{Subject to: } x+y \..

1월 1일 심야: Petrozavodsk Winter 2018. ITMO Contest 좋은 셋이냐 하면 그건 잘 모르겠는데... 확실히 배울 건 많은 셋이었다. 그래도 이번 신년 연습 중에서는 이게 그나마 제일 정상이었던 거 같다 (...) A는 적분 식을 찾았으나 너무 복잡해서 포기했다. 하지만 그 복잡한 적분을 노가다하는게 정해였다고 한다(...) 우웩 F는 connection 정보를 관리하는 DP를 짜면, 가능한 연결 상태가 약 3000개 ~ 4000개 정도이다. 이걸 directed graph로 모델링하면, 결국 여기서 거리가 $K$ 인 walk를 찾는 문제가 된다. 이는 Berlekamp-Massey를 사용해서 해결할 수 있다. 곧 블로그에 글을 쓸 지도 모름. H는 directed mst라고..

Topcoder SRM 744 Easy는 그대로는 매우 귀찮으나, 2차원 부분합을 구할 때 쓰는 포함 배제 테크닉을 활용하면 조금 덜 귀찮아진다. 물론 그래도 귀찮다. 난 문제를 잘못 읽어서 망했다. Medium은 행과 열에 대해서 해당 행 / 열을 뒤집었는가? 를 나타내는 $n+m$ 개의 boolean 변수를 잡으면, 주어진 조건은 $X_i + X_j$ 의 홀짝성에 대한 제약조건으로 바뀐다. 이를 일종의 이분 그래프라고 생각하고 풀어주면 된다... 라는 류의 문제를 한 두 번 본게 아니어서 그냥 아무 생각 없이 코드를 짰으나 문제에 함정이 있다는 것을 늦게 깨달았다. 고치니까 150점. Hard는 큰 트리에서 특정한 형태의 선형 계획법 (LP) 를 돌리는 문제이다. small-to-large 트릭을 활..

방학동안 삼성전자 소프트웨어 멤버쉽에서 팀연습을 계속 진행하고 있다. 아래는 그 기록이다.12월 23일아침: Atcoder Regular Contest 077 C D E F koosaga 3:04 17:04 26:24 - tncks0121 4:51 21:30 45:37 - alex9801 24:20 34:13 47:11 - 점심: GP of Xian매우 말려서 루즈한 분위기로 계속 진행했는데 끝나고 나니까 등수가 기대 이상으로 높았다. 대체 왜 높을까.. * A는 풀이가 궁금한데 아무도 안 적어 준다.* B는 NEERC 2018 I와 비슷한 유형의 카운팅 문제이다. 수학 못하는 팀이라 대회 때는 아무도 안 잡았다 (그건 잘 한거 같다.) 나중에 NEERC 업솔브 할 일 있으면 비슷한 유형으로 풀어보면 좋..

난이도 순입니다. 1. ARC 051. Sum of Three Integer $A, B$ 를 정하면, $C = S - A - B$ 로 자동으로 정해집니다. 고로 모든 $A, B$ 를 이중 루프로 순회하고, $0 \leq C \leq K$ 를 확인하면 됩니다. $A, B$의 가짓수가 각각 $K+1$개이니 시간 복잡도는 $O(K^2)$입니다. 포함배제 원리를 사용한 $O(1)$ 풀이도 있지만, 이 문제에서는 필요 없습니다. 2. POI 1997. Canoes 먼저 각각의 사람을 몸무게 순으로 정렬해 놓읍시다. 가장 가벼운 사람은 다른 사람과 보트를 태워 보내는 것이 합리적으로 보이니, 가장 가벼운 사람을 보낼 때는, 다른 사람 한 명을 잡아서 같이 보트를 태워 보냅니다. 같이 탈 수 있는 사람이 여럿이면 물..