그냥 하는 노트와 메모장

* BOJ 10564 - 팔굽혀펴기[분류 - 다이나믹 프로그래밍] 처음엔 생각나는대로 풀었는데 시간과 메모리가 마음에 안들어서 계속 생각하다 문득 떠오른 풀이를 공유하고자 합니다.[첫 풀이]2차원 배열에서 dp[누적 회수][팀이 득점한 총 점수]로 설정해서 O(M N^2) 시간 복잡도를 갖는 풀이를 써봤습니다. 직관적이고 이해하기 쉬워서 작성은 금방했습니다만, 여러 테스트 케이스를 고려하면 "누적 회수"가 "팀이 득점한 총 점수"에 의존적으로 결정되기 때문에 N^2을 모두 채우지 않을거라는 기도 메타에 약 800ms으로 풀이가 맞았습니다. [보다 확실하고 효율적인 풀이]'이전 경기 결과에서 다음 경기에 점수 얼마를 얻었다'가 아니라 반대로 생각해봅시다. '첫 경기를 추가해보자'라고.그러면 문제는 갑자기 ..

* BOJ 14559 - Protocol[분류 - 수학, 다이나믹 프로그래밍] 아이디어를 생각하기 어려운 문제.. 구하고자 하는 건 M세대를 거쳐 2^M개의 112345^k꼴로 표현되는 수의 합입니다. x+1 세대의 합을 x 세대로 표현이 가능해야 큰 수 M에 대응할 수 있습니다. 하지만 f(x), g(x)로 x+1을 나타낼 수가 없습니다. 즉, 다른 트릭을 쓰지 않고서는 범위를 줄일 수 없고, 점화식을 구할 수 없습니다. (페르마 소정리) 임의의 소수 p에 대해 임의의 양의 정수 x(x 1); return h * h * (n % 2 ? a : E); } int _pow(int a, int n) { if (n > 1); return ((ll)h * h % MOD) * (n % 2 ? a : 1) % MO..

* BOJ 13011 - 사탕의 밀도[분류 - 수학] 굉장히 재밌는 문제. 아래 수식을 생각해보자. 우리의 목표는 최종 비용을 최소하는 것이 목표다. 이는 곧 total cost를 최소화 하는 것임을 알 수 있다. 여기서 x를 곱한다고 한들 최소성에 대해 영향을 주지 않는다. 또 하나의 값에 대해 Wi개로 나눠보자. 하나가 아니라 모든 i에 대해 분해를 하고나면 |x-Ci/Wi| 형식으로 통일할 수 있다. 여전히 이 합을 최소화 하는 것이 문제에서 원하는 목표와 동치임을 계속 생각하고 있어야 합니다. 를 만족하는 x값을 x좌표에 찍어봅시다. 이제 이 합을 최소화하는 x의 위치를 특정해야 하는데 그 x의 위치가 정해지면 합은 찍었던 모든 x좌표와의 거리로 볼 수 있습니다. 자 x가 찍힌 두 점 사이에 있다..

* BOJ 13010 - h(n) [분류 - 정수론, 이분 탐색] 탐색 범위 실수로 왜맞틀을 계속한 문제..ㅜ [풀이] 문제를 읽으면 소인수분해를 하고 싶어지지 않으십니까. 그래서 먼저 소인수분해 해줍니다. 여기서 n=h(x)=x^d(x)를 만족하는 x 중 가장 작은 x를 찾는 것이 문제인데요, d(x)는 x의 약수의 개수이기에 하나의 수입니다. 따라서 소수 Pt를 인수로 몇 개로 갖는지를 나타내는 Ck로 묶어낼 수 있어야 합니다. 따라서 d(x)의 후보 집합을 A로 나타내면 아래와 같습니다. 이 집합은 최대공약수로 쉽게 구할 수 있습니다. 따라서 답을 구할 때 소인수 분해하고 승수에 대한 최대 공약수를 구한 뒤, 모든 가능한 d(x)에 대해 x를 역으로 구한 뒤 이 x의 약수의 개수가 d(x)와 같은 ..

* CS Academy - Substring restrictions [분류 - DSU/ Dynamic programming] 심플한 문제에 비해 굉장히 난이도가 높은 문제입니다. 처음엔 레이지 세그트리로 덤볐다가, 시간초과와 메모리 초과를 동시에 받아버린.. [해설] 쿼리 len x y를 로 표기하고 'x부터 x+len-1까지 각각을 y부터 y+len-1까지 각각을 같게 보겠다'라는 의미로 보겠습니다. 가장 간단하게 브루트포스로 먼저 생각해봅시다. 이를 구현하기 위해서는 단순히 하나의 반복문으로 해결할 수 있습니다. 이 때 '같아야 한다'를 DSU에서의 union(또는 merge)의 의미로 받아주시면 되겠습니다. 당연히 범위가 10^11까지 올라가므로 O(NM)으로는 시간이 만족할 수 없습니다. 이제 우..

* BOJ 1056 - 수[분류 - 정수론, 가지치기, 다이나믹 프로그래밍, 최단경로 알고리즘] 수의 범위만 봐도 10^18이기 때문에 메모리나 시간 측면에서 단순 다이나믹이나 BFS로 구현할 수 없는 문제입니다. 이 사실만 봤을 때 가지치기가 필수임을 알 수 있는데, 1번과 2번 연산으로는 절대로 시간이나 메모리를 줄일 수 없습니다. 따라서 3번 연산을 가지고 놀아야해요. 반대로 N에서 1로 만든다고 생각하고 진행해봅시다. [해설] 전제 1) 임의의 수 N에 대해 어떤 자연수 x제곱에 가장 가까운 지점은 최대 두 개의 지점이 있다. 하나를 a^x라고 하면 또 다른 하나는 (a+1)^x로 둘 수 있다. 즉, 두 지점의 밑은 정확히 1 차이가 난다. 증명 1) 가장 가까운 두 지점이 a^x, (a+y)^x..

