목록Algorithm/Memo &Tips (25)
블로그 옮겼습니다
시간복잡도가 \(4^N\) 일 것같지만 \(3^N\) 이라고한다. 이유는 잘모르겠음 걍 외우자ㅎ +이유를 깨달았다부분집합(1)의 부분집합(2)이니까부분집합(1) 에 포함되거나 안되거나고, 만약 된다면 부분집합(2)에 포함되거나 안되거나니까 결국1. 부분집합(1)에 포함되지만 부분집합(2)에는 포함되지않거나2. 부분집합(1)에도 포함되고 부분집합(2)에 포함되거나3. 둘다 안포함되거나셋중 하나이기때문에 3^N
12345678910111213141516171819int isOver1(line l1, line l2){ int ab = ccw(l1.p1, l1.p2, l2.p1) * ccw(l1.p1, l1.p2, l2.p2); int cd = ccw(l2.p1, l2.p2, l1.p1) * ccw(l2.p1, l2.p2, l1.p2); if(ab == 0 && cd == 0) { return !(l1.p2
1for(int subset = bit; subset ; subset = ((subset-1) & bit)){}cs
LCA(A, C) = C, LCA(B, C) = LCA(A, B) or LCA(B, C) = C, LCA(A, C) = LCA(A, B)가 참이면 존재하는거임
길이가 3인 단순경로일 때는 그래프 모양이 예외적으로 살짝 다르지만 4부터는 a개가 붙어있는 두 노드 사이의 노드개수만늘어날 뿐, 모양이 같다는 사실을 알 수가 있다. 예제: Three Tree (길이가 3인 단순경로의 개수N이 입력으로 주어질 때 트리 아무거나 하나 만들어 출력)http://lavida.us/problem.php?cid=1496&pid=4
사실 이건 너무 당연한건데 이 문제 에서 다른 복잡한 식안에 변형되어 숨어있으니까고보면 이 포스팅의 제목과 같은 문제라는 것을 파악하지 못하여 이 글을 메모삼아 올린다.가장 무식한 방법은 O(N^2) 로 모든 쌍을 봐주어 최소값을 갱신하는 것이다.그런데 사실 그냥 N개의 수 중에 가장 작은 두 수의 합이 답이 될 것이다. 그럼구현하기에는 정렬하여 0번째, 1번째 값의 합을 구하는 O(NlgN) 방식이 제일 깔끔하다.O(N) 에 구현하려면 사실 두개의 변수를 두어 구현할 수는 있지만 구현 방법에 따라조건문 처리해주는게 뭔가 귀찮을 수도있다. 이렇게도 한번 생각해 보자.m = 0~i-1 원소들중 최소값이기 때문에 m+A[i] 로 답을 갱신하고m = min(m, A[i]) 로 m을 갱신하는 식으로 반복문을 돌..
N 명의 사람이 각각 선물을 하나씩 준비해왔을 때 모두가 자신이 준비한 선물 이외의 선물을 갖도록 나눌 때그 경우의수를 구하는 문제 1 2 3 4 5 다섯명의 사람이 있다고 가정하자.맨 처음에 1번사람은 자신의 선물이 아닌 나머지 사람들의 선물, 즉 n-1 개의 선물을 가질 수 가 있다.그럼 그중에 하나의 경우인 1번사람이 2번사람의 선물을 가질 때를 생각해보자.그럼 2번사람이 받는 선물은 두가지 경우로 나뉜다. 첫번째, 1번사람의 선물을 갖는 경우. 그럼 1번 사람과 2번사람이 선물을 둘이 교환한 것과 같게 되므로D[i] : i명의 사람이 자신의 선물을 안갖도록 선물을 교환하는 경우의수일때, 교환한 두명을 제외한 나머지 n-2명에게 같은 행위를 반복하므로 D[n-2] 가 된다. 두번째, 1번 사람이 아..
예를 들어 소수 0.375 를 정수로 만들어 주기 위하여 곱해야 하는 최소 정수는 몇일까?답은 40이 나와야 한다.10의 거듭제곱꼴인 매우 큰 수 S가 있다고 하자. 그리고 주어진 소수를 p라고 해보자.그러면 p*S 는 정수가 될 것이 분명하다. (물론 가장 낮은 소수점 자릿수보다 10의 지수가 크거나 같아야만 한다)그렇다면 gcd(pS, S) 를 해보자. 만약 p가 정수였다면 gcd(pS, S)는 S임이 자명하다. 하지만 p 가 소수이기때문에p를 정수로 만들어 주기 위한 S의 최소 약수만큼이 빠질것이다. 그렇다면 p를 정수로 만들어 주기 위한 S의 최소 약수는 S/gcd(pS, S) 가 될 것이다. 그런데 잘 생각해 보면어떤 소수를 분수의 합꼴로 나타내보면, 즉 3*(1/10^(-1)) + 7*(1/1..
개인적으로 가장 알아야한다고 생각하는 네가지를 쓰겠다. 1번째\(\binom n k = \binom {n-1}{k} + \binom {n-1}{k-1}\) 예를 들어 생각해보면 쉬운데 어떤 반에서 n명의 학생중 k명의 대표를 뽑으려고하는데 이 때의 경우의 수는특정 학생 x 에 대해 두가지의 케이스로 나누어 생각해 볼 수가있다.학생 x를 뽑는 경우와 뽑지 않는 경우 이렇게 두 가지의 케이스이다.만약 학생 x를 뽑는다면 나머지 n-1 명의 학생들 중에 k-1명의 대표를 더 뽑아야 하므로 \(\binom {n-1}{k-1}\) 가지의경우의 수가 있으며, 학생 x를 뽑지 않는다면 나머지 n-1 명의 학생들 중에 k명의 대표를 뽑아야 하므로\(\binom {n-1}{k}\) 가지의 경우의 수가 있다. 그래서 두 ..