개발블로그by페페

int treeHeight = 0; int length = N; while (length != 0) { length /= 2; treeHeight++; } *주의 : length /= 2 는 2로 나눈 몫 보다는, 다음 번의 length는 이번 length를 반으로 나눈다는 뉘앙스 *주의 : 트리 배열은 우측 반쪽이 N의 공간이며, 트리 자체는 최하단 리프 우측 반쪽이 아닌 최하단 전부를 공간으로 사용하고 있다 - 트리 모양을 생각하되 최하단 리프 전체에 N이 들어가 있는 부분을 생각 - 그리고 아래에서 위로 움직이면서 높이를 계산할 것이다 - N을 2로 나눌 수 있으면 트리에서 한 칸 씩 올라갈 수 있다는 말이고 높이가 1씩 더해진다는 것 - 이제부터 세밀한 부분 for 문에서 tree[i] 등을 pr..

(Briefing) (문제) (단 하나의 맥락) (입출력과 되어야 하는 그림) N개의 수 수의 변경이 빈번히 일어나는 와중에 특정 구간의 곱을 구함 세그먼트 트리 + MOD I // 수의 갯수 N, 변경횟수 M, 곱 구하는 횟수 K (2) 첫번째 수 ... (N+1) N번쨰 수 (N+2) a b c ... (N + M + K + 1) a b c O // K개의 줄에 결과를 1000000007로 나눈 나머지를 출력 *a가 1일 때 b번째 수를 c로 바꿈 *a가 2일 때 b~c 곱 출력 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer..

(Briefing) (문제) (단 하나의 맥락) (입출력과 되어야 하는 그림) N개의 정수 배열 A번째 ~ B번째 중 가장 작은 정수 찾기 a~b 쌍이 M개 주어진다 I // N M (2) 1번째 값 ... (N+1) N번째 값 (N+2) 1번째 ab 쌍 ... (N+M+1) M번째 ab쌍 O // ab 사이 최솟값을 차례대로 출력 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { // box recognition static long[] tree; public static void main(S..

원리 방향 방법 N개의 배열값들 트리 최하부 리프단 오른쪽 절반에 몰아넣는다 A[2^k] ~ A[2^(k+1) -1] 0 ~ 2^(k-1) 구간인 위로 올라가면서 값을 저장, 요구하는 값을 편하게 load 가능 2N, 2N+1 > 부모인 N에 저장 자식 노드 2쌍이 부모 노드의 값에 영향을 미치는 구조 구간값 계산시 start가 왼쪽 리프쌍에 위치한다면, 부모 노드는 해당 자식 노드값을 포함되므로 선택하지 않는다 end index가 오른쪽 리프쌍에 위치한다면, 부모 노드는 자식 노드값을 포함하므로 선택하지 않는다 start / 2 == 1 > 선택 end / 2 == 0 > 선택 부모 노드로 이동하면서 선택한 것 누적 계산하기 start는 오른쪽 위 부모노드로 end는 왼쪽 위 부모노드로 start = ..

DIVERGENCE - RECOVERY BOX - PRINT 시행단에서 Operate 되면 divergence가 일어난다 - return값으로 그 중 Main pillar divergence를 측정 : - 먹지를 갖다대면 그 track이 드러난다(recovery) - return값으로 발산된 것을 count++; 혹은 answer[i] = number; 혹은 plate = plate + D[i] 등으로 저장 출력 : System.out.println(answer[i])

모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리 > 가중치가 작은 에지부터 에지가 N-1개가 될 때까지 연결하되(정렬 > union) > find로 대표 노드가 같으면(왼쪽 방향 회전(find로 찾아진 대표 노드)이 오른쪽 새 연결과 만날 때) 사이클이 생기므로 건너뛴다 - 사이클이 포함되지 않는다 - N개의 노드가 있을 때, 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1 개이다 - 에지 중심의 시행 ------------------------------------ 1 재료 edge list 형태로 저장 edge class에는 Node-start, Node-end, weight로 구성 union find 배열도 초기화 2 가중치 기준으로 오름차순 정렬 comparable()..

모든 노드 간 최단 경로 탐색 - 음수 w 있어도 수행가능 - Dynamic programming 이용 단 하나의 맥락 - A~B 사이의 최단 경로 위에 K노드가 존재한다면, K로 들어가고 나오는 경로 역시 최단 경로 - D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 1 D[S][E](Adjacency matrix) 선언 후 > S == E일 때 0 > 나머지 = INF 2 D[S][E] = W 저장 3 3중 for문의 형태로 반복 > 업데이트 for (k : 1~N) { for (S : 1~N) { for (E : 1~N) { D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]); } } }

2022.08.08 - [Track Phase-Turnovering/algorithm 100] - 059 : 타임머신으로 빨리 가기 출발 노드에서 다른 모드 노드까지 최단 경로 탐색 - 음수 w가 있어도 수행 가능 - 에지 중심 시행 - 전체 그래프에서 음수 사이클의 존재 여부 판단 가능 1 edge list graph and D[index] - ArrayList edges > s, e, w - D[1] = 0, D[2~N] = ∞ 2 모든 에지를 확인, 정답 배열 업데이트 - if (D[s] != ∞ && D[s] + w D[e] = D[s] + w - 음수 사이클이 없을 때, 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 수는 N-1 3 음수 사이클이 존재하는 지 확인 - 모든..

// union public static void union(int a, int b) { a = find(a); b = find(b); if (a != b) { label[b] = a; } } 인식과 작업의 대상 / 모듈이 인식할 수 있도록 하기 : int a, int b; 작업 공간 : while : queue, ArrayList 등 작업이 언제 시작되는지 끝날 때 : if (a != b) : External module을 실행 작업의 종류 : 값 변화 : 위상 변화 : default 작업

직관적으로 전체 파악을 하지 못할수도 있다 또한 피보나치를 계산하는 bottom-up 방식에서 "반복되는 cycle unit이 전체로 퍼져나감" + "단 하나의 초기 설정값, 혹은 마지막이나 중간에 파라미터가 고정되고, 양 방향으로 Underlying potential도 가지고 있지 않은 공간이 분명히 있다" 이 두가지를 찾는것이 우선