컴퓨터공학 💻 도서관📚

n n >> m :  n / (2의 m승)   컴퓨터 내부에는 2진수 형태로 값들이 저장되기 때문에, 2진수 형태로 저장되어 있는 값들을 왼쪽(>)으로 지정한 비트 수만큼 밀어주면 2배씩 늘어나거나 1/2로 줄어드는데, 왼쪽 비트시프트(오른쪽 비트시프트(>>)가 될 때에는 왼쪽에 0(0 또는 양의 정수인 경우)이나    1(음의 정수인 경우)이 개수만큼 추가되고, 가장 오른쪽에 있는 1비트는 사라진다.  예시 n = 10 print(nprint(n>>1) #10을 반으로 나눈 값인 5 가 출력된다. print(nprint(n>>2) #10을 반으로 나눈 후 다시 반으로 나눈 값인 2 가 출력된다. 정수 10의 2진수 표현은 ... 1010 이다. 10 10 >> 1 을 계산하면 ... 101 이 된다. ..

이 문제는 시간복잡도가 O(N x M) 이면 통과되는 시간 제한이 있다   가장 가까운 조상은 공통된 조상 중에서 가장 낮은 조상이라고도 할 수 있다 그렇기에 영어권에서는 (Lowest : 가장 낮은) 라는 단어를 사용한다           N과 M의 범위가 최대 10만개라고 하면 시간 초과 판정을 받는다 이때는 어떻게 해결하는가?     거슬러 올라갈 때는 가능하면 빠르게 2의 제곱꼴로 올라가게 한다 예시로 거리가 3이면 1번째에 2칸 올라가고 2번째에 1칸 올라간다      lca 함수에서 먼저, 항상 b가 더 깊도록 swap을 진행한다 (1

(이거 지금은 무슨 소리인지 이해 안 감)   2진법에서 모든 비트에 대해서 플립(0을 1로, 1을 0으로)을 진행하고 1을 더하면 7에서 -7이 된다 바이너리 인덱스 트리에서는 "0이 아닌 마지막 비트를 찾는 과정"이 효과적으로 사용된다   3 3 + 1 = 4 3 + 1 + 4 = 8 3 + 1 + 4 + 8 = 16 데이터의 개수가 N개일 때 특정 위치의 값을 바꿀때 최악의 경우에도 logN을 보장한다

이 문제는 간선이 음수가 될 수 있다는 조건을 제외하면 일반적인 다익스트라 알고리즘과 같은 조건이다    (음수 간선)2번 노드 : 2 + 1 + (-2) = 16번 노드 : 2 + 1 + (-2) + 2 + 2 = 5   (음수 간선 사이클) 음수 간선의 순환이 포함되는 경우에는 최소비용을 특정한 값으로 결정할 수 없는 경우가 발생할 수 있다 밑에 예시에서는 음수 간선의 사이클이 발생한다 이때 싸이클에 포함되어 있는 모든 간선에 대한 값을 모두 더하면 음수의 값이 나온다 이 경우에는 싸이클을 반복적으로 도는 과정을 통해서 비용을 무한히 줄일 수 있다그래서 그래프 내에 음수 간선의 순환이 포함되어 있다면, 최소비용, 즉 최단거리가 음의 무한인 노드가 발생한다 -4 + 2 + 1 = -2 -2 + (-2)..