[조합론] Chapter 2. 수학적 귀납법 [내부링크]

정수론도 초반 챕터가 귀납법이였는데 조합론에서도 나오는거보면 중요한 것이긴 한가보다. 귀납법(약귀납법), induction(weak induction) (1) 기본 단계 정리가 정의된 최소의 m, 대개의 경우 0 또는 1에 대하여 성립함을 증명한다. (2) 귀납 단계 정리가 n에 대하여 성립한다면("귀납적 가정")이라면 n+1에 대하여도 성립함을 증명한다. 강귀납법 (1) 기본 단계 정리가 정의된 최소의 m, 대개의 경우 0 또는 1에 대하여 성립함을 증명한다. (2) 귀납 단계 정리가 n+1 보다 작은 모든 정수에 대하여 사실이라면("귀납적 가정")이라면 n+1에 대하여도 성립함을 증명한다. 이게 성립하는 이유를 보자. 귀류법으로 위 두 단계.......

[조합론] Chapter 3. 기본적인 계수 문제 [내부링크]

고등학교의 확률과 통계에 배우는 개념들이 나온다. 조합 Example 3.5는 고등수학에서 같은 것이 있는 순열을 의미한다. 유한 알파벳에서의 문자열 전단사함수 bijection 갑자기 전단사함수 이야기가 나온 이유는 전단사함수를 이용해 개수를 세는 문제에서 f 가 전단사 함수임을 보이고 치역의 원소의 개수를 세는것이 정의역의 원소의 개수를 세는것보다 쉬울 수 있기 때문이다. 전단사 함수이면 치역과 정의역의 원소의 개수가 같기 때문이다. 선택 문제

[백준] 15731 Python 문법 [내부링크]

점화식을 세워보자. i-1 이 f 이면 무조건 i에서의 indent는 1개가 늘어나는 수밖에 없고 i-1 이 e이거나 시작위치이면 i에서 indent가 j가 되려면 i-1에서 indent가 j, j+1, ... n 개인 경우 모두가 가능하다. 저 시그마를 어떻게 처리하느냐? prefix sum으로 처리하면 된다. 이걸 직접 prefix sum을 구현 안하고 점화식 단계에서 풀어낼 수 있는데, 그럼 더 빨라진다. 하지만 난 그런건 할줄모른다.

[백준] 20307 RREF [내부링크]

Gaussian elimination 을 잘 구현하면 된다. 주의할 점은 정말 "잘" 구현해야 된다는 것이다. 문자열도 파싱해야 하고 차라리 유리수(기약분수)를 다루는 구조체를 정의해서 연산을 오버로딩 한다음에 하는것이 편하다. 그리고 왜인진 모르겠는데 계산을 하다보면 long long 범위를 넘어가서 연산순서에 주의해서 lcm 같은것을 처리해주어야 한다.

한적한 밤의 PS [내부링크]

일단 어떤 동물이든 0, 1, 2 .. 처럼 증가를 해야한다. 그렇지 않고 0, 0, 0 같이 동일한 수가 세개거나 1, 2 같이 건너뛰는 수가 있으면 항상 답은 0이다. 그렇지 않아고 할 때 각 동물의 마리수를 a, b(a >= b) 라고 하자. 0 ~ b-1 까지는 동일한 순서를 가진 두 동물을 어떤 동물이든 선정할 수 있으므로 2^b 가지 경우가 나온다. 이 때 a!=b 이라면 1~a 까지와 1~b 까지 가는 경우를 두 동물이 아예 다르게 설정될 수 있으므로 2를 더 곱해준다. 그냥 bfs 돌리고 정렬하셈 그냥 bfs 돌리고 찾자. 경로의 합이 최소인 점은 겹치는 간선이 없다. 만약 그렇다면 겹치는 간선을 풀어줄수있어서 최단경로가 더 줄어들어서 모순이다. .......

[백준] 12843 복수전공 [내부링크]

괴닉의 정리에 의해 Minimum vertex cover = Max flow 이고 정답은 N - Minimum vertex cover 이다. 모순관게를 최소의 강의를 안들음으로써 끊어준다고 생각하면 된다. 간선수의 제한이 너무 많지만 시간제한과 정답률을 믿고 제출하면 맞는다.

[백준] 17834 사자와 토끼 [내부링크]

서로 만날 수 없으려면 1. 아예 다른 컴포넌트에 있다. 2. 같은 컴포넌트에 있지만 컴포넌트가 이분그래프이고 각기 다른 position에 있다. 이 두 경우를 모두 세주어서 출력해주자.

[백준] 16474 이상한 전깃줄 [내부링크]

LIS + DP 문제이다. LIS 자체가 DP이긴 한데... 한번 더 쓴다. 일단 인덱스를 적절히 조절해주자. a -> b 로 갈때, dp[i] = b에서 i-1 번째까지 전깃줄만 썼을 때 최대 전깃줄 수 0-based로 K - dp[m] 가 답이다. dp 테이블을 적절히 관리해주기 위해 a->b 간선들은 모두 내림차순으로 정렬해주고 dp를 돌려주어야 하며 각 i 가 지날때마다 prefix maximum 으로 모두 변경해주자.

