개발블로그by페페

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도 가지고 있지 않은 공간이 분명히 있다" 이 두가지를 찾는것이 우선

gg

private private가 붙은 변수, 메소드, 클래스는 해당 클래스에서만 접근 가능 default 접근 제어자가 없는 변수, 메소드, 클래스는 default 접근 제어자가 되어 해당 package 내에서만 접근 가능 protected protected가 붙은 변수, 메소드, 클래스는 - 동일 패키지의 class - 해당 class 를 상속 받은 다른 패키지의 class에서만 접근 가능 public public이 붙은 변수, 메소드, 클래스는 어떤 클래스에서도 접근이 가능하다 // 접근제어자를 모두 public으로 단순하게 open할수 있지만, 접근 제어자를 잘 이용하면 코딩 실수 및 중복 등의 위험요소를 제거 가능하다

출발 노드와 모든 노드 간의 "최단 거리" 탐색 - weight가 있을 때 - 에지는 모두 양수일 때 0 Adjacency matrix로 구현해도 좋지만, 시간 복잡도 및 N의 크기에 대비해 Adjacency graph로 구현한다 1 최단 거리 배열 D[N]을 만들고 - 출발 노드 0 - 나머지 노드는 Integer.MAX_VALUE로 할당 2 cycle unit - D[N]에서 가장 값이 작은 노드를 고른다(출발 노드에서 시작) - 해당 노드와 연결된 노드에 에지의 가중치를 업데이트 - Min(D[selected] + edge weight, D[connected]) 3 kaiten space - 모든 노드가 선택될 때까지 반복 - boolean[] visited를 만들어 중복 처리 - 출력

- 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 - 우선 순위와 관련 - ArrayList[N]을 사용 1 : 진입 차수(in-degree) - indegree D[N]을 만든다 - 인접 리스트에서 노드와 edge 값이 할당되면, 에지인 D[i] 값을 올려준다(D[i]++;) 2 : cycle unit 진입 차수가 0인 노드를 Queue에 저장한다 해당 노드와 연결된 edge의 D[i]를 1씩 감소시킨다(D[i]--;) 3 : 다음 노드인 2를 선택 모든 노드가 정렬될 때까지 반복 4 : 정렬 결과를 출력