개발블로그by페페

size는 총 2번을 커버해야 한다 - bottomline의 수들과 - 그 수들의 합을 계산할 수 있는 slot들 "1에서 다시 2배씩 현재 수까지 도달하는 로직" > 현재 수가 1이 될때까지 exp /= 2; 하는동안 counter(exponent)를 1씩 올린다면, 총 2회가 나옴 > 그런데 5~7 사이의 수라면 감가된것이 있으므로 exp + 1; > bottom에서 위로 올라가면서 계산하는 slot을 위해 다시 (exp+1) + 1 5는 사실 8에 귀속되어야 하지만, 몫을 나눠서 height를 구하는 방식은 4에 귀속 됨 즉 4까지 8을 사용하는 것 2^3은 8, 그리고 bottom 한줄은 나머지 층수의 모든 노드 수와 동일함 기수와 서수 차이 15부터 역순으로 1까지 그러나 3과 2로 계산되어 1..

DFS같은 recursive에서 - plate를 바로 return하거나 - print하기 어렵다 > 그래서 plate를 waterfalling variable로 만들어 main에서 print한다 부모 > 자식노드로 진입하기만 한다면 leaf가 생기는 것이고, 특정 노드(우선은 부모 노드로 간주)에서 자식으로 진입되는 게 아무것도 없다면(여기서는 deleteTarget 포함) plate 추가 부모-자식 쌍으로 유입하되 root는 별도 관리 root와 deleteTarget Lock 별도 관리 import java.util.ArrayList; import java.util.Scanner; public class Main { static ArrayList[] TP; static boolean[] visited..

BFS 흐름에 parent 리시버 Pair만 해주면 된다 DFS로 가능한 것도 참고할 것 import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static ArrayList[] TP; static int[] parent; static boolean[] visited; public static void main(String[] args) { // ISC Scanner sc = new Scanner(System.in); int V = sc.nextInt(); // D2F TP = new ArrayList[V+1]; for (int i =..

순회 자체는 간단하다 현재 node Print / L recursive / R recursive 순서만 정해준 후 프로그램에게 '지금 - 다음' Unit의 반복으로 while line을 돌도록 시키는 것 *내가 하는 게 아님 문제는 인자의 공급과 어떤 TP를 사용할 것인가인데, binary tree 순회에서는 node 정보로 양 자식노드에 접근가능한 int[26][2] 사용 숫자 + 'A' = char String > char 도 가능 괄호로 묶어줘야 함 (char) (node + 'A') import java.util.ArrayList; import java.util.Scanner; public class Main { static int[][] TP; public static void main(Stri..

depth 정보와 parent 정보 필요 > TP 정보 및 BFS로 공급해줄것 일반 BFS 흐름에 patch 부착 (pairing) - depth - parent parent는 connected와 now 관계로 바로 공급 가능 다만 root는 0으로 depth를 잡고 root아닌, root와 연결된 바로 다음 노드부터 depth정보를 공급하므로, sP - 지금 root(depth가 0인 노드갯수) 1 충족 - 다음 node의 depth = 1 depth가 1인 과거 노드갯수 queue.size() 충족 > 즉 queue.poll()로 다 빠져나갔을 때 > 다음 depth는 카운터를 올린다

단순 에지 순회만 하는 bellman-ford는 - queue 대신 Edge[] 를 사용 - Edge(s, e, w) class 공급하나 Comparable 넣지않음 MSP는 - PQ 사용 - Edge class(s, e, w) 공급 및 w 기반 Comaparble 역시 사용 Topology Sort는 - ArrayList로 []접근하지 않고 V만큼 ArrayList() 초기화 공급 - get으로 access DFS, BFS는 - ArrayList[] 로 양방향 노드 더하기 Dijkstra는 - ArrayList[]로 특정 노드에 연결된 '다음 노드 + distance' TP 정보를 공급 - 최단거리부터 갱신해야하므로 w 기반 PQ도 필요하다 - sP 필요 sP 작업 필요 에지가 여러개 있을 수 있으므로..

우선순위는 필요없으나 에지중심 작업이므로 s와 e, 그리고 사이인 w를 사용할 Edge class 필요 MSP처럼 최소거리부터 연결하기 위해 정렬시킬 필요가 있을 때에는 PQ에 에지를 (모두)넣고 (BFS없이)빼야 하지만 순서없이 단순히 모든 에지를 순회시켜 check-in으로 충분한 경우에는 Edge를 기반으로 하는 List만 만들고 넣어준다 receiver 필요 1이 sP이므로 0 설정 첫번째 for문은 단순반복이므로 while으로 대체하는게 편할수도 있다 모든 에지를 순회하되, 시작부터 INF 되는것은 거른다 크다 > 작다 에서 큰것 = 작은것 으로 할당 surviving boolean으로 return이 아닐 때에는 cont가 필요하다 더 작은 거리가 발생만 하면 변경작업 없이 바로 boolean으..

에지 거리 값을 넣기 전에, 에지가 없을 수도 있으므로 초기화를 해준다 - 모든 노드와 노드 사이를 출력해야 하므로 import java.util.Scanner; public class Main { public static void main(String[] args) { // ISC Scanner sc = new Scanner(System.in); int V = sc.nextInt(); int E = sc.nextInt(); // TP int[][] TP = new int[V+1][V+1]; for (int i = 1; i

작은것부터 연결해야 하기 때문에 - 54321 정배열 PriorityQueue - 배열의 기준을 잡으려고(w) compareTo 필요 * 인식자에서 queue에 바로 넣어버리므로 별도 TP list는 필요하지 않음 (넣자마자 자동 정렬됨) union은 이미 check-in 되었다는 phaser로 사용됨 노드가 3개라면 모두 연결된 에지는 2(V-1)개이다 그래서 while공간이 1 > 2를 모두 순회하고 3은 진입하지 않는다 import java.util.PriorityQueue; import java.util.Scanner; public class Main { static int[] parent; public static void main(String[] args) { // ISC Scanner sc ..

ArrayList - capacity를 별도로 정하지 않고 - 1~V번 new ArrayList()를 add한다 []처럼 순차 pointer(i)가 없으므로, get(s)를 사용하여 access 그리고 add를 더함 또 순서가 있으므로 배열과 달리 단방향만 더해주면 된다 TP와 별도로 Field인 Queue가 필요 * 에지 가중치가 아닌, 에지 양 끝 노드의 순서이고 순서 정보는 indegree로 공급받으므로 pQ는 필요없다 *통상 OP시 개설해도 되지만, indegree가 0인것을 먼저 넣고 시작해야 하므로(sP) 미리 개설 후 sP 유입까지 끝내둔다 indegree가 0인 (동일 위상 내) 무더기 작업이 끝나고 다음 작업이 필요하므로 BFS를 사용한다(DFS와 대조하여) sP는 위에서 작업했으므로, ..