나머지 연산을 포함한 다른 코드

큐에 넣어서 BFS를 하면, 트리의 최종 높이를 알 수 있다 일반적인 BFS와 다르게 트리 구조는 사이클이 없는 구조이기 때문에 check 배열 없이 수행할 수 있다

7의 배수 판정법 예) 48216 뒤에서부터 세 자리씩 끊는다. 48/216 홀수번째 수의 합 - 짝수번째 수의 합을 계산한다 216 - 48 = 168 절댓값을 취해 양수로 만든다 그 값이 7개의 배수 혹은 0이면 7의 배수가 된다 168/7 = 24로 7의 배수다

임의의 배열과 일정한 간격이 주어졌을 때, 일정한 간격 안에서의 최솟값을 찾는 알고리즘을 슬라이딩 윈도우라고 한다 배열의 길이를 N이라고 할 때 각 구간에서의 최솟값을 O(N)의 시간복잡도에서 해결할 수 있다 자료구조는 deque, 덱을 이용한다. 덱의 맨 앞에 최솟값을 위치시키고 다음과 같은 과정으로 슬라이딩 윈도우 알고리즘은 진행된다 1. 앞의 원소가 구간 L에 들어있는지 인덱스 검사를 하고 범위 밖에 있는 원소라면 제거한다. 그리고 2번 과정으로 들어간다 2. 뒤에서부터 자신보다 작은 최솟값들은 제거한다. 왜냐하면 뒤의 구간에서 현재 값보다 작기 때문에 최솟값이 될 수 없다. 제거하면서 자신보다 작은 값을 만나면 뒤에 바로 원소를 넣는다 3. 1, 2 과정을 거치고 나서 맨 앞에 있는 값이 최솟값이..

Lowest Common Ancestor로, 트리의 깊이를 모두 안다는 전제 하에 가장 가까운 공통 조상을 찾는 알고리즘이다 1. 두 트리의 깊이가 같아질 때까지, 두 트리 중 보다 깊은 트리를 올린다 2. 같은 노드가 나올 때까지 한 칸씩 올린다 이를 이용해서, 두 트리의 거리도 알 수 있다. LCA로 조상을 찾고, 두 트리의 조상까지의 거리를 더하면 그 것이 정점의 거리가 된다