Search

 

001 (DFS)

public class Main {

    static ArrayList<Integer>[] F;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {

- 같은 클래스 안, 다른 모듈들에서 동시에 사용가능하게 변수 인식

- static으로 한다

 

 

002

public class Main {

    // recognizer + excess modifier
    static ArrayList<Integer>[] F;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int C = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        // Capacity
        F = new ArrayList[C+1];

        // initializer
        for (int i = 1; i <= C; i++) {
            F[i] = new ArrayList<>();
        }

        // value allocator
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            F[s].add(e);
            F[e].add(s);

        }

> DFS 시 에지-노드 그래프를 나타내기 위해 인접 리스트를 사용하며

> 에지 개수만큼 밸류 할당

> "인식 > 캐퍼시티 > 초기화 > 할당"

 

 

 

003

// Operating DFS + marker
int marker = 0;
for (int i = 1; i <= N; i++) {
    if (!visited[i]) {
        marker++;
        DFS(i);
    }
}

// External Module : DFS
static void DFS(int v) {
    
    // EP
    if (visited[v]) {
        return;
    }
    
    // Phaser
    visited[v] = true;
    for (int i : F[v]) {
        if (!visited[i]) {
            DFS(i);
        }
    }
}

DFS

• 1 : 일단 linear for문으로 모든 요소를 DFS 실행하나, if (!visited[i]) phaser를 추가하여 거른다
• 2 : DFS가 시작되면 if(visited[v) return phaser 로 우선 방문된 인자로 중복에 걸리는지 확인한다, 이것은 1번에서 시작되는 요소를 거르기 위한 게 아닌, 아래에서 실행되어 나오는 connected를 거르기 위한 것
• 3 : 해당 인자에 대해 phaser switch 켜준다
• 4 : connected node를 차례로 DFS 해주나, 방문되지 않을 때만 실행한다

Marker

• DFS에서 connected 횟수가 아닌, 연결 요소이므로 하나의 DFS가 모두 끝날때까지 1회, 즉 시작될 때 1번만 체크하면 된다

 

- 재귀에 걸리는 DFS 같은 경우는 외부에서 1, 내부에서 1 들어오는 양방향 phaser로 예외 처리를 한다

- 클래스 내 외부 모듈 사용 : static void, 그렇지만 recursive를 turn 하기 위해 return이 사용됨

- 재귀 부메랑이 다시 돌아올 때는 EP에 걸렸을 때

- F[v] 는 connected edge임

- boolean visited의 초깃값은 들어가지 않는다

 

 

004

static boolean isPrime(int num) {
    for (int i = 2; i <= num / 2; i++) {
        if (num % i == 0)
            return false;
    }
    return true;
}

> 소수 판별 함수

> 모든 자연수로 나눴을때 살아남는게 목적

> 1 ~ N/2 // N/2+1 ~ N // N+1 (1~4, 5~8, 9)

> 첫번째 파트로 안나눠지면, 두번째 파트로도 안나눠진다는 것은 동일하기에 i < num이 아닌 i <= num / 2 를 사용하여 선혈 공간 줄임 

 

 

 

 

006

static void DFS(int number, int digit) {

    // Quick Recovery PipeLine
    if (digit == N) {
        if (isPrime(number)) {
            System.out.println(number);
        }
        return;
    }

    for (int i = 1; i < 10; i++) {
        if (i % 2 == 0) {
            continue;
        }
        if (isPrime(number * 10 + i)) {
            DFS(number * 10 + i, digit++);
        }
    }
}

> if의 종류

• thesis Pipeline
• Quick Recovery Pipeline(checker 충족시)
• Exceptional Pipeline (phaser)

> 해당 if는 checker 2 + OEC로 구성

> QRP 후 재귀에서 return 잊지 말기

> 아래 DFS 진행은, 각 단계를 저장하는 게 아닌, 소수이기만 하면 다음 단계로 나아가 끝에 도달하는 기능만 해주면 된다

 

 

007

// Operating DFS
for (int i = 0; i < N; i++) {
    
    // action
    DFS(i, 1);
    
    // QRP
    if (arrived)
        break;

}

해당 QRP는 action 밑에 오는데,

> 처음은 무조건 depth가 1이라 안 되고

> for문의 다음 시행공간에 들어가기 전에 확인해서 break 해야 하기 때문이다

조건 충족시 바로 break되도록 할것

 

 

008

// OEC
if (arrived)
    System.out.println("1");
else
    System.out.println("0");

> int 아닌 string으로 출력

 

 

009

// External Moduel : DFS + checker
public static void DFS(int now, int depth) {

    // QRP
    if (depth == 5 || arrived) {
        arrived = true;
        return;
    }
    
    // action
    visited[now] = true;
    for (int i : F[now]) {
        if (!visited[i]) {
            DFS(i, depth++);
        }
    }
    
    // Handling Exception
    visited[now] = false;
}

Nonconserved :

• 문제의 특성상 완전 탐색하는 게 아님
• 한 노드에서 어디까지(4번 connected == depth:5) 갈 수 있는지 알아보기 위해
• 일반 DFS처럼 한 노드의 탐색 결과를 보존하지 말고, 다음 connected node가 될 수 있도록 false로 꼭 바꿔준다

 

D에서 순환하여 A로 가는 결과는 없는지?

• !visited로 거르기 때문에 없다

 

checker / phaser가 왜 2개나 필요한지?

• depth는 단일 노드의 결과를 반영한다
• arrived는 아직 탐색이 안된 다음 노드에서, 이미 전 노드가 depth에 도달한 적이 있으니 중복해서 탐색하지 말란 소리다
• 만약 문제가 각 노드별로 depth 5를 충족하는 것을 찾아내라고 하면 arrive는 없어져야 함
• visited phaser는 비보존, arrived checker는 보존

 

phaser 는 특수 공간에서 위상값( 존재 or 음으로 사라짐 ) or 방문하거나 방문되지 않음

 

 

010(BFS)

// PRe
for (int i = 1; i <= E; i++) {
    Collections.sort(Connected[i]);
}

> 낮은 노드부터 탐색하기 위해 오름차순 정렬, 까먹지 말기

> 어레이 소트가 아닌 컬렉션 소트에 주의

 

 

 

011

// Operating DFS
visited = new boolean[N+1];
DFS(S);
System.out.println();

// Operating BFS
visited = new boolean[N+1];
BFS(S);
System.out.println();

 

> 각 탐색 실행하기 전 visited[] 초기화 해주고

> 줄 바꿔주기

 

 

012

// EM  : BFS + OEC
private static void BFS(int Node) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(Node);
    visited[Node] = true;

    while (!queue.isEmpty()) {
        int now_Node = queue.poll();
        System.out.println("now_Node" + " ");
        for (int i : Connected[now_Node]) {
            if (!visited[i]) {
                visited[i] = true;
                queue.add(i);
            }
        }
    }
}

DFS

• 그대로 Node를 받아서 사용하지만 

BFS

• queue에 넣고, poll 될때 connected 탐색을 시작한다
• 이때 넣는것과 빠지는 노드가 다르므로(FIFO), add와 poll 둘다 phaser에 기록한다
• 탐색결과는 poll 후 하나만 하면 됨
• 추가 : poll 넣을 박스 준비할 것

 

 

013

//setup
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static boolean[][] visited;
static int[][] Connected;
static int xC, yC;

2차원 탐색에서의 setup은 x y 좌표로 사용하기 위해

 

 

 

014

for (int i = 0; i < xC; i++) {
    st = new StringTokenizer(br.readLine());
    String line = st.nextToken();
    for (int j = 0; j < yC; j++) {
        Connected[i][j] = Integer.parseInt(line.substring(j, j+1));
    }
}

> String으로 된(공백없는) 수열 쪼개서 matrix에 넣기

 

 

015

// EM : BFS
public static void BFS(int i, int j) {

    // Setup
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[] {i, j});
    visited[i][j] = true;
    
    // action
    while (!queue.isEmpty()) {
        int now[] = queue.poll();
        for (int k = 0; k < 4; k++) {
            int x = now[0] + dx[k];
            int y = now[1] + dy[k];
            if (x >= 0 && x < xC && y >= 0 && y <yC) {
                if (Connected[x][y] != 0 && !visited[x][y]) {
                    visited[x][y] = true;
                    Connected[x][y] = Connected[now[0]][now[1]] + 1;
                    queue.add(new int[] {x, y});
                }
            }
        }

    }
}

// 선언과 동시에 배열의 크기 지정 및 값 초기화
int[] arr = {1,2,3,4,5};
int[] arr = new int[]  {1,3,5,2,4};
int[] odds = {1,3,5,7,9};
String[] weeks = {"월","화","수","목","금","토","일"};

2차원에서 BFS 실행

> ArrayList는 필요없다

> new int[] {i, j} 가 무엇인지 알아낼 것

> x y는 좌표로 쓰이는 것

connected는 여기서 depth로 쓰임

 

-

 

016

class Edge {

