그냥 하는 노트와 메모장

BOJ 2638 - 치즈 [분류 - BFS] [풀이1] 빈 공간이 보장되는 (0, 0)부터 계속 BFS를 돌면서 4방향에 대해 2방향 이상에 공기에 노출되는 경우에 대해서 삭제한다. 그러다가 모두 지워지는 시점을 출력한다. [풀이2] 빈 공간 (0, 0)부터 시작해서 공기가 될 부분, 즉 치즈가 사라질 부분을 또다른 큐에 넣도록 한다. 그러면 그 위치부터 공기가 시작되는 부분이기 때문에 [풀이1]에서 사용한 (0, 0)에서 다시 돌릴 필요가 없어지는 것이다. 두 개의 큐를 사용하여 공기인 부분은 진행하고 치즈인데 2방향 이상이 공기에 맞닿은 부분이 있다면 다른 큐에 넣어두는 것이다. 이 방식은 따로 명명할 방법이 없어 나는 토글 큐(toggle queue)라고 부르긴 한다. #include #includ..

BOJ 1053 - 팰린드롬 공장 [분류 - 다이나믹 프로그래밍] [풀이] 4번 연산이 엄청 까다로워 보인다. 하지만 딱 한 번만 사용할 수 있으니 이에 대해 전처리를 진행해보자 1. 4번 연산을 사용하지 않는다. 2. 4번 연산을 사용한다(swap(s[i], s[j]), i != j). 나머지 연산에 대해서 생각해보자. 최소 연산수를 만족하기 위해서 삽입을 하거나, 삭제를 하거나, 특정 문자로 교환하는 행위는 반드시 팰린드롬을 만들기 위해 이득이 되어야한다. 다시 말하면 연산을 진행했을 때, 결과 팰린드롬의 일부가 반드시 되어야한다. 양끝부터 시작해서 팰린드롬 연산을 진행한다. 이 과정은 위의 4번 연산을 쓸 때와 안 쓸 때에 모두 계산이 필요하다. dp[l][r] = 구간 [l, r]에 대해 팰린드롬..

BOJ 2618 - 경찰차 [분류 - 다이나믹 프로그래밍] [풀이] 경찰차 1이 있는 (1, 1)을 1번 사건, 경찰차 2가 있는 (N, N)을 2번 사건, 그리고 나머지 N개의 사건을 3, 4, ..., N+2번 사건이라고 하자. 각 경찰차가 마지막 사건을 처리한 위치가 각각 a, b라고 하면 그 다음 사건을 처리할 때 그 사건의 번호는 max(a, b) + 1이 된다(순차적으로 진행해야 하므로). dp[a][b] = 경찰차 1이 a를 해결했고, 경찰차 2가 b를 해결했을 때 남은 모든 사건을 해결하기 위한 이동 최소 이제 문제는 꽤 간단해진다. 당연하게도 그 다음 사건 w(w = max(a, b) + 1)번 사건을 해결하기 위해서는 경찰차 1에 할당할 것인지 경찰차 2에 할당할 것인지 두 가지밖에 없..

BOJ 1600 - 말이 되고픈 원숭이 [분류 - BFS] [풀이] 말처럼 뛰는 동작은 k를 정확히 1만큼을 올리기 때문에 k+1과 k는 인접해있다. 따라서 k+1번째에 특정 좌표 (y, x)에 도달했다면 그 값이 곧 최소 동작이 된다. vi[k][y][x] - y행 x열에 k번만 말처럼 뛰어서 도달할 수 있는 동작 수의 최소값 BFS 특성상 진행하려는 방향에 대해 정확히 1만큼 증가시키고 vi[k+1][y][x]에 도달할 수 있는 위치가 (y1, x1), (y2, x2)일 때, 1. vi[k][y1][x1] > vi[k][y2][x2] BFS 큐에 들어가는 좌표는 (y2, x2)가 더 우선순위를 가진다. 2. vi[k][y1][x1] = 0) for (j = 0; j < n[i]; j++) { int ..

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