그래프 알고리즘 spfa, floyd-warshall [링크] [풀이] 예전에 풀었던 문제이나, 동아리 리뷰 문제로 나온 문제중 레이팅이 가장 높고, 이전에 짰던 코드를 보니 굉장히 복잡해서 더 간단하게 풀어보기 위해 건드려보았다. 먼저, '최대'이윤을 구하는 문제이고 문제 정의상 음수 간선에서 양수 cycle을 판별해야하는 문제이기 때문에 spfa로 해결이 가능하다. 일반적으로 spfa에서 cycle을 판별하듯이 판별하여 cycle이 있으면 바로 'Gee'를 출력하면 해결이 될까? 0 2 0 0 1 9999 1 2 9999 2 1 9999 0 3 0 10000 10000 10000 10000 이런 입력이 들어온다고 치자. 1과 2에서 cycle이 발생하므로 일반적으로 cycle판별 후 있을 때 retu..
투포인터 [링크] [풀이] 전형적인 투포인터 문제이나, '중복'되지 않게 처리해주기 위해 처리해주는 것이 약간 까다롭다. 입력배열을 a + b형태로 더한 배열($10^6$개)과 c - d형태로 더한 더한 배열($10^6$개)로 만들어보자. 여기서 투포인터를 돌리면 끝이다. 다만, 유의해야할 점은 1. 두 수를 더해서 배열을 만들 때 두 수는 서로 달라야한다. 2. 음수도 입력으로 들어올 수 있기 때문에 $n^2$개를 모두 만들어 주어야한다. 2중 for문을 $i$ from $0$ to $n$, $j$ from $i + 1$ to $n$으로 돌리면 음수의 경우에 답이 나오지 않는다. 3. 배열을 만들 때 값만 저장하는 것이 아닌, index도 같이 저장해둬야 중복을 처리할 수 있다. 4. 중복처리는 투포인..
UNION-FIND MST(크루스칼) LCA와 응용 [링크] [풀이] 전체 풀이를 설명하면 MST를 먼저 만들고, 쓰지 않은 간선들을 하나 하나 탐색해가면서 그 간선을 추가하면 CYCLE이 생긴다. 무조건. 그러므로 CYCLE을 제거할 수 있는 MST의 간선을 하나 제거한다. 그랬을 때 나오는 스패닝 트리의 값의 최솟값을 찾으면 두 번째로 작은 MST의 값을 구할 수 있다. 이제 제거할 간선을 하나 찾아야 하는데, greedy하게 생각해보면 cycle에 있는 간선 중 가장 큰 간선을 제거해야한다. cycle은 lca를 구하면 MST의 cycle을 찾을 수 있다. 문제는 lca까지 가는 간선 중 최댓값을 구해야하는데, naive하게 생각해보면 dfs돌리면 되니 O($n$)이다. LCA를 구하는 과정에서 L..
무려... 3년전에 3개월동안 고생하다가 못 풀고 입대 후, 전역 하고 풀었다... 가히 인간승리가 아닐 수 없다. [링크] [풀이] 머릿속에 맴돌던 아이디어는 딱 하나다. 아 이거 napsack dp같은데... dp테이블 하나의 값을 얻기 위해 필요한 정보는 1.현재 남은 날짜, 2.이제 선택할 레벨의 캐릭터, 3.남은 현재 선택할 레벨 캐릭터의 개수 라고 생각했다. $n$이 매우 작으니 dp table을 이렇게 구성해보았다. $dp[i][j][k]$는 $i$일 남았고, $j$레벨을 선택할 때, $k$개의 "더"캐릭터가 있을 때 "더" 얻을 수 있는 최대 레벨 로 구성했다. 여기서 "더"를 강조한 이유는, 문제에서 처음에 각 캐릭터가 얼마나 주어질지 언급이 없기 때문에, dp table에 그냥 캐릭터수..
533 [링크] [풀이] ps를 한창하던 2018년, 여름 즈음에 이 문제를 봤던 기억이 있다. 다른 알고리즘에 비해서 dp는 너무 어렵게 느껴져서, 풀다가 포기했던 기억이 난다. 아마 같이 문제를 봤던 형님은 얼마 안 가 풀었는데, 답지를 보자니 dp는 답지보면 너무 쉽게 느껴져서 다음에 풀어보기로 하고 군 입대를 했다.... 잡설은 뒤로하고, tree에서 dp를 쓰는 특이한 문제로 기억된다. 자, dp table $dp[i][j]$를 $j$가 0일 경우 => $i$번째 node가 얼리어답터가 아닐 때 $i$의 subtree를 완성시키는데(모두 수용하도록 하는데에) 필요한 최소 얼리어답터 수 $j$가 1일 경우 => $i$번째 node가 얼리어답터일 때 $i$의 subtree를 완성시키는데필요한 최소 ..
* 링크BOJ 2599 짝 정하기 * 풀이풀이는 간단하다. 출력해야할 값이 6개(3열 2행)인데 3개(2행)은 나머지 3개(1행)만 구하면 구할 수 있으므로 1행의 값들만 구하면 된다.입력으로 들어오는 값을$n$$a \quad d$$b \quad e$$c \quad f$라 하고, 출력할 값을$1$$x \quad (a \, - \, x)$$y \quad (b \, - \, y)$$z \quad (c \, - \, y)$라 하자.a, b, c, d, e, f는 모두 상수이고 x, y, z만 구하면 된다. 이제 식을 구성해보자.$a에서\, x명이\, e로,\, (a\, -\, x)명이\, f로\, 간다.\, 마찬가지로\, b에서\, y명이\, d로, (b\, -\, y)명이\,f로,\, c에서\, z명이\, ..