[백준] 13262 수열의 OR 점수 [내부링크]

Divide and conqure optimization 문제가 예전 글들 안찾아보고도 슥슥 구현이 되는걸보니 이제 좀 손에 익은것 같다. 이 문제는 O(N^2)에 DnC Opt 를 돌려야 하는데, 일단 DnC 가 동작하는 이유를 알아보자. 이 그 뭐시기냐 점화식이고 구간합 OR 배열은 당연히 Monge array가 아니다. 하지만 opt[k][i]와 opt[k][i+1]을 비교해보자. OR 연산이므로 수가 더 추가되면 최적해를 앞으로 갈 이유가 없다. 무조건 그자리거나 뒤로가는게 최적이기 때문에 최적해의 단조성이 보여져서 DnC opt를 쓸 수 있다. 시간제한이 빡빡해보여서 OR을 처리하기 위해 O(30) 짜리 구간합 배열이나 세그먼트 트리를 안쓰고 sparse table로 O(1) 쿼리가 가능하도록 전.......

[일상] 220123 낮에 쓰는 일상 글 [내부링크]

오래간만에 일상 글을 쓴다. 2022년이 되어도 놀랍게도 내 생활엔 아무런 변화가 없었다. 근래에 코로나 검사, PCR 검사라고 하는 건가 뭔가를 두 번을 받았는데 생각보다 별거 아니었다. 일단 뭔가 생활 얘기를 하기 전에 몇 가지 이벤트들을 훑자면 1. 다음 주 목요일(1월 27일)에 라식 수술을 받기로 했다. 안경은 거의 초등학교 2-3학년부터 낀 거 같고 렌즈는 중학교 3학년 때 껴보기 시작했으니 거의 십몇 년간의 시각장애인 생활을 청산하려고 한다. 지금까지 왜 안 했냐라고 한다면 귀찮아서도 있고 뭔가 걱정돼서도 있는데 심심하니까 이거라도 좀 해야겠다. 하고 나면 굉장히 편할 것 같다. 빛 번짐과 안구건조증은 감수하더라도(렌즈.......

[조합론] Chapter 1. 비둘기집 원리 [내부링크]

블로그의 [조합론] 카테고리는 이 책의 내용들을 정리해나가는 공간이 될 것이다. 참고로 이 책에선 Theorem 이든 Definition 이든 Example 이든 동일한 수준으로 번호를 계속 증가시켜나간다. 1.1, 1.2 ... 책에 나온 내용대로 중요하다고 생각되는 부분들만 간추린다. 비둘기집 원리의 증명엔 귀류법이 자주 쓰이는 것 같다. 다음은 정수론과 관련된 하나의 예시이다. 이제 비둘기집 원리의 일반화된 정리를 살펴보자. 다음은 기하학과 관련된 하나의 예시이다.

[백준] 업다운 랜덤디펜스 #1 [내부링크]

업다운 랜덤디펜스는 티어 G5 부터 시작해서 랜덤 문제를 뽑은 뒤 그 문제를 30분 이내에 해결하면 티어를 한단계 올리고 그렇지 못하면 내리는 방법입니다. 1. G5 20444 색종이와 가위 - AC(+) [9m 30s] 가로를 자를 횟수를 m이라고하고 세로를 n - m 이라고 하면 이분탐색으로 찾아줄 수 있다. 2. G4 1101 카드 정리 1 - AC(+1) [14m 20s] 그리디 문제인데, 일단 다른 종류의 카드가 두 개 이상 있는 박스는 무조건 조커 박스가 되거나 한번에 다 조커박스로 옮기는게 최적이다. 그리고 한종류만 있는 상자들에 있는 그 종류마다 각 개수를 세둔다음, 적절히 연산을 해주면 되는데 정확히 모르겠다. 3. G3 1278 연극 - AC(+)[10m 55s] 재귀 문.......

[백준] 업다운 랜덤디펜스 #2 [내부링크]

에서 이어집니다. 13. G1 3366 수열 줄이기 - AC(+) [19m 40s] 14. P5 21762 공통 부분 수열 확장 - AC(+1) [18m 20s] 후기 회사 점심시간에 짧게 두문제만 해봤습니다 ㅎ G4부터 연속으로 올라와서 기분이 좋네요 시간이 없어서 1, 2 편에 문제들 설명은 다시 돌아와서 적을 예정입니다. 플레티넘 한번 찍어보고 싶었는데 다시 골드로 가도 여한이 없습니다. 3편에서 P4와 함께 이어집니다.

[백준] 업다운 랜덤디펜스 #3 [내부링크]

에서 이어집니다. 15. P4 14800 Ratatouille (Large) - AC(+) [27m 30s] 그리디 태그가 붙어있는데 최대유량으로 맞췄다. 근데 뻔한 반례가 있는데 그냥 통과되는거 보니까 데이터가 약한거같다. 다시 생각을 해봐야겠다. 16. P3 2329 전파와 병합 1 - GG 문제만 10분읽고 이해를 마친후에 이건 30분내에 풀만한 문제가 아니란걸 깨달았다. 그냥 열심히 구현한다음에 문제풀이 글로 올리겠다. 분류를 까보니 역시나.... 후기 짧게 짧게 단타만 치는중...

[백준] 23297 전파와 병합 1 [내부링크]

총평: 삼성 상어시리즈와 카카오 문자열 파싱 문제를SCC에 접목시켜 무한으로 즐기는 기분이였다. + SCC는 필수는 아닌걸로

[백준] 6286 리벤지 오브 피보나치 [내부링크]

문제를 해결한 과정을 단계별로 설명한다. 1. 10만까지의 피보나치수의 앞에 40자리만 모두 구하기 일단 수의 자리가 40자리라고 했으므로 우린 정수형으로 피보나치 수를 저장할 수 없다. 따라서 정수를 문자열로 바꾸고 문자열끼리 더하는 함수를 만들어준다. 그런데 여기서 문제가 있다. 10만까지 피보나치 수를 문자열로 구해도 피보나치수는 자리수가 꽤 빨리 커지기 때문에 10만까지 모든 피보나치수를 문자열로 저장할 수 없다. 그리고 이 문제는 놀랍게도 메모리 제한이 128MB 인데 왜그런진 모르겠다. 그러면 우린 망한걸까? 아니다. 문자열끼리 더하면서 앞에 40자리 까지만 남기는 방법이 있다. 대충 오차를 피하기 위해 저장할 최대.......

[백준] 14862 최대공약수 기댓값 [내부링크]

이문제는 결론적으로 최대공약수의 합을 수식을 승법적 함수를 쓰는것까지 나타내서 시간을 최적화 해야 통과되는 문제다. 즉, 테스트 케이스 하나를 Harmonic Lemma를 사용한다면 에 계산 가능하다. N은 모듈러 역원으로 구해주면 된다. 위방법으로 제출했을때는 시간초과가 나게된다. 좀더 최적화를 해보자. 함수 g를 Linear sieve로 O(N)에 전처리해둔다면 Harmonic Lemma 없이도 한 테스트 케이스가 O(N)에 처리되기 때문에 맞을 수 있다. 하지만 여기서 Harmonic Lemma 까지 써준다면 정도로 빠르게 통과 가능하다. 실제로 28ms 나왔다.

[백준] 8201 Pilots [내부링크]

N이 300만이여서 NlogN 이 될까 싶지만 시간제한이 넉넉하므로 FASTIO 까지 써주니 1.9초로 통과는 했고 O(N) 풀이도 배워보았다. O(NlogN) 풀이 이분탐색 + 모노톤 큐로 풀 수 있다. 길이 K가 가능하다면 J(J<K) 는 항상 가능하므로 이분탐색을 적용할 수 있는 문제이고, 정해진 길이 K에 대해서 모노톤 덱으로 O(N)에 검사를 해준다면 O(NlogN)이 나온다. 최대값, 최소값을 위해 덱을 두개를 써야하고 덱 자체도 상수가 있기 때문에 그렇게 빠른 O(NlogN)은 아니다. O(N) 풀이 투포인터 + 모노톤 큐로 O(N)에 처리가 가능하다. 구간 [L, R] 을 유지한다. R이 증가할때 [L, R] 에 최대값 - 최소값이 t보다 크다면 모노톤하게 유지하고 있는 현.......

[백준] 17792 Keep Him Inside [내부링크]

처음엔 무지성 랜덤풀이 + 삼분탐색으로 문제를 해결할 수 있었다. 랜덤 풀이 임의의 서로 다른 두 점을 랜덤으로 잡고 두 점의 fraction 합에 대해서 얼만큼 가중치를 부가할지 삼분탐색으로 최적점을 찾아나가면서 진행하는 방식인데, 이는 78%에 반례가 있어서 통과되지 못했다. 왜냐하면 계속 두개씩 봐주면서 local minima를 찾아주어도 global minima에 도달하지 못하는 점의 위치가 있을 것같다. 이를 해결하기 위해 또 랜덤적으로 그냥 삼분탐색을 skip 하고 가중치를 한쪽에 몰빵을 해주는 로직을 넣었더니 그냥 통과가 되어버렸다. 정해 이 문제를 올바르게 해결하는 방법은 N개의 점 중 3개의 점만 이용해서 가중치 1을 적절하게 배분.......

[백준] 16313 Janitor Troubles [내부링크]

사각형 네 변의 길이가 주어졌을때 사각형의 최대 넓이를 찾는 공식이다. 네 변을 가지고 적절히 조합해 항상 어떤 원에 내접하는 사각형을 만들 수 있다. 그리고 이 때의 넓이는 브라마굽타 공식을 이용해 아래와 같다. 외접원이 없는 일반화된 공식인 브레치나이더 공식에서 사각형이 원에 내접하지 않을 때 더 넓이가 줄어든다는 점을 보면 브라마굽타 공식에 그냥 사각형의 넓이를 적용하는 것과 답이 동일하다. 브라마굽타 공식은 헤론의 공식과 꼴이 비슷하다. 삼각형은 세 변이 결정되면 항상 넓이가 일정하지만, 사각형은 위와 같은 공식들로 넓이가 변할 수 있음을 알고가면 된다.

[백준] 2453 부서 배치 [내부링크]

의외로 쉽게 보인 문제이다. 문제 description만 읽고는 뭐 개나 고양이나 분단의 슬픔처럼 max-flow, min cut을 이용한 문제인가 싶었지만, 잘 생각해보니 각 컴포넌트들을 분리하고 컴포넌트들의 parity 를 뽑아내서 각각 부서 A, B에 배치를 해줄지를 DP로 찾아주는 문제였다. 간선 정보가 들어오면 이분 그래프를 만들어준다. 만약 -1 u v 라면 u와 v에 양방향 간선을 잇고 1 u v 라면 u와 v 사이에 더미 정점을 만들고 연결해준다. 이제 각 컴포넌트들마다 쏠린 정도를 arr에 담아준다. 이걸 알아내고 N이 크지 않음을 이용해 정도에 DP를 돌리면 된다.

[백준] 19580 마스크가 필요해 [내부링크]

이 문제와 동일한 그리디가 성립하는 문제이다(아니 사실 같은 문제라고 봐도 무방하다.). L, R 이 있다면 R이 작은순으로 정렬 한 후, 정렬된 순서대로 살수 있는 것 중 가장 작은 가격의 마스크를 사는게 최적이다. 나는 좌표압축 + 펜윅트리를 써서 느리게 풀었는데, 좌표압축 없이 우선순위큐로도 푸는게 정해다. 우선순위 큐 사람과 마스크를 모두 오름차순 정렬한다. 사람은 L에대해 마스크는 P에 대해이다. 우선순위 큐는 최소힙을 사용한다. 마스크를 1부터 M까지 보면서 현재 마스크 가격에 대해 현재 사람의 L이 더 작다면 우선순위 큐에 사람의 R을 추가한다. 우선순위큐에 있는건 R들이므로 R < 마스크 가격이라면 모두 빼준다. 이.......

[백준] 19588 상품권 준비 [내부링크]

체감 난이도는 약간 더 어려웠다. 최강의 팀은 항상 b개를 빼고 큰것부터 m개씩 a묶음을 묶었을 때 만들어진다는 것을 수식으로 정리하면 알 수 있다. 이제 어떻게 b개를 뺀것 이후에 큰것부터 m개씩 a묶음을 묶은걸 빨리 찾느냐인데, 결론적으로 구간합을 쓰면 되는데, 여기서도 잘생각해야한다. 첨에 xor에 대해 구간합 배열을 만들어둔다. 그럼 모든 경우에대해 이중구간합 배열을 만드는데는 얼마가 걸릴까? 이 걸린다. 이유는 b를 M으로 나눈 나머지를 offset이라고 두고 이미 만들어진 이중구간합 배열들을 인덱스만 조절해서 쓸 수 있기 때문이고 총 M개의 이중구간합배열을 만드는데 하나를 만드는게 이전에 만들어둔 xor 구간합 배열을.......

[백준] 20192 순서 섞기 [내부링크]

2020 KOI 고등부 2차대회 문제이다. 그냥 그 어떠한 알고리즘도 필요없이 ad-hoc이다. 개인적으로 어려웠던 문제 어제 꽤나 관찰을 해본결과 정답에 근접하게는 갔는데 딱 이렇다 하고 도출해내진 못해서 힌트를 보고 풀었다. 인접하고 같은 원소를 모두 제거하자. 그럼 위처럼 봉우리기 생긴다. 일단 봉우리가 1개가 있으면 무조건 1번만에 정렬이 가능하다. 여러개가 있다고 하고 가장 왼쪽과 오른쪽부터 A에서 떼어내서 B에 붙인다고 해보자. 항상 빨간색 부분 두 개(왼쪽 오른쪽은) 오름차순으로 정렬을 해주면서 B에 붙일 수 있다. merge sort의 과정처럼 생각을 할 수 있다. 반대로 초록색에 있는 가장큰 원소는 빨강색에 있는 가장 큰 원.......

[백준] 13704 수열과 쿼리 11 [내부링크]

Mo's 인건 알았는데 흔한 유형인줄알고 쉽게 풀릴것같았는데 1시간 반정도 고전해서 좀더 까다로운 방법으로 풀었다. 내 방법 왼쪽에 넣어줄때 뺄때와 오른쪽에 넣어줄때 뺄때 4가지를 모두 고려해서 함수를 만든다. 주 아이디어는 왼쪽에서 시작하는 수열과 오른쪽에서 시작하는 수열을 계속 업데이트 해주는 것이다. 그리고 왼쪽 오른쪽 각각 cnt와 offset을 관리한다. 예를 들어 왼쪽에 넣을때는 과 같이 해주어서 cnt_l, cnt_r 각각 하나씩 오프셋에 맞게 적절히 구간합 배열을 써서 카운트를 증감시켜주고 k가 늘어난 개수를 정답에 더해준다. 정해 구간합 배열을 이용하는 것이다. 상상도 못했네 배열 a를 모두 구간합 배열로 바꾸었.......

[백준] 13330 유사 팰린드롬 [내부링크]

딱 DP 점화식이 나오는 문제인데, DP[i] = 0~i 까지 쎄타 팰린드롬을 만들때의 최소 개수라고 하자. j = 0 ~ i - 1 까지 검사해보며 [j + 1, i] 구간이 쎄타 팰린드롬이 된다면 DP[i] = min(DP[i], DP[j-1] + 1) 을 해줄 수 있다. 그럼 [j + 1, i] 구간이 쎄타 팰린드롬이 되는지를 O(1)에 알 수 있다면 O(N^2)(정확히는 O(N*(N-1)/2)) 에 DP를 때려버릴 수 있다. 어떻게 O(1)에 알 수 있을까? 몰라 그냥 3중 for문으로 돌렸더니 O(N^3)로 통과함 ㅅㄱ 라고 할뻔 가장 쉬운 방법은 메모리를 512MB 나 주므로 n^2 짜리 2차원 배열을 전처리해서 사용하는 방법이다. 맞힌사람들 중 메모리가 10만 이상인 사람들은 이걸 쓴 것이다. 나.......

[백준] 18117 분수 [내부링크]

[백준] 14861 LCM 더하기 [내부링크]

오랜만에 mobius inversion 문제를 풀어본다. 예전에 풀려고 했다가 수식정리가 잘안되서 못풀었는데 다시 도전해보았다. 4시간동안 첫단추부터 잘못꿴 풀이로 꼬라박다가 그만두고 rkm 님 글을 참고해서 풀었는데, 일단 그 과정에서 Linear sieve, 각종 공식들, Mobinus inversion을 이용한 수식전개를 엄청 반복하며 오히려 이해도가 상승된 부분도 있는것같아서 나쁘진 않다고 생각한다. 일단 올바른 풀이부터 보고 그냥 아래엔 쓰다만 풀이를 안지우고 포스팅하겠다. 올바른 풀이 LCM(1~n, 1~m) 합 구하기 뒤에 부분을 빠르게 구할 수 있도록 전처리를 해두어야 한다. 안에 있는 dm(d) 는 승법함수이므로 위와 같은 식이 성립한다. 따라서 에.......

[백준] 17411 가장 긴 증가하는 부분 수열 6 [내부링크]

다른 풀이법들과 다르게 풀었다. 정해는 세그먼트 트리를 또 가만히 안냅두고 노드값에 <LIS 길이, 개수> 를 적절히 merge 해주며 관리해주며 LIS를 위처럼 구현된 MAX 세그먼트 트리로 찾는 방식과 비슷하게 구현을 해서 정답을 찾는 방식이다. 내가 푼 방식은 다음과 같다. 일단 뭘로든 각 인덱스의 LIS 값을 모두 찾아둔다. 동일한 LIS 값을 가진 인덱스들을 모아둔다. 이제 LIS 길이 차이가 1 나는 두개씩 살핀다. 두 인덱스들의 배열을 인덱스 순서에 따라 merge 한뒤에 LIS 길이가 1 짧은 인덱스들이라면 펜윅에 그 인덱스의 배열의 값에 그 인덱스의 정답을 업데이트 해준다. 반대로 현재 보고있는 길이의 인덱스들이라면 1부터 자.......

[백준] 210112 골드러시 [내부링크]

오늘은 골드에게 개털린 날이였다. 솔직히 한문제 한문제를 따지고보면 다 어디서 본 유형들이였지만 그냥 개털렸다는 표현이 맞다. A에서 B를 만든다면 2^50 가지 경우가 생기지만 B에서 제거를 하는 방향으로 간다면 그렇게 많은 경우가 생기지 않는다는 점을 이용해서 BFS를 돌린다. 그래프에 모순이 생기지 않는다고 했으므로 플로이드 와샬을 정방향, 역방향 두번 돌려서 어떤 소의 정방향, 역방향에서 도달할 수 있는 수의 소가 N-1 이 된다면 정확히 rank를 알 수 있으므로 정답에 세준다. 여기서부터 오늘 PS가 개말리기 시작했는데, 그냥 next_permutation 으로 하나하나씩 대응시켜주어서 검사하면 된다. 대응할 수 있는 숫자는 0부터.......

[일상] PS 이야기 [내부링크]

어저께 Div3을 치거나 오늘 문제를 풀면서 느낀건데, 문제를 푸는것에 대해서 왜인지 모르게 자만아닌 자만을 하게된것같다. 내가 세상에 존재하는 모든 문제의 1%도 풀지는 못했지만 백준에서 골드+플레를 꾸준히 푼 결과 도합 1700문제 가까이 풀게 되었는데 이쯤되니까 골드정도 되는 문제는 어디서 보거나 풀어본듯한 기억이 나는 문제일 확률이 30% 가까이 되는것같고(이제 골드에서 BFS 문제는 맞은사람 순으로 정렬해서 풀다보니 이제는 보지도못한다), 플레티넘도 약간 웰노운성이 있거나 흔한 DP인 경우 빠른시간안에 많은 고민않고 풀이가 떠오를때가 가끔 있다(특히 골드3-5, 플레 4-5는 맞은사람 순으로 밀면 똑같은게 계속 튀어나오.......

[백준] 12763 지각하면 안 돼 [내부링크]

첨엔 그냥 무지성 100만개 노드의 BFS로 풀었는데 1500ms 정도로 그냥 통과가 되어버렸다. 빠른 풀이는 다음과 같다. N과 L이 작다는 점을 이용해 DFS로 브루트포스를 진행하면 된다. 이러면 120ms가 나오는데, 여기서 좀더 최적화를 위해 각 정점마다 pair로 <최소 시간, 최소 돈> 을 갖고있는다. 이제 u -> v 로 가려고 할 때 v의 pair 중 더 작아지는 값이 하나라도 있는 경우에만 진행한다. 이렇게 하면 8ms 가 나온다. 아래 주석을 해제하면 방금 말한 최적화를 사용하는 것이다.

[백준] 2285 우체국 [내부링크]

1차원이나 몇차원(맨하탄 거리면 N차원을 각각 생각해주어서 1차원 문제 N개로 변형 가능)에서 N 개의 점 중 어떤 위치에서 N개의 점의 거리의 합이 최소가 되는.... 같은 문제는 흔한 description인데, 이 값들중 중앙값이 항상 최소가 되고 sum(x)는 unimodal 한 그래프 개형을 그린다는 것을 숙지하고 있어야 한다. 왼쪽과 오른쪽의 점의 수가 같은 구간이 있다면 위와 같이 기울기가 0인 구간이 선으로 존재하게 되고, 딱 오른쪽 왼쪽 수가 같은 지점이 한군데라서 점이라면 아래로 뾰족하게 된다. 이 문제는 누적합을 구해서 그 뾰족한 구간을 찾는 문제이다. 문제 분류엔 큰수연산이 있지만 당연히 이 방법으론 큰수연산이 필요하지 않다. .......

[백준] 2658 직각이등변삼각형찾기 [내부링크]

구현 문제였다. N이 10정도로 작으므로 구간합 배열은 필요하지 않다. 일단 일반성을 잃지않고 딱 두 가지 삼각형 모양만 나온다. 이러한 모양이 아니라면 배열을 90도 돌려서 찾아주면 된다. 찾아준다음에 전체 1의 개수와 삼각형내에 포함된 1의 개수가 같은지를 확인하고, 그렇다면 점 세개를 찾은뒤에 돌려준만큼 다시 반대로 돌리거나 4-돌린횟수 만큼 더 돌려서 원래 좌표를 복원한뒤 정렬해서 출력하면 된다. 말은 간단한데 구현이 더럽다.

[백준] 22899 오렌지컵 출제하기 [내부링크]

뭔가 우선순위 큐를 쓰는것같은데 해답을 도출해내기 어려웠고, 더럽게 풀었다. 내 풀이를 정리한뒤 다른 더 간단한 풀이를 정리하도록 하자. 내 풀이 출제할 수 있는 문제가 하나씩 늘어나는게 아니라 하나씩 줄어든다고 해보자. vector<set<int>> submit(N + 1) 같은걸 선언해서 현재 X 개의 문제를 낸 사람들의 인덱스를 관리할 수 있다. 처음에는 모두가 문제를 N개 낼 수 있으므로 b가 작은순으로 정렬해서 K개를 앞에서부터 뽑아오는게 최적일 것이다. 그리고 N-K 개가 남아있다. 이제 N-1 부터 1까지 문제 출제수를 줄인다고 생각해보자. 어떤 문제를 L개 이상 출제한 사람이 있다면 그 사람의 문제는 빠져야되고, 남은 N - K.......

[백준] 7476 최대 공통 증가 수열 [내부링크]

이 문제는 당연하게도 역추적 DP이지만 시간복잡도를 개선하는 과정이 까다로울 수 있다. 결론적으로 O(N^3)에 문제를 해결할 수 있다. dp[i][j] 를 A는 i에있고 B는 j에 있을 때 (항상 A[i] == A[j]) A와 B각각 i, j 뒤에있는 것들을 이용해서 공통증가수열을 만들때 최대 길이 이다. 그럼 i + 1 ~ N - 1 까지 A를 살펴보며 A[i] 보다 큰 녀석이 나오면 일단 그것을 다음 i 값으로 사용해줄 것이라고 생각할 수 있다. 그럼 B는 어쩔것인가? j 보다 큰 인덱스 중 A[i]와 같은 원소가 가장 빨리 나오는 인덱스를 선택해주면 된다. 그리디하게 생각했을 때 당연히 더 앞에 있는걸 선택해주는게 최적이다. 이는 전처리로 O(N^2)에 구할 수.......

[백준] 1226 국회 [내부링크]

Knapsack + Greedy 어질어질하다 문제를 그리디 태그에서 하나 고른거라 그리디인건 알았는데 아무리 생각해봐도 뭔가 냅색스러운 풀이가 나왔다. 총 합이 10만인 것도 그렇고 뭔가 O(NM) 으로 푸는 문제같았다. 중요한 관찰을 하나 했어야 했는데, pivot = total / 2 + 1 라고 하자. 인원수가 k 인 당을 연합에 포함시키려면 무조건 연합의 크기는 [pivot, pivot + k - 1] 이여야 한다는 점이다. 따라서 당을 인원순으로 정렬하고 뒤에 x 개만 보는것으로 연합에 포함될 가장 작은 당인원이 k명일 때 연합의 최대 크기와 k 이상을 가진 당끼리만 연합을 형성해준다고 보면 된다. 이제 냅색을 쓸 차례인데, 뭔 말도안되게 처음에 냅색을 작.......

잔소리 [내부링크]

이딴거 만들지말고 인라인수식이나 해달라고 네이버블로그 개같은 SEO는 덤

[수학] 키타마사법 - きたまさ法 [내부링크]

이 글은 키타마사법에 대해 다루나 FFT를 사용해 더 시간복잡도를 단축하는 구현을 담지는 않는다. 분할정복을 이용한 거듭제곱(exponential by squaring)과 행렬곱 거듭제곱 를 계산하는 것은 곱셈이 O(1)에 수행된다고 가정할 때, 나이브하게 계산하면 O(n) 이지만, 과 같은 성질을 이용해 n을 2진수로 표현해 빠르게 거듭제곱을 하면 이 걸린다. 이를 좀더 나아가 행렬곱에 적용시켜 피보나치 수열을 더 빠르게 찾는 방법이나, 행렬그래프가 주어졌을 때 0초에 어떤 위치에 있고 T초뒤에 어떤 위치에 있는 경우의 수를 계산하는 방법에는 행렬의 곱은 O(m^3) 이기 때문에 이 걸리게 된다. 선형 점화식 피보나치 수열의 점화식을 보자. 이고 이.......

[백준] 10562 나이트 [내부링크]

X가 1, 2, 3, 4 일때 각각 45개 정도의 초항을 구해서 벌레캠프로 점화식을 구한 뒤, 키타마사법이나 행렬거듭제곱으로 해결할 수 있다. 초항을 구하는 과정은 비트필드 DP를 이용해서 구해주면 된다. 나이트의 특성상 위에 두 row만 봐주면 되기 때문이다.

[일상] 3일째 술을 먹는다 [내부링크]

요 조합으로 주말부터 심심해서 공부빡세개 하고 난뒤에 3일째 먹고있는데 맛있습니다. 오늘은 공부하기 전이지만 먹고 slope trick을 더 이해해봐야겠군요

[CF] Codeforces Round #764 (Div. 3) [내부링크]

오늘 있었던 Div3 업솔빙 오늘 술을 먹어서 그런지 컨디션이 안좋았는데 D에서 크게 말려 E까지밖에 못풀었다. F 인터랙티브 문제인데 로컬에서 테스트가 쉽도록 템플릿을 하나 짜두었다. 어쨋든 이 문제는 그냥 이분탐색인데, 실제로 이분탐색처럼 구현을 하려고 하면 말린다. 이분 탐색 문제인데 문제의 조건대로 그대로 구현을 하면 된다. 1부터 n-1 까지 수들을 벡터에 넣고 벡터에 존재하는 수들중 중간값을 n에서 뺀것을 쿼리를 날리면 배열은 반씩 줄어들게 된다. 남아있는 숫자들만 다시 배열로 옮겨서 숫자가 1개만 남을때까지 해주면 된다. 처음 숫자를 찾는건줄... G 이것도 그냥 비트를 하나씩 큰것부터 보는 브루트포스 + DSU 문제.......

[DP] Slope trick 공부 - BOJ - 19693 Safety [내부링크]

어저께부터 Slope trick을 공부하고 있는데, relation이 딱 정해져 있어서 점화식을 세우고 Monotonicity 같은 트징을 찾으면 적용할 수 있는 DP 최적화 기법들인 Convex hull trick, D&C Opt, Knuth Opt 등보다 정말 이해하기도 어렵고 난해하다. 기본문제부터 다이아 3을 찍고가는 이유가 있다. 아직 Slope trick에 대해 뭔가 글을 쓸 이해도도 안되기 때문에 이 문제를 접근하고 푸는 과정을 다시 곱씹으며 이해도를 높혀보려 한다. 이 글을 Slope trick을 처음 배우는데 공부할 용도로 쓸 순 없을 것이다. 나도 아직 이해를 해가는 과정이기 때문에 이론이 불완전한 부분이 있을 수 있다. Description & Relation 일단 이 문제에서 요.......

[백준] 13323, 13324 BOJ 수열 1, 2 [내부링크]

아쉽게도 2연콤을 하지는 못했다. 역추적이 그냥 값을 구하는것과 난이도차이가 별로 없다고 하는데 아직 Slope Tirck에 대한 이해가 부족한 것 같다. BOJ 수열 1은 그냥 이문제에서 설명한 두 set을 관리하는 버전에서 한쪽만 관리해도 되는 더 쉬운 버전이다. 사실 Slope trick의 대표적인 기본 문제라고 할 수 있다. 일단 B가 증가함수(increasing)여야 된다는 조건이 있는데, 모든 A[i]에 i를 빼줌으로써 비감소 함수(non-decreasing)를 찾는 문제로 변환할 수 있다. 이를 normarlize라고도 한다. 코드를 한번에 첨부한다. 최종 DP값 찾기 이렇게 구현해주면 정답값을 찾을 수 있다. 역추적 코드를 보면 정답을 찾는 과정에서 rightmost란 배.......

[백준] 6569 몬드리안의 꿈 [내부링크]

비트필드 DP중 플레티넘 중위권에 흔하게 나오는 문제이다. 예전에 봤을땐 감이 잘 안왔는데 오늘 다시보니 풀 수 있었다. dp[y][state] 를 현재 y와 y-1 칸이 어떻게 채워져있는지 state 라고 해보자. 공간복잡도는 dp[11][1<<11] 만 필요하다. 일단 state 에서 안채워져있는 곳은 세로로 블록을 무조건 끼워넣어야 하므로 넣어준다. 그리고 이제 남은 공간중 가로로 끼워넣을 수 있는 인덱스를 0 ~ X - 2 까지 모두 찾고 이를 또 브루트포스로 넣고 안넣고를 모두 완전탐색한다. 완전탐색하며 가로로 끼워넣는 인덱스중 1차이나는 것이 있으면 겹치게 끼워넣는다는 뜻이므로 세주지 않는다. y가 Y가 되고 Y-1 행이 모두 차있을 때 (state.......

[백준] 2454 트리 분할 [내부링크]

오늘 플레티넘을 많이 풀어서 간만에 만족스럽다. 플레 러시 성공 그리디 풀이 내가 풀어보고 뭐가 정해인지 보려고 jh님 블로그를 참고했다. <A, B>(경로 개수, i가 포함된 경로의 정점 개수) 를 dp로 두었을 때 B가 정점 개수면 B를 기준으로 오름차순 정렬해서 앞에것 한두개씩만 봐주는게 최적이다. 왜냐하면 자식 한개랑만 묶어줄 시에는 무조건 결과로 반환할 A의값은 변하지 않기 때문에 B가 가장 작은거랑 이어주는게 최적이고 자식 두개랑 묶어줄 시에는 무조건 A의 값이 1 줄고 젤 작은것 두개랑 묶어주는게 최적일 것이기 때문이다. 자식이랑 어떻게 이어주느냐에 따라 A의 값이 항상 고정이 되기 때문에 B로 정렬을 해주고 가.......

[백준] 3329 Ministry [내부링크]

Tree isomorphism을 연습하려고 풀어봤는데, 풀다보니 해싱 없이 푸는 방법을 모르겠어서 그냥 해싱을 썼다. 맞은 분들 코드를 봤는데 다 해싱을 쓰긴 하셨다. 일단 스택으로 괄호 문자열을 적절히 파싱한 뒤, 부모 자식관계를 적절히 이어 트리를 구성하고 공부한데로 level이 낮은 것부터 검사해주며 서브트리를 하나의 값으로 나타낸 뒤 적절히 노드의 라벨을 정해준다. 라벨을 정할 때 주의해야할 건 이 문제에서 정의하는 depth 라는 것이 일반적인 트리의 depth와 다르다는 것이다. 루트에서부터 레벨이 아니고 가장 루트로부터 멀리있는 leaf와의 거리가 depth가 되는것같다. 해석이안돼;; 따라서 해싱없이 라벨링을 같은 depth에 대해서.......

[백준] 2,700 Solve [내부링크]

살려줘

[백준] 3614 정사각형 [내부링크]

f 함수를 정의해야한다는것에서 좀 애를 먹었는데 찾아보니 위와 같은 문제도 있는걸보니 웰노운인듯하다. f 함수 식이 저렇게 나오는 이유는 대략 아래와 같은 블로그에서 설명을 보면 된다. g=1 일때는 x + y - 1개이고 나머지 경우는 gcd로 쪼개서 보면 수식을 세우면 된다. gcd(a, b) = g 일때 a/g와 b/g는 서로소라는 것으로 증명 가능하다. 시간복잡도 1등!

[백준] 2911 전화 복구 [내부링크]

집의수는 아무래도 상관없다. 두 집이 여러번 통화하면 안된다는 제한은 없기 때문이다. 그냥 x 좌표 순으로 정렬하고 전화 횟수를 산처럼 깎아내려가면 된다. USACO 에서 몇번 나올 정도이고 이걸 그냥 구하라고 하면 실버급이 되는 문제인데, 문제를 읽고 그것임을 파악하는 난이도가 있는 문제였다.