* BOJ 12977 - 원 위의 점[ 분류 - 조합, 확률 ] 원호(circular arc)는 (각도)x(반지름)으로 정의됩니다. 즉 그 각도만큼 비례하게 되죠. 따라서 한 점을 골랐을 때 그 점이 p각호을 가지는 원호 A에 있을 확률은 p/360가 됩니다. N개의 점 모두 독립적으로 선택되므로 독립확률이구요. P[1개의 점이 A 내에 있을 확률] = p/360 N개의 점은 모두 서로 다른 점으로 유추할 수 있습니다. 원호는 이산(discrete)값이 아니라 연속값이기 때문에 중복 선택에 대한 의미가 없습니다. 즉 N개의 점을 모두 같은 위치를 선택하는 확률은 서로 다른 점 N개를 선택하는 경우에 대해 0이라고 보기 때문이죠(선 위에 있는 한 점의 길이는 0으로 보는 것처럼). 원호에 존재하는 점의 수..

* 온코더 제12회차 3번 문제 '격자 칠하기' 풀이 [ 분류 : 구현/조합/확률 ] 예전에 못풀었던걸 최근에 확률 공부하다가 생각나서 풀어봤는데 풀려서 기분이 좋다 ㅎㅎ 문제 요약) N x M 격자에서 총 K번의 연산을 수행한다. 연산은 격자 내부에서 두 칸을 선택하여 두 칸을 양끝으로 하는 사각형 내부에 색을 칠한다. 이 때 칸을 선택하는 확률은 모두 동일하며, 다른 칸을 선택하는 확률과 독립적이다. K번 연산을 모두 끝낸 뒤 칠해진 1 x 1 칸의 개수의 기댓값은 얼마인가? 해설) [확률] 연산 한 번에 대해서 생각해보자. N x M 격자에서 하나의 칸을 선택하는 경우의 수는 NM 임은 쉽게 알 수 있다. 또한 두 개의 칸을 선택하는 경우의 수는 (NM)^2 이다. 이는 칸 선택이 서로 독립적이기 ..

* BOJ 2176 합리적인 이동경로[분류 : 다이나믹 프로그래밍/ 최단 경로] 분류에서 보이듯 굉장히 희한한 문제다. 심지어 그래프 + 다이나믹인데, 트리 + 다이나믹은 익숙하지만 이런 조합은 처음 봤다. [풀이] S에서 T로 가능 경로는 반드시 T로 가까워져야 한다는 조건이 있는데, 이는 거꾸로 말하면 T로 멀어지면 안된다는 뜻이다. 보다 정확하게 말하면 S에서 T로 가능 경로 중에 사용된 간선 집합을 P라고 정의할 때, 방향 간선 (u, v)에 대해 u 위치에 있을 때보다 v로 이동하면 T에 더 가까워져야 함을 알 수 있다. 정리하면 아래처럼 정의할 수 있다.증명) 역으로 u가 v보다 T로부터 가깝다고 하자(du < dv). 그렇다면 현재 위치 u까지 왔을 때, T에 가까워지기 위해서는 v로 이동했..

* BOJ 17242 Kaka & Bebe[분류 - 최단 경로/ 그리디] 최단 경로를 구하는 문제. 뭐랄까 각 정점당 상태를 나타내고자하면 c의 상한이 1000이고 d의 상한 역시 1000이므로 1000 x 1000의 상태를 가질 수 있다.. 최대 정점의 수가 1000이니, 이를 모두 표현하고자 한다면 1000000000 = 10^9이므로 시간초과가 날 것임을 명확하게 알 수 있습니다.[해설] 전제 1) 각 정점에 대한 상태는 1000개 이하면 충분하다. 전제 1 증명) 각 정점당 1000 x 1000의 상태를 가질 수 있다곤 했는데,, 과연 1000 x 1000 상태가 모두 등장하는 경우가 있는지 생각해봅시다. 최단 경로 그리디 알고리즘 다익스트라를 쓴다면, 또는 상태에 대한 단순 BFS를 쓴다면 이전..