    int e;
    int weight;

    public Edge(int e, int weight) {
        this.e = e;
        this.weight = weight;
    }
}

> ArrayList<Integer>(); 가 아닌

> 가중치(거리) 정보 있는 Edge 로 사용하기 위해

 

-

 

017

// L2~
Connected = new ArrayList<Integer>();
for (int i = 1; i <= N; i++) {
    Connected[i] = new ArrayList<>();
}
for (int i = 0; i < N; i++) {
    int s = sc.nextInt();
    while (true) {
        // delivery box
        int e = sc.nextInt();
        if (e == -1)
            break;
        int w = sc.nextInt();
        Connected[s].add(new Edge(e, w));


    }
}

더 자각하지 않아도 되는 것

• delivery box는 전달되기만 하면 더 이상 신경쓰지 않아도 됨

왜 if(-1) 이 중간에 들어가 있지?

• 일단 자각할 박스가 필요하니, int e 로 인풋을 받아봐야 판단 가능한 것
• 받았다 해도, Field에 저장되지 않으니 괜찮다

Edge class를 만들어 사용할 때

• 앞에 꼭 new를 붙인다

 

-

 

 

018

// EM : BFS
private static void BFS(int Node) {

    // Setup
    Queue<Integer> queue = new LinkedList<>();
    queue.add(Node);
    visited[Node] = true;

    // action
    while (!queue.isEmpty()) {
        int now_node = queue.poll();
        for (Edge i : Connected[now_node]) {
            int e = i.e;
            int w = i.weight;
            if (!visited[e]) {
                visited[e] = true;
                queue.add(e);
                distance[e] = distance[now_node] + w;
            }
        }
    }
}

 

 

Edge class를 사용할 때

• int i 가 아닌 Edge i임
• int e = i.e; int w = i.weight;로 값을 로드해야 사용가능
• 마지막 visited에 i를 넣어주는 게 아닌, e를 넣어줘야 함
• distance를 제외하곤 나머지 그대로 e 사용하면 됨

> 기본 distance 값은 0으로 설정되어 있나?

 

-

 

019

// Operation BFS + distance
phaser = new boolean[N+1];
distance = new int[N+1];
BFS(1);


// Max flip
int Max = 1;
for (int i = 2; i <= N; i++) {
    if (distance[Max] < distance[i]) {
        Max = i;
    }
}


// Operation BFS + distance
phaser = new boolean[N+1];
distance = new int[N+1];
BFS(Max);


// OEC
Arrays.sort(distance);
System.out.println(distance[N]);

- max flip시, 맨 첫번째 값을 정하고, 두번째부터 for문을 돌린다

> 새로 BFS 할 때, 거리랑 방문 리셋 잊지 말것

> 마지막에서 for문을 굴리면서 max를 찾기보다, 그냥 오름차순 정렬 후 맨 오른쪽 값이 max다

 

-

 

020(Binary Search)

// L4~
for (int i = 0; i < tC; i++) {

    // setup
    int s = 0;
    int e = C-1;
    int target = sc.nextInt();
    boolean checked = false;

    // binary search
    while (s <= e) {
        int m = (s + e) / 2;
        if (F[m] > target) {
            e = m - 1;
        } else if (F[m] < target) {
            s = m + 1;
        } else {
            checked = true;
            break;
        }
    }

    // OEC
    if (checked)
        System.out.println(1);
    else
        System.out.println(0);
}

> target은 value이고, m은 cursor이므로 F[m]과 target을 비교해야 함에 주의

 

 

-

 

021

// L2 + setup
int[] F = new int[C];
int s = 0;
int e = 0;
for (int i = 0; i < C; i++) {
    F[i] = sc.nextInt();
    if (s < F[i])
        s = F[i];
    e += F[i];
}

> cursor가 아닌, 블루레이 용량을 탐색해야 하므로 최솟값인 9와 모든 레슨크기를(1~9) 더한 45 사이에서 탐색한다

 

-

 

 

022

int m = (s + e) / 2;
int plate = 0;
int marker = 0;

for (int i = 0; i < C; i++) {

    if (plate + F[i] > m) {
        marker++;
        plate = 0;
    }

    plate += F[i];

}

- plate는 F[i]의 범위들을 오름차순으로 묶는 것인데,

- 가령 1에서 6까지 27이라는 Plate에 담겼지만, 7으로 넘어갈 때 1에서 7까지는 plate 초과라 해당 plate는 리셋

- 7부터는 새 plate에 담기 시작한다

 

-

 

023

if (plate != 0)
    marker++;

if (marker > M) {
    s = m + 1;
} else {
    e = m - 1;
}

// OEC
System.out.println(s);

- 그리고 해당 배열의 끝 인자가 용량을 초과해서 하나가 더 담겼으면 plate 갯수를 하나 더 늘려주고

- 만약 접시 갯수가 주어진 것보다 초과이면, 용량을 m보다 큰데서 찾고

- 적거나 같으면 m보다 작은데서 찾는다

- 그리고 출력되는 것은 s 인덱스 

- 접시 갯수는 3개만 써야 하고, 그 와중의 용량의 최솟값이니 s <= e 때까지 진행되다가, s가 e보다 커지는 순간(최솟값) 출력

 

-

 

 

024

기본 논지

- 작은 수의 갯수가 k-1개인 중앙값이 정답

- 2차원 배열에서 N행이 N의 배수로 구성되어 있으므로, 2차원 배열에서의 k번째 수는 k를 넘지 않는다

- 따라서 2차원 배열의 1~k번쨰 안에 정답이 있다 > 시작 Index = 1, end index = k

 

 

-

 

024

for (int i = 1; i <= C; i++) {
    marker += Math.min(m / i, C);
}

작은 값을 비교하며 카운터

 

 

-

 

 

025

//setup
long s = 1;
long e = K;
long ans = 0;

// binary search
while (s <= e) {

    long m = (s + e) / 2;
    long marker = 0;

    for (int i = 1; i <= C; i++) {
        marker += Math.min(m / i, C);
    }
    
    if (marker < K) {
        s = m + 1;
    } else {
        ans = m;
        e = m - 1;
    }
}

// OEC
System.out.println(ans);