devlog

출처 : https://www.acmicpc.net/problem/3197 풀이 방법 처음에는 매 번 visited를 초기화하고 BFS를 두 번씩 수행하면서 얼음을 녹이고, 백조가 만날 수 있는지 확인하는 방식을 사용했다. 그러나 이 방법은 시간 초과가 발생한다. 이를 개선하기 위해, 다음 턴에 녹일 얼음을 따로 큐에 저장해 두고, 해당 얼음들만 녹인 뒤 인접한 얼음을 다시 큐에 넣는 방식으로 변경한다. 이렇게 하면 불필요한 중복 연산을 줄여 얼음을 녹이는 알고리즘의 시간 복잡도를 낮출 수 있다. 백조가 만날 수 있는지 확인할 때에도, 첫 번째 백조 위치에서 BFS를 진행하며 물과 인접한 얼음을 별도로 저장한다. 이후 턴에서 그 얼음이 녹았는지 확인한 뒤, 녹았다면 그 지점부터 다시 BFS를 탐색하며, ..

출처 : https://www.acmicpc.net/problem/2042 풀이 방법 구간 합을 구하고, 요소를 변경하고 구간 합을 또 구하니 세그먼트 트리를 사용하면 된다. 세그먼트트리 구현 시 주의점세그먼트트리의 인덱스는 1부터 시작한다.node와 배열의 idx는 다르다build함수 구현시 start == end일 때 tree [node] = arr [start]이다.update를 할 때 원래 배열값과 차이인 diff값으로 업데이트를 진행한다.tree의 노드의 수는 일반적으로 n * 4로 잡는다.#include using namespace std;int n, m, k;long long arr[1000001];long long tree[4000004];long long build(int start, i..

특징트리의 모든 노드들은 오른쪽, 왼쪽 서브트리의 높이 차이를 {-1, 0, 1} 중 하나를 가짐노드 추가, 삭제 후 조건을 만족시키지 않는다면, 균형을 맞추는 작업을 진행한다. 노드 하나 씩 검사하며 만족하지 않는 노드가 발생한다면, 해당 노드에서 작업을 수행하면 된다.만족하지 않는 경우70에서 만족하지 않으므로 70을 기준으로 오른쪽 회전을 한다.60은 70이 원래 자신의 왼쪽 자식이 있었지만 비게 되었으므로 60을 70의 왼쪽 자녀로 해준다.노드의 삭제에서2번의 단계가 필요한 경우아래와 같은 경우 노랜 색만 집중을 해보면 60이 루트로 가야 완전 이진트리가 된다.1단계70을 기준으로 오른쪽으로 회전해 60을 70자리로 올려준다.2단계50을 기준으로 왼쪽 회전을 한다.이러면 완전 이진트리가 완성된다...