Union-Find - 처음에는 parent[i] = i로 초기화한다. - find로 조상의 루트로 갱신함과 동시에 리턴한다. 이를 통해 트리의 레벨을 최소화해 시간복잡도를 낮춘다. → 경로 압축 - 그냥 타고타고 올라가서 조상의 번호를 리턴하면 최대 시간복잡도는 $O(N)$이가 되기 때문이다. - 트리의 랭크는 높이와 같은 의미를 갖지만 경로 압축을 사용하면 높이와 다른 값을 가질 수도 있다. 따라서 높이 대신 랭크라는 표현을 사용한다. - 랭크가 작은 것을 랭크가 높은 것의 자식으로 만든다. 💚 2606 바이러스 - 컴퓨터가 연결된 상태가 주어진다. - 1번 컴퓨터가 웜 바이러스에 걸렸을 때 웜바이러스에 걸리게 되는 컴퓨터의 수를 구하는 문제 DFS를 통해 모든 컴퓨터 연결 상태를 탐색할 수 있다. ..

https://atcoder.jp/contests/abc256/tasks/abc256_c C - Filling 3x3 array AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 각 행과 각 열의 합이 정해져있으므로 만약 행과 열마다 2개 요소가 정해지면 나머지 하나의 요소의 값은 정해지는 구조이므로 N은 최대 30이고, 시간복잡도는 $O(N^4)$으로 그리 크지 않다. #include #include using namespace std; int h[3]; int w[3]; int arr[3][3]; int main() {..

https://atcoder.jp/contests/abc256/tasks/abc256_b B - Batters AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 시간 제한이 2초라서 사실 딱히 별다른 알고리즘을 풀지 않고 그냥 구현해도 무방하다. 그래도 그러면 재미없으니까 최대한 효율적으로 풀어보려 노력했다. 누적합(Prefix Sum)을 사용하면 시간복잡도 $O(N)$를 사용해 매 piece마다 마지막 위치를 예상할 수 있다. #include using namespace std; int arr[100]; int suffi..

https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 인간은 망각의 동물이라 그랬나.. 요즘 바쁘다보니 알고리즘 풀이를 2주 정도 쉬었더니 엄청나게 실력이 대폭 줄어있었다..ㅠ 더 열심히 하자...ㅎㅎ 우선 점화식을 잘 세워야한다. 메모이제이션의 대상은 추후에도 계속 사용될 가치가 있는 값이어야 한다. 그리고 여기서는 단순히 최대의 자두를 고르는 것이 아니라 제한된 이동 수 안에서 자두의 수를 최대화해야한다. 그렇다면 점화식에 필요한 파라미터는 시간, 현재 ..

LIFO의 특성을 활용 💚 9935 문자열 폭발 - 문자열 S에서 폭발 문자열 T를 모두 지우는 문제 - 스택에 넣는 것은 (문자열의 인덱스, 폭발 문자열에서 인덱스) - 현재 문자가 폭발 문자열의 첫 번째 문자와 같으면 스택에 넣는다. - 다른 경우에 스택에 비어있으면 그냥 넘어간다. - 다른 경우에 스택이 비어있지 않으면 스택의 가장 위에 있는 것의 폭발 문자열의 인덱스를 가져온다. 이 인덱스를 p라고 한다. - 현재 문자가 폭발 문자열의 p + 1와 같으면 스택에 넣는다. (p + 1이 폭발 문자열의 마지막 문자면, 폭발 문자열을 찾은 것이다. 스택에서 폭발 문자열을 지운다.) - 다르면 스택을 모두 비워버린다. - 폭발 문자열의 길이가 1이면 스택을 사용할 수 없기 때문에 그냥 for문을 돈다. ..

💚 2234 성곽 💥 여기서 쟁점은 하나의 벽을 제거해서 얻을 수 있는 가장 넓은 방의 크기를 구하는 일이다. 하나의 벽을 제거할 때는 최대 두 개의 방을 합할 수 있으므로 인접한 방의 크기 합의 최대를 구하면 된다. 따라서 방별로 인접성을 파악한 후 이미 구한 방의 크기를 활용하면 되지 않을까? 🎶 딩동댕동~ 앞서 푼 16932 모양만들기 문제와 유사하게 풀면 된다. 이를 위해 각 방의 정보와 해당 위치의 방 정보를 저장하는 작업이 필요하다. #include #include using namespace std; int n, m; // 성곽 int a[50][50]; // [i,j]의 방번호 int d[50][50]; // 방 i의 크기 int room[50 * 50]; // 문제에서 안내된 1,2,4,..