그냥 하는 노트와 메모장

BOJ 8902 색상의 길이 [분류 : 그리디, 다이나믹 프로그래밍] [풀이] 하나의 색에 대해서만 생각해보자. 합쳐질 차선에 배치할 때 그 색상 중 가장 왼쪽에 올 수 있는 1차선의 후보와 2차선의 후보를 가려내보자. 순서상 같은 차선에서 같은 색상을 가지는 인덱스 i 3 a=5, F[0][a] -> 6 dp[a][b]=현재 1차선에서 a번째 후보와 2차선에서 b번째 후보를 사용할 수 있을 때 만족하는 최소 거리 (거리를 계산해야하는 색의 수) 나는 후보를 하나씩 사용하면서 거리를 계산했다. 현재 후보군 위치가 (a, b)이므로 이 이전에 사용한 데이터를 가지고 현재 어떤 색상을 쓰고 있는지(이하 usedCnt) 또 그 색상을 모두 배치 했는지(이하 doneCnt)을 알 수 있다. 각 색마다 가장 왼쪽..

BOJ 1226 국회 [분류 - 다이나믹 프로그래밍, 그리디] [풀이] 당을 하나씩 추가하면서 전체의 절반을 초과하는 경우를 봐야한다. $$a_i=의석수$$ $$total=\sum_{i=1}^{n} a_i$$ $$ half=\lfloor{total/2}\rfloor $$ [접근] 0부터 half까지 순회하면서 현재 좌석수를 더해줌으로 절반을 초과하는지 확인하면된다. [그리디] 단, 좌석수 기준 비오름차순으로 정렬한 데이터를 가지고 추가해야한다. 조건에서 보면 현재 좌석 수를 x로 구성했을 때 x를 만들기 위해 연합된 당들 각각 하나를 빼면 좌석수가 절반 이하이어야만 한다. 현재 당의 좌석수가 ci라고 할때 현재 당을 제외한 나머지 당으로 half를 구성했다고 치자. 그러면 half + ci도 정답 후보가..

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..

BOJ 2995 생일 [분류 : 세그먼트 트리] [풀이] [좌표평면] 구간의 왼쪽들을 x축으로, 구간의 오른쪽들을 y축으로 생각해보자. 좌표평면으로 옮긴 두 구간을 비교할 땐 두 점을 비교하는 걸로 동치로 볼 수 있다. 둘 중에 한 점이 x축이 작고 y축이 크면 다른 한 점(구간)을 포함한다라고 볼 수 있다. [정렬] 세그먼트 트리 갱신해야하기 때문에 정렬을 수행한다. 나는 x축을 비오름차순으로, y축을 비내림차순으로 접근했다. 이렇게 접근하면 방문하고 있는 x좌표는 지금까지 방문한 좌표들보다 무조건 작거나 같으므로 구간을 포함할 수 있는 가능성을 열어두게끔 한다. 반대로 y좌표는 같거나 작아야하는 좌표들 중 가장 큰 값을 가져와야하므로 구간 최대를 가져오기 위해 세그먼트 트리를 사용한다. 더보기 #in..

배낭 문제(냅색) 시리즈 - BOJ 12865 평범한 배낭, BOJ 12920 평범한 배낭2, Algospot SUSHI [분류 : 다이나믹 프로그래밍] 냅색 문제들을 모아 풀이를 공유하는 포스팅입니다. 이 포스팅은 희한한 냅색 문제들 보는 대로 갱신됩니다. 1. BOJ 12865 평범한 배낭 더보기 일반적으로 알고있는 냅색을 사용하면 된다. 시간 복잡도는 O(NK)가 된다. 재귀적으로 처리해도 좋고, 일차원 배열을 만들어서 큰 값에서 작은 값으로 내려가면서 데이터 오염을 피하며 dp를 구성해도 좋다. #include #include #include using namespace std; const int MAX_N = 100; int N, dp[MAX_N][100001], w[MAX_N], v[MAX_N..

