그냥 하는 노트와 메모장

BOJ 1128 피보나치 냅색 [분류 - 브루트포스, 수학] 어렵다ㅏㅏ [풀이] [표현식] 제켄도르프의 정리(https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem)에 의하면 1보다 크거나 같은 자연수는 모든 계수는 0또는 1이고 인접한 피보나치 수에 대한 계수 ei × ei-1 = 0인 피보나치 수열로 표기할 수 있다. 또 이 수열은 유일(unique)하다. [전파] 가변량 ei를 i번째 피보나치 수에 대응되는 물건을 몇 개 쓸 수 있는지를 나타낸다고 정의하자. 주어진 무게 C에 대해 ei = 1인 가장 큰 피보나치 수 Fi에 대해 생각해보자. Fi 무게를 가지는 물건을 가방에 넣지 않으면 이 계수 ei는 이전 피보나치 Fi-1, Fi-2에 전파된다. 따라서 ei..

BOJ 18892 가장 긴 증가하는 부분 수열 ks [분류 : 다이나믹 프로그래밍] [풀이] [시작과 끝] 시작과 끝점이 K에 따라 달라질 수 있다. 모든 경우를 생각하기 귀찮으니 시작과 끝을 고정시키기 위해서 0번째에 충분히 작은 값(-10^9)을, N+1번째엔 충분히 큰 값(10^9)을 넣어주고 LIS를 구하자. 배열 A중에 0번째보다 작거나 N+1번째보다 큰 값은 존재할 수 없기 때문에 이 상태로 LIS를 돌려도 똑같은 답을 구해낼 수 있다. [추적] 0번째부터 시작해서 K번째 LIS를 찾아간다. 대신 사전순으로 처리해야하기 때문에 갈 수 있는 인덱스 구간을 정렬해주자. set을 이용하면 삭제도 편하고 정렬도 알아서 해주니 편하다. 정렬된 데이터에 대해 i번째에 접근했다고 하자. 그러면 세 가지 경..

BOJ 3217 malloc [분류 : 구현 / 세그먼트 트리] 최대 변수의 개수는 1000개, 또 메모리 할당 범위는 100 second >= _sz) break; cur++, nxt++; } if (nxt == allocated.end()) continue; else addr[var] = allocated.insert(nxt, { cur->second, cur->second + _sz }); } else { var = string(cmd).substr(cmd[0] == 'p' ? 6 : 5, 4); auto it = addr.find(var); if (cmd[0] == 'p') printf("%d\n", it == addr.end() ? 0 : it->second->first); else { if (..

BOJ 2507 공주 구하기 [분류 : 다이나믹 프로그래밍] [풀이] [O(N^3) 메모리] 가장 간단하게 p번째 섬을 출발 경로 또는 귀환 경로에 포함할지를 판단하는 dp를 생각할 수 있다. 하지만 이는 메모리 O(N^3)를 잡아 먹기 때문에 불가능하다. [접근 아이디어] 이런 왕복문제의 경우 시작점에서 도착점으로 가는 경로를 생각하자. 즉, 시작점은 항상 하나고, 도착점도 항상 하나로 두고 그 상태에서 서로 다른 경로를 구하면 그것이 곧 갔다가 오는 경로를 모드 셈해주는 것과 같다. [도달 검사] 첫 번째 섬을 제외한 나머지 섬은 반드시 한 번만 밟을 수 있기 때문에 왕복을 위해선 서로 다른 경로 두 개를 구성할 수 있는 경우의 수로 문제를 변형할 수 있다. 단, 한 경로는 현재 섬에서 현재 섬보다 ..

BOJ 4457 상근이의 자물쇠 [분류 : 다이나믹 프로그래밍] 독특한 문제 [풀이] [경우의 수] 트리를 구성할 때 트리 자체의 높이 h를 고정했다고 보자. 그러면 그 높이 h에서 n개의 노드를 배치해야 한다. h를 만드려면 현재 루트가 되는 노드를 제외한 두 서브 트리 중 하나가 반드시 높이 h-1를 가져야한다. 또 조건에서 두 서브 트리의 높이 차이는 1이하이어야 하므로 경우의 수는 세가지가 나온다. 왼쪽 서브 트리의 높이가 h-1, 오른쪽 서브 트리 높이가 h-1 왼쪽 서브 트리의 높이가 h-1, 오른쪽 서브 트리 높이가 h-2 왼쪽 서브 트리의 높이가 h-2, 오른쪽 서브 트리 높이가 h-1 [기저 사례] 기저 사례로는 h가 -1일 때 남은 노드의 수 n이 0이어야만 경우의 수로 포함시키도록 한..

BOJ 13433 기하 문제 [분류 : 브루트포스] [풀이] [순열] 기본적으로 N!을 생각할 수 있다. 단순히 원을 차례대로 나열하는 방법의 수로 생각하면 되겠다. (C++에선 next_permutation 사용) [유효성 검사] 원의 반지름 r1, r2, r3에 대해 r1 > r2, r3 > r2인 경우에 순서가 r1, r2, r3란 배치라면 유효성을 검사할 필요가 있다. 바로 이전 원 옆에 붙히지 못할 경우가 있단 의미다. [거리 계산] 바로 옆에 붙힐 수 없다면 x축 어디에 놓을 수 있는지 생각하기 전에 먼저 유효성 실패했을 때를 생각해보면 된다. 유효성 실패는 곧 아래 수식일 경우를 말한다. $$sqrt(x^2 + (r_{i} - r_{j})^2) \lt r_{i} + r_{j}$$ 결국 바로 ..

BOJ 12909 그래프 만들기 [분류 : 다이나믹 프로그래밍] [풀이] [노드의 수] 현재 노드 u에서 자식 노드를 추가하는 행위는 전체 사용할 수 노드 수가 줄어든다. 단 그 자식 노드를 루트로 하는 서브 트리의 크기(노드의 수)를 결정해줘야 한다. 당연한 소리지만 현재 N을 사용할 수 있다면 서브 트리의 크기는 최대 N-1다. [상태] 서브트리의 크기가 x라고 하자. 그러면 현재 노드 u에서 추가적으로 사용할 수 있는 노드 수는 N - x가 된다. 자식을 이미 하나 추가했으니 차수는 하나 증가한다. 결국 상태는 (노드 수, 차수)로 볼 수 있다. 노드의 수는 계속 줄어들 수 밖에 없으므로 이 상태를 유지하며 부분 문제를 해결, 부분 구조를 사용해주시면 되겠다. 더보기 #include #include..