* BOJ 1866 택배 (https://www.acmicpc.net/problem/1866) [분류 - 다이나믹 프로그래밍] 구간에 대해 처리를 해야하나 싶었는데 엄청난 수학적 증명 + 다이나믹에 대한 처리가 있어서 소개하고자 합니다. 1. 우선 정렬을 합시다. 정렬을 해야 거리에 대해서 다음 위치를 계산할 때, 그 이전 거리들을 계산했다는 부분 구조로 만들 수 있습니다. 2. dp[i] = i 번째 지역까지의 최소값 먼저 구간 [1, N]에 대해 생각해봅시다. 가장 마이너한 0지점에서 트럭만을 이용할 경우 T * pos[i]의 비용이 발생합니다. 반면, 헬기를 이용하는 경우를 생각해봅시다. 최적으로 헬기와 트럭을 배정했다면 하나의 헬기가 담당하는 지역의 위치는 반드시 연속적입니다. 비연속적이라면 비용..

* FFT (Fast fourier transform) 문제들어렵긴 어려운데 "상대적"으로 쉬운 문제들을 소개합니당 1. Golf Bot(https://www.acmicpc.net/problem/10531)FFT 활용에 가장 기본적인 지수에 대한 처리를 다루는 문제다. 문제는 한 개의 정수 리스트에서 중복을 포함하여 두 수를 뽑아서 더한 결과를 리스트로 만들어야 한다.들어오는 쿼리가 결과 리스트에 포함되어 있는지 아닌지를로 판단해야 하는 문제임은 쉽게 알 수 있다. 하지만 두 수를 뽑아내서 더하여 리스트를 만드는 것은 의 시간이 걸리므로 명백하게 시간 초과임을 알 수 있다. 여기서 FFT가 등장한다. 곱셈에서 와 를 곱하면 이 된다. 이처럼 와 를 더하기 위해서 지수로 올려놓고 곱셈을 수행하는 것이다. ..

BOJ 2957 - 이진 탐색 트리 (BST) [ 분류 - BST ] 역시 이진 탐색 트리을 포함하여 자료구조 자체를 물어보는 문제는 증명 문제로 이어지는 것이 운명인가보다.. 당연하게도 삽입이 O(N)인 구조이기 때문에 O(N^2)으로 데이터를 확인하는 것은 시간초과로 이어질 수 밖에 없다. 명제) 삽입할 노드를 x라고할 때, 이 x는 직전원소(predecessor) 또는 직후원소(successor) 중 하나의 자식으로 가도록 되어 있다. 증명) 직전원소를 P, 직후원소를 S라고 지칭하자. 아래 상황을 고려해보자. 1. P와 S가 루트의 같은 서브트리에 있는 경우 x가 다른 서브트리에 삽입되려는 경우 P.key < x < S.key 이기 때문에 반드시 x도 같은 서브트리에 있어야만 성립 2. P와 S가..

BOJ 9522 - 직선 게임[ 분류 : 이분 매칭(Bipartite matching), Greedy, Game theory ] 문제가 다소 독특하여 포스팅하고자 한다. 나는 증가경로를 이용하여 접근해봤다. 문제를 보면 알겠지만, 한 점에 대해 x축 또는 y축에 그을 수 있으므로, 총 2개의 직선을 그을 수 있다. 그렇다면 처음에 게임을 시작하는 상근이는 시작할 점과 축을 정하고, 그 이후에 여기에 종속되어 번갈아 가며 이전 직선 위의 점을 선택해야 한다. 즉, 상근이는 점뿐만 아니라 축도 정할 수 있다. 축이 정해진 시점에서 x축과 y축이 번갈아가며 등장하는 구조가 될 수밖에 없다(1). 또 x와 y에 대해 이분 그래프를 구성할 수 있다. x축에 평행하는 서로 다른 두 개의 직선은 절대로 겹칠 수 없고..

[Network flow, MCMF] Graph modeling practices 네트워크 플로우 및 MCMF에서는 그래프 모델링이 큰 비중을 차지합니다. 모델링을 하고나서 플로우 흘리는 개념은 고정되어 있으나, 그 문제가 그래프인지 또 그래프임을 알더라도 모델링을 하지 못하면 풀기 못하는 경우가 허다합니다. 이 게시물은 그래프 모델링에 있어, 신기하거나 재밌게 느꼈던 문제 및 제가 어떻게 그래프 모델링 했는지 소개하고자 합니다. 물론! 다른 풀이가 있을 수 있으니 참고바래요 :) ※ 소스코드는 일부러 첨부하지 않았습니다. 제 소스가 궁금하신 분들은 댓글 남겨주시면 쪽지나 메일로 보내드리겠습니다. * 백준백준 사이트는 보통 문제가 2차 출처입니다. 원본 출처는 다른 곳이 있을 수 있으니 참고해주세요. 1..