BOJ 10563 정수 게임 [분류 : 다이나믹 프로그래밍] 은근히 어려운 문제.. [풀이] [구간 내의 수 선택] 현재 수를 뽑을 수 있는 구간을 [l, r]이라고 하자. 여기 안에서 조건에 만족하는, 즉 양 옆에 수들 모두 자신보다 작은 후보 집합 S={x | A[x-1] A[x+1]} 중에서 하나 x를 뽑았다고 해보자. [구간 밖의 선택] 그러면 구간은 [l, x), (x, r] 구간으로 나눠지고, 여기서 어느 구간을 선택할지를 고르면 되는데, 1이 존재하는 구간은 반드시 둘 중에 하나밖에 없다. 그 1이 포함되지 않은 구간을 선택하는 경우는 현재 내가 1이 포함되어 있는 구간 중 어느 수를 선택해도 반드시 질 경우에 유효할 수 있다. 가령 구간 [l, x)을 뽑으면 반드시 진다고 ..

BOJ 1555 소수 만들기 [분류 : 다이나믹 프로그래밍, 수학] [풀이] [순열] N개의 수에 대해서 각 자리수에 어떤 수를 둬도 상관없으므로 최대 N!은 먹고 들어간다. (C++에서 next_permutation 사용) [연산 규칙] +,-,*,/ 모두 사칙연산에도 쓸 수 있지만 특히 -는 사칙연산뿐만 아니라 단항 연산에 사용될 수 있다. 즉, 값을 음수면 양수로, 양수면 음수로 바꿀 수 있다. 단순히 두 피연산자 e1과 e2(e1가 왼쪽에 있을 때)가 있을 때 나올 수 잇는 방법은 아래가 있다 e1 + e2 e1 - e2 e1 * e2 e1 / e2 하지만 음수를 붙여주면 경우의 수는 배로 늘어난다. -e1 - e2 -e1 + e2 -e1 * e2 -e1 / e2 보면 1.~4.에 음수를 붙힌 것..

BOJ 1955 수식 표현 [분류 : 다이나믹 프로그래밍] [풀이] 할 수 있는 연산을 생각해보자. 덧셈 곱셈 팩토리얼 여기 세 가지 연산에서 항으로 들어갈 수 있는 표현식도 생각해보자. 대신 마지막 표현식만 생각하자. 표현식을 e1, e2로 둘 때 e1+e2, e1*e2, e1!로 표현이 가능하다. 따라서 n이 주어지면 1.에서는 단순 덧셈으로 구간을 나누고, 2.에서는 약수 판별을, 3.에서는 현재 값이 특정 표현식 e1의 팩토리얼인지 확인해서 다이나믹을 구성해주면 된다. 특정 표현식이라고 표기한 이유는 6! = (3!)!일 수도, (1+5)!일 수도 있기 때문이다. 더보기 #include #include #include using namespace std; const int MAX_N = 1e4 +..

BOJ 15487 A[j]-A[i]+A[l]-A[k] [분류 : 다이나믹 프로그래밍] [풀이] A[j] - A[i]를 먼저 계산해보자. 고정된 j에 대해 A[j]-A[i]가 최대가 되기 위해선 A[i]가 최소이어야 한다. 따라서 j를 순회하면서 [0, j) 구간에서 최소값을 유지하자. 나머지 A[l] - A[k]을 구간 (j, N)에서 구하면 된다. 이 부분은 거꾸로 진행하면 된다. 즉 k를 N-2부터 시작해서 2까지 감소시켜나가면서 A[l]을 최대값으로 유지하며 진행하면 된다. 이렇게 양쪽으로 최소/최대를 유지해나가며 그 중 최대값을 가져오면 AC를 받을 수 있다. 더보기 #include #include using namespace std; const int MAX_N = 1e6; int main() ..