그냥 하는 노트와 메모장

* 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 이다. 이는 칸 선택이 서로 독립적이기 ..

* 강한 연결 요소(SCC, Strongly connected components) - 코사라주(kosaraju)와 타잔(tajan) 알고리즘 이전에 SCC에 포스팅한 적이 있어요. 그 때는 코사라주 알고리즘에 대해서 공부한 적이 없었는데 이번에 CLRS 공부하면서 알게 됐습니다. 또 이 코사라주로부터 타잔 알고리즘을 더 쉽게 이해할 수 있게 되서 제가 이해한 방식으로 포스팅하려고 따로 글 올려봅니다. 먼저 코사라주 알고리즘부터 보겠습니다. * 코사라주 알고리즘 - 알고리즘 순서 1. DFS 한 번 돌며 모든 자식을 다 돌았음을 알리는 종료 시점 f[]를 저장한다. 2. G=(V, E)에 대해 transpose of G = G^T = {(v, u) | (u, v) in G}를 정의한다. 3. G^T에 대..

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

* 베주의 항등식, 확장 유클리드 알고리즘 [해당 포스팅은 두 정수의 최대 공약수를 구하는 유클리드 알고리즘 지식을 요구합니다.] 확장 유클리드 알고리즘을 설명하기 앞서 베주의 항등식을 통해 확장 유클리드 알고리즘의 (x, y) 해가 반드시 존재함을 보고 넘어가겠습니다. * 베주의 항등식 확장 유클리드 수식과 완전히 동일합니다만, 여기선 (x, y) 해가 반드시 존재함에 포커싱을 두고 있다는 점을 다시 인지하며 명제를 봐봅시다. 0이 아닌 정수 a, b에 대해 d를 a와 b의 최대 공약수라고 하면 수식을 만족하는 해 (x, y)는 반드시 존재한다. 특히 a와 b가 서로소이고 d=1이라면 베주의 항등식에 의해 정수해가 반드시 존재해야 합니다. * 계산 방식 먼저 유클리드 알고리즘을 이용하여 해를 어떻게 구..

* 오일러 피 함수(Euler phi function, ) 서로소 개수를 파악할 때 포함-배제의 원칙을 사용해도 되지만, 더욱 간단한 방법이 있습니다. 바로 오일러 피 함수의 특징을 이용하는 것입니다. 오일러 피 함수의 정의는 다음과 같습니다. =n보다 작으면서 n과 서로소인 수의 개수 * 성질 명제 1) 오일러 피 함수는 곱셈적 함수(Multiplicative function)이다. 즉 gcd(m, n)=1이면 이다. 증명) m X n 테이블이 있다고 해봅시다. 1부터 nm까지 수로 테이블을 열 순서로 채워서 아래처럼 만들어봅시다. 이 테이블에서 r행에 있는 모든 원소를 가져오면 다음과 같은 형태를 띄게됩니다. d=gcd(r, m)이라고 정의한다면 두 가지 경우가 나옵니다. 1. d > 1 d > 1인..

* 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를 쓴다면 이전..

* 페르마의 소정리 다른 이론의 근간 또는 여러 암호학 수학의 기반이 되는 매우 중요한 이론이라 함 알아봤는데, little theorem이라곤 하는데 다방면에 쓰이는 걸 보니 작은 정리이긴한데 매우 큰(?) 개념임을 알 수 있었습니다.. 단 이 포스팅에선 증명을 포함하지 않았습니다. 오일러 정리라던지 다른 개념을 알아야 하기에 나중에 포스팅할 숙제로 남겨놓겠습니다.. 페르마 소정리의 기본 명제는 다음과 같습니다.p가 소수이다. ^ a와 p는 서로소이다. -> 여기서 파생되는 명제 중 하나는 아래와 같습니다. 즉 a의 곰셈 역원는 이다. 이 명제는 modularity에서 수에 대한 매우 큰 승수를 구할 때 사용할 수 있습니다. 보조 정리 1) p와 서로소인 모든 a에 대해 인 1

* 마스터 정리(Master theorem) 마스터 정리는 일반적으로 재귀적으로 호출되는 함수에 대해 시간 복잡도를 알고 싶을 때 사용합니다. 단순 for문 중첩으로는 알 수 없는 것들을 계산해야 하는 경우가 있기 마련이죠. 종만북에서도 다이나믹 프로그래밍 구현을 재귀 형식으로 아주 쉽게 구현, 문제에 접근할 수 있도록 해준답니다. 하지만 시간 복잡도를 계산하지 않고 재귀로 짜다보니 시간초과가 날 것만 같은 것을 증명하지 못하고 코드로 짠 다음 시간 초과를 받고서야 깨닫는 경우가 있어서 정리해봤습니다. 시간 복잡도를 계산하기 위해서는 세 가지 방식이 있는데요.1. 치환법2. 재귀 트리3. 마스터 정리(또는 확장 마스터 정리) 치환법은 점화식을 보고, 직관적으로 점화식 형태를 도출해내고 그것을 증명하는 방..

BOJ 2419 - 사수아탕 [분류 - 다이나믹 프로그래밍] 어메이징한 문제다.. 이걸 어떻게 눈치채고 문제를 푸나 싶다 하하하.. 너무 으렵다 처음에 접근했던 잘못된 방식은 x축으로 정렬을 하고, 거기서 몇 번째를 뜻하는 구간 [l, r]을 잡고 [l-1, r] 또는 [l, r+1]을 부분 문제로 잡는다. 여기서는 왼쪽에서 끝났는지, 오른쪽에서 끝났는지를 알 수 있게끔 구성한다. 그리고 기저 사례를 왼쪽으로 더 이상 갈 수 없고 오른쪽으로도 더 이상 갈 수 없는 경우로 잡는다. 마지막으로 구간 [l, r]에서 몇 초에 도착을 했는지도 저장하도록 해서 거기서 먹을 수 있는 사탕의 수를 최대로 하는 방식으로 하면~ 메모리 + 시간 초과를 세트로 받을 수 있다. 풀이) 자 먼저 x축에 대해 정렬하고, 특정 ..

* n번째 문자열에서 k번째 문자 찾아가기 튜토리얼 이따금씩 n번째 문자열에 대해 n-1번째 또는 그 이전의 문자열과의 관계가 주어지고, n번째 문자열의 k번째 문자를 출력하라는 문제가 등장합니다. 가령 1번째 문자열 = "ffx" n번째 문자열 = "abcde" + n-1번째 문자열 + "fghijk" + n-1번째 문자열 처럼 점화식이 있는 상태에서 n번째 문자열의 k번째 문자를 출력하라는 겁니다. 보통 이런 문제는 실제 n번째 문자열을 직접 구성해서 거기서 k번째를 가져오도록 못하게 메모리 또는 시간제한을 둡니다. 즉, 문제를 접근했을 때 직관적으로 떠오르는 풀이는 틀리게 문제를 구성한다는 거죠. 따라서 문자열을 빌드업하며 계산하는 방식은 사용할 수 없습니다. 문제) 베이스 : = "abc" 점화식..