개발블로그by페페

하나의 DFS 세션에서 끝이나지 않는다면, (더 방문할 노드가 남아있다면) 해당 노드를 포함한 연결체와 떨어져있는 다른 연결체 방문이 필요하다 해당 EP가 왜 필요한가? import java.util.ArrayList; import java.util.Scanner; public class Main { static ArrayList[] TP; static boolean[] visited; public static void main(String[] args) { // ISC Scanner sc = new Scanner(System.in); int V = sc.nextInt(); int E = sc.nextInt(); // D2F TP = new ArrayList[V+1]; for (int i = 1; i

오른쪽에서 조여오는 squeezer를 두는데, 우선 1~V를 다 돌아야 하므로, sq는 0부터 시작한다 그리고 일반 tp는 전체에서 sq만큼 뺀 경계선 느낌으로 할당하면 된다 모든 노드들이 한번에 정렬되지는 않지만, 제일 큰 노드는 있어야 할 곳으로 배치된다 (오른쪽으로 보낼만 하면 보내고 / 그것보다 더 큰게 있으면 가만히 놔둔다) 가만히 놔두면서 새로운 큰 것이 나타나면, 그것을 오른쪽으로 보낸다 import java.util.Scanner; public class Main { public static void main(String[] args) { // ISc Scanner sc = new Scanner(System.in); int V = sc.nextInt(); // D2F int[] TP = n..

0번 노드부터 V-1번 노드까지 모두 IS로 보낸다 하나라도 체크인되면 나머지는 필요없다. 모든 쌍을 구하는 게 아닌, 존재하느냐의 문제이므로 for / while에서 break = DFS와 같은 method에서 return pointer와 depth를 사용하여, recursive 시 depth를 보충해 줄 수 있다 (pipeline patch) depth == 5 로 끝내지는 게 아닌 "depth > checkin > break;" signalling 하는 이유는 depth는 DFS안에서 계속 변화하기 때문에 순간을 catch하기 어렵고, 하나의 DFS시작점이 끝나야 for linear 공간은 중 하나가 끝나기 때문이다 비보존 patch - BFS라면 이렇게 해서는 안되지만, DFS 끝에 patch가 ..

가중치를 사용하기 위해 Edge Class를 구현했더라도(ArrayList[] TP) 와 달리 BFS에서는 Edge를 가져와 pointer로만 탐색 사용, Patch로 value를 사용해도 된다(반은 넣고 반은 사용) * 하나의 BFS시작에서 먼 노드, 그리고 그 노드에서 반대 방향으로 먼 노드 2개만 판단하므로, 중복해서 업데이트 할 필요가 없다 (D patch시 if 조건 X) 불순물은 if pipeLine으로 따로 빼 둬서 만약 -1이 있다면 자동으로 해당 위상 공간으로 흘러갈 것이다. 그러므로 나머지 정제된 것은 원래대로 바로 값들을 TP로 넣어주면 된다 (단방향 작업) BFS는 Print작업이 아닌, D만 건드려서 업데이트한다 BFS(시작) + 먼곳의 pointer BFS(먼곳) + 다음 먼곳 ..

오른쪽으로 쌓고, 왼쪽으로 잘라낸다 3가지 작업 (인식자 = 넣을거) - 넣기 - 넣을 때 L을 벗어나는 것 제거(4-3 = 1) - 넣는것보다 큰것은 미리 제거하고 넣음 *접근 : field > pointer(deque.getFirst()); *connector를 사용 / 별도 class Node 사용 *for i 의 connector 외에 별도 기수 할당이 필요하면 Node를 사용(특히 비교) import java.io.*; import java.util.Deque; import java.util.LinkedList; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOE..

value가 아닌 pointer를 stack에 넣고 필요하면 connector를 사용하는 방식 비교 후 OEC를 작성해야 해서 현재 stack[]과 TP[] 비교 그리고 둘 다 pointer를 사용하여 connector인 TP 필요 지금 pointer는 stack에 들어있는 것으로(0~) 비교 대상 pointer는 i로(1~) 지금값과 오른쪽의 값을 사용해야 하므로 0을 SP로 넣고 (다른 TP의) 1과 비교 시작 stack.pop()과 OEC 작성 2가지 작업이 동시에 일어난다(한줄에) System.out.print랑 똑같이 작용

- Queue 공간 생성하기 - while : (while 내부 공간에서) 바깥에 도달할 때까지 - 입출력 > queue공간 및 값까지 완성 되었으면 > 바로 시행 공간으로 넘어간다 PriorityQueue를 많이 사용해서 헷갈릴 수 있지만 원래 Queue는 넣었던 순서대로 정렬된다

S[0]을 먼저 TP[0]으로 넣어두고 1부터 시작해도 됨 0부터 1 0부터 2 ... 0부터 V-1까지 구간만 우선 생각한다 또한 나머지가 있다면 나머지가 같은 것으로 bundling한다 *나머지가 0일때도 더해줘야함 나머지는 T와 다르다. 1 ~ T-1 구간에 존재 동일한 나머지 bundling이 있다면 조합으로(큰오른쪽, 작은오른쪽 자동으로 순서가 정해지므로) 수를 counter에 더한다 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 T = sc.nextInt(); /..

> 2차원 행렬에 3차원 블럭(음양 / 값의 존재 여부) 만들기 일반 TP[](A[])와 합 S[]의 capacity는 같다 - 1부터 ~ 5까지 - 1까지 합 ~ 5까지의 합 두번 더하고 난 뒤 - 마이너스 보정 + 해당 포인트 박아넣기 전체에서 - 직전들을 두번 빼고 + 플러스 보정 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { // ISC BufferedReader br = new..

0은 필요없지만 0이 있어야 1부터 서술 가능 s와 e를 받아서 s-1까지 빼버린다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { // ISC BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); // D2F..