다메카솔

🔍문제

https://www.acmicpc.net/problem/1253
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.

🤔발상

두 수의 합을 구하는 문제는 정렬된 배열일 경우, 양 끝에 포인터 지정하고, 포인터를 움직이면서 원하는 값보다 큰지 작은지를 판단하면서 포인터를 이동하는 투 포인터 알고리즘으로 해결할 수 있습니다.

🔦입출력

N의 수는 2천개이며, N의 값은 10억이므로 두 수의 합은 INT 범위 이내고 투포인터로 탐색할 때 오래걸리지 않는 수입니다. O(N)

📃의사코드

    1. 숫자들을 오름차순으로 정렬한다.
    2. 각 수마다 투포인터로 해당 수를 만들 수 있는지 확인
    3. 만들 수 있다면 카운트를 증가시킨다.

👨‍💻코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int n = Integer.parseInt(br.readLine());
            int[] arr = new int[n];
            Arrays.sort(arr);

            String[] sarr = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(sarr[i]);
            }


            int count = 0;
            for (int i = 0; i < n; i++) {
                int start = 0;
                int end = n - 1;
                while (start < end) {
                    if (start == i) {
                        start++;
                        continue;
                    }
                    if (end == i) {
                        end--;
                        continue;
                    }
                    int sum = arr[start] + arr[end];
                    if (sum == arr[i]) {
                        count++;
                        break;
                    } else if (sum < arr[i]) {
                        start++;
                    } else {
                        end--;
                    }
                }
            }
            System.out.println(count);
        }
    }
}

🚀TIL

• - 투포인터 알고리즘을 알고있다면 쉽게 해결할 수 있는 문제입니다.
• 삼중 포인터 문제도 예전에 리트코드에서 풀어본 기억이 있는데, 재귀형식으로 포인터 하나를 고정한 뒤에, 다시 자신을 호출하여 2가지 변수를 선택하는 알고리즘이었습니다. 복습을 해두면 좋을 것 같습니다.

🔍문제

https://www.acmicpc.net/problem/4485
젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. \[0]\[0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.

하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 \[N-1]\[N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

🤔발상

0,0에서 n-1,n-1까지  최단거리를 탐색하는 문제입니다.
한 지점에서 다른 지점까지의 최단거리에서 다익스트라 알고리즘을 사용할 수 있을 것 같습니다.
또한 좌표 이동 시 1칸씩 이동 가능하다는 점에서 bfs탐색에 적합할 것으로 보입니다.

🔦입출력

동굴의 크기는 2~125이며 루피는 0~9 범위입니다.

📃의사코드

- 데이터 입력받기
- bfs탐색
- 결과 출력

👨‍💻코드

import java.util.*;
import java.lang.*;
import java.io.*;

/*
입력
동굴의 크기 정수 Number(2~125)
N줄 - 도둑 루피의 크기(0~9)
출력
가장 작은 최소 금액(최단 거리)
설계
2차원 배열을 0,0에서 n-1,n-1까지 최단 거리로 갈 때의 비용을 측정
상하좌우 1칸 이동 가능
dfs 탐색으로 누적 거리를 파라미터로 넘기며, 종료 지점의 값을 반환해서 최소값 찾기
*/

// The main method must be in a class named "Main".
public class Main {
    public static void main(String[] args) throws IOException{
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            StringBuilder sb = new StringBuilder();
            String problem = "Problem";

            int n = Integer.parseInt(br.readLine());
            int tc = 0;
            while (n != 0) {
                tc++;
                Map map = new Map(n);
                map.init(br);
                sb.append(problem).append(" ").append(tc).append(": ").append(map.getResult()).append("\n");
                n = Integer.parseInt(br.readLine());
            }
            bw.write(sb.toString());
        }
    }
}

class Map {

    private int[][] map;
    private int minResult;
    private int[][] dirs = {{0, 1}, {1, 0},{0, -1}, {-1, 0}};

    Map(int n) {
        map = new int[n][n];
    }

    public void init(BufferedReader br) throws IOException {
        int n = map.length;
        minResult = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
    }

    public int getStart(){
        return map[0][0];
    }

    public void dfs(int x, int y, int sum, boolean[][] visited) {
        visited[y][x] = true;
        int n = map.length;
        if (x == n - 1 && y == n - 1) {
            minResult = Math.min(minResult, sum);
            visited[y][x] = false;
            return;
        }
        for (int[] dir : dirs) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
                continue;
            }
            if (!visited[ny][nx]) {
                dfs(nx, ny, sum + map[ny][nx], visited);
            }
        }
        visited[y][x] = false;
    }

    public int getResult() {
        return bfs();
    }
    private int bfs() {
        int n = map.length;
        int[][] minCost = new int[n][n];
        for (int[] row : minCost) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        minCost[0][0] = map[0][0];
        Queue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(0, 0, map[0][0]));

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            int x = current.x;
            int y = current.y;
            int cost = current.cost;

            if (x == n - 1 && y == n - 1) {
                return cost;
            }

            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                    int newCost = cost + map[ny][nx];
                    if (newCost < minCost[ny][nx]) {
                        minCost[ny][nx] = newCost;
                        queue.offer(new Node(nx, ny, newCost));
                    }
                }
            }
        }
        return -1;
    }
}

class Node implements Comparable<Node> {
    int x, y, cost;

    Node(int x, int y, int cost) {
        this.x = x;
        this.y = y;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node other) {
        return this.cost - other.cost;
    }
}

🔍문제

https://www.acmicpc.net/problem/2458

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

1번 학생의 키 < 5번 학생의 키
3번 학생의 키 < 4번 학생의 키
5번 학생의 키 < 4번 학생의 키
4번 학생의 키 < 2번 학생의 키
4번 학생의 키 < 6번 학생의 키
5번 학생의 키 < 2번 학생의 키
이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.



1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

🤔발상

자신의 키가 몇 번째인지 알 수 있는 학생이 누군지 고민을 했습니다.
문제에서 이미지로 주어진 그래프를 관찰하다보니, 한 학생이 다른 학생과 모든 학생과 직,간접적으로 연결 관계가 존재하면 자신의 키가 몇 번째 인지 알 수 있다고 보았고, 플로이드 워셜 알고리즘을 이용하여 연결 관계를 파악하고, 이 숫자를 세어 전체 인원수와 비교하면 될 것으로 보았습니다.

🔦입출력

다행이 학생 수가 500 이하로, 만약 10,000등 수가 많았으면 다른 그래프 탐색방법을 고민해보았어야 할 것 같은데 플로이드 워셜을 사용할 수 있을 것 같습니다.

📃의사코드

- 데이터 입력받기
- 플로이드 워셜 이용하여 연결관계 업데이트
- 각 학생의 연결된 인원 수 세기
- 모든 학생과 연결된 학생의 수 세기

👨‍💻코드

import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) throws IOException{
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            String[] nm = br.readLine().split(" ");
            int n = Integer.parseInt(nm[0]);
            int m = Integer.parseInt(nm[1]);
            HeightUtil heightUtil = new HeightUtil(n, m);
            heightUtil.init(br);
            bw.write(String.valueOf(heightUtil.getResult()));
        }
    }
}

class HeightUtil {

    boolean[][] graph;
    int[] dist;
    int n;
    int m;

    public HeightUtil(int n, int m) {
        this.n = n;
        this.m = m;
        graph = new boolean[n + 1][n + 1];
        dist = new int[n + 1];
    }

    public void setGraph(int a, int b) {
        graph[a][b] = true;
    }

    public void floydWarshall() {
        for (int k = 1; k <= n; ++k) {
            for (int j = 1; j <= n; ++j) {
                for (int i = 1; i <= n; ++i) {
                    if (graph[i][k] && graph[k][j]) {
                        graph[i][j] = true;
                    }
                }
            }
        }
    }

    public void setDist() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] || graph[j][i]) {
                    dist[i]++;
                }
            }
        }
    }

    public int getResult() {
        int result = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == n - 1) {
                result++;
            }
        }
        return result;
    }

    public void init(BufferedReader br) throws IOException {
        for (int i = 0; i < m; i++) {
            String[] ab = br.readLine().split(" ");
            int a = Integer.parseInt(ab[0]);
            int b = Integer.parseInt(ab[1]);
            setGraph(a, b);
        }
        floydWarshall();
        setDist();
    }
}

🚀TIL

• 다른 탐색 방법도 한번 고민해보고 구현해보면 좋을 것 같습니다.

🔍문제

https://www.acmicpc.net/problem/2457
오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 
N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

🤔발상

꽃들을 시작 날짜와 종료 날짜로 정렬한 뒤에, 앞에서부터 조건에 맞는지 검사하면서 가장 종료 날짜가 긴 꽃을 선택하면 될 것 같았습니다.
주 키워드는 정렬과 그리디 알고리즘으로 보입니다.

🔦입출력

입력
꽃들의 총 개수 N(1~100,000)
꽃이 피는 날짜와 지는 날짜 x N
출력:  
선택한 꽃들의 최소 개수

📃의사코드

- 입력받은 꽃들을 정렬 가능한 클래스로 생성하여 배열에 담기
- 배열 정렬
- 시작날짜, 종료날짜 기준점 생성
- 시작날짜가 종료날짜 이전 동안 반복
	- 꽃들 배열 탐색
		- 탐색 대상의 시작날짜가 현재 시작날짜보다 늦으면 안됨
		- 탐색 대상의 종료날짜가 현재까지 찾은 마지막 날짜보다 뒤라면
			- 마지막날짜 업데이트
			- 인덱스 업데이트
			- 찾음 플래그 on

👨‍💻코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.time.LocalDate;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

public static void main(String args[]) throws NumberFormatException, IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int n = Integer.parseInt(br.readLine());
            Flower[] flowers = new Flower[n];
            for (int i = 0; i < n; i++) {
                flowers[i] = new Flower(br.readLine());
            }
            Arrays.sort(flowers);
            final int BASE_YEAR = 2023;
            LocalDate start = LocalDate.of(BASE_YEAR, 3, 1);
            LocalDate end = LocalDate.of(BASE_YEAR, 12, 1);

            int count = 0;
            int idx = 0;
            LocalDate maxEnd = start;

            //1. [x]시작날짜, 종료날짜 비교
            //2. [x]선택한 값이 종료날짜 이전인 동안 반복
            //3. [x]탐색 대상의 시작일이 이전 꽃의 이전 꽃의 종료일보다 이후이면 선택 안함
            //4. [x]탐색 대상의 기간이 이전 최대값보다 크면 선택
            while (start.isBefore(end)) {
                boolean find = false;
                for (int i = idx; i < n; i++) {
                    if (flowers[i].getStart().isAfter(start)) {
                        break;
                    }
                    if (flowers[i].getEnd().isAfter(maxEnd)) {
                        maxEnd = flowers[i].getEnd();
                        idx = i;
                        find = true;
                    }
                }
                if (!find) {
                    count = 0;
                    break;
                }
                start = flowers[idx].getEnd();
                count++;
                idx++;
            }

            bw.write(String.valueOf(count));
        }
    }

}

class Flower implements Comparable<Flower> {

    private final LocalDate start;
    private final LocalDate end;

    Flower(String str) {
        StringTokenizer st = new StringTokenizer(str);
        start = LocalDate.of(2023, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        end = LocalDate.of(2023, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }

    public LocalDate getStart() {
        return start;
    }

    public LocalDate getEnd() {
        return end;
    }


    //equals, hashCode, toString 생략
    @Override
    public int compareTo(Flower o) {
        if (this.start.equals(o.start)) {
            return o.end.compareTo(this.end);
        }
        return this.start.compareTo(o.start);
    }
}

🚀TIL

• 처음엔 LocalDate를 좀 더 활용하고 싶어 CronoUtil.DAYS.between(start,end)로 period를 구해서 최적해를 찾아보려 했는데, 시작 날짜에 따라 문제의 최적해가 꽃의 period만으로 판단할 수 없어서 수정하였습니다.
• 날짜를 다루는 알고리즘 문제가 꽤 자주 나오는데, 시간내서 java.time 복습을 해야겠습니다.
  
  

🔍문제

오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.

깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.

🤔발상

간단한 dfs 구현 문제인데, 여러 개념들을 복습할 수 있을 것 같아 연습 겸 풀어보았습니다.
1. 그래프 탐색을 위한 그래프 자료구조 구현
2. bfs, dfs 탐색 구현
1. bfs 탐색에는 queue를 사용
3. 방문 순서는 클래스 레벨에서 전역변수로 관리, 노드번호를 인덱스로 배열에 저장해서 출력

🔦입출력

정점의 최대 수가 100,000입니다. 메모리 제한이 512mb이며 dfs는 재귀호출로 함수 내의 지역변수가 메모리에 저장됩니다. 불필요한 변수선언을 하지 않도록 주의합니다.

📃의사코드

- 데이터 입력
- dfs 탐색
- 연결노드 탐색 시, 정렬순서로 탐색
- 방문 순서를 저장
- 결과 출력

# 👨‍💻코드

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            Graph graph = new Graph(n, m, start);
            graph.init(br);
            graph.dfs(start, new boolean[n + 1]);
            bw.write(graph.getResult());
        }
    }
}

class Graph {

    List<List<Integer>> graph;
    int start;
    int nodeCount;
    int edgeCount;
    boolean[] visited[];
    int[] visitOrder;
    int visitIndex;

    Graph(int v, int e, int s) {
        nodeCount = v;
        graph = new ArrayList<>();
        for (int i = 0; i <= v; i++) {
            graph.add(new ArrayList<>());
        }
        visitOrder = new int[v + 1];
        this.edgeCount = e;
        this.start = s;
    }

    public void init(BufferedReader br) throws IOException {
        for (int i = 0; i < edgeCount; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            graph.get(src).add(dest);
            graph.get(dest).add(src);
        }
    }

    public void dfs(int node, boolean[] visited) {
        visited[node] = true;
        visitOrder[node] = ++visitIndex;
        List<Integer> integers = graph.get(node);
        integers.sort(Integer::compareTo);
        for (Integer nextNode : integers) {
            if (visited[nextNode]) {
                continue;
            }
            visited[nextNode] = true;
            dfs(nextNode, visited);
        }
    }

    public void bfs(int node) {
        boolean[] visited = new boolean[nodeCount];
        Queue queue = new LinkedList<Integer>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Integer cur = (Integer) queue.poll();
            visited[cur] = true;
            for (Integer nextNode : graph.get(cur)) {
                if (visited[nextNode]) {
                    continue;
                }
                visited[nextNode] = true;
                queue.offer(nextNode);
            }
        }
    }

    public String getResult() {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < visitOrder.length; i++) {
            sb.append(visitOrder[i]).append("\n");
        }
        return sb.toString();
    }
}

🚀TIL

• 하나의 자료구조도 문제의 요구사항에 맞춰 적합한 구현형태가 다르다보니 하나의 풀이만 존재하지 않는 것 같습니다.
• 자주 사용하지 않으면 잊어버리므로 자주 복습하도록 노력해야겠습니다.

🔍문제

https://www.acmicpc.net/problem/1865

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

🤔발상

주어진 데이터는 노드와 간선이 주어지는 그래프 형태의 데이터이며 음의 가중치가 존재합니다.
그 중에 사이클이 존재하는지 검사하는 알고리즘으로 벨만포드 알고리즘으로 풀기에 적합한 문제라 판단하였습니다.
최단거리를 찾는 방법 중 자주 쓰이는 알고리즘 3개 중 하나이며 각각의 특징은 다음과 같습니다.

• 다익스트라
  • 한 노드 사이의 최단거리를 계산
  • DP를 이용하여 빠름
  • 음의 가중치가 존재하면 사용 불가능
• 플로이드 워셜
  • 모든 노드 사이의 최단거리를 계산
  • O(N ^ 3) 시간복잡도로 느림
  • 음의 가중치가 존재해도 사용 가능
• 벨만포드
  • 모든 노드 사이의 최단거리를 계산
  • 음의 가중치가 존재해도 사용 가능
  • 음수 사이클을 감지 가능함

🔦입출력

음의 가중치가 주어진 간선은 입력 순서로 구분되며, 입력값을 전처리해주어야 합니다.

📃의사코드

- 데이터 입력
- 입력시 음의 가중치 별도 처리
- 벨만포드 알고리즘 이용, 거리 업데이트
- 사이클 검사 결과 출력

👨‍💻코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int tc = Integer.parseInt(br.readLine());
            for (int i = 0; i < tc; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int v = Integer.parseInt(st.nextToken());
                int undirected = Integer.parseInt(st.nextToken());
                int directed = Integer.parseInt(st.nextToken());
                Graph graph = new Graph(v, undirected * 2 + directed);
                graph.init(br, undirected, directed);
                graph.bellmanFord(1);
                bw.write(!graph.isCycle ? "NO" : "YES");
                bw.newLine();
            }
        }
    }
}

class Graph {

    boolean isCycle;

    class Edge {

        /**
         * source
         */
        int s;
        int dest;
        int weight;

        Edge() {
            s = dest = weight = 0;
        }

        Edge(int s, int dest, int weight) {
            this.s = s;
            this.dest = dest;
            this.weight = weight;
        }
    }

    int V, E;
    /**
     * edge
     */
    ArrayList<Edge> e;

    Graph(int v, int en) {
        V = v;
        E = en;
        e = new ArrayList<>();
        isCycle = false;
    }

    public void init(BufferedReader br, int undirected, int directed) throws IOException {
        StringTokenizer st;
        for (int i = 0; i < undirected; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            e.add(new Edge(src, dest, weight));
            e.add(new Edge(dest, src, weight));
        }
        for (int i = 0; i < directed; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            e.add(new Edge(src, dest, -weight));
        }
    }

    public void bellmanFord(int src) {
        Graph graph = this;
        int V = graph.V, E = graph.E;

        int[] dist = new int[V + 1];
        Arrays.fill(dist, 1000000000);
        dist[src] = 0;

        for (int i = 1; i <= V; i++) {
            for (int j = 0; j < E; j++) {
                Edge edge = graph.e.get(j);
                if (dist[edge.dest] > dist[edge.s] + edge.weight) {
                    dist[edge.dest] = dist[edge.s] + edge.weight;
                }
            }
        }

        for (int i = 0; i < E; i++) {
            Edge edge = graph.e.get(i);
            if (dist[edge.dest] > dist[edge.s] + edge.weight) {
                isCycle = true;
            }
        }
    }
}

🚀TIL

• 문제를 푸는 것보다 개선에서 굉장히 고생을 많이 하였습니다.
• 최초 풀이는 평소 익숙한 방식인 2중연결리스트로 그래프 자료구조를 구현하여 일반적인 그래프 순환탐색을 이용하여 구현하였습니다.(노드마다 모든 간선을 탐색하는게 아닌, 연결 간선만 탐색)
• 그 후 최적화 시도를 위해 연결관계를 표현하지 않고 간선만 입력받아 리스트로 저장한 뒤, 간선을 순회하는 벨만포드 알고리즘 의사코드를 작성하였는데 몇가지 오류가 발생하였습니다
  • 이전엔 발생하지 않던 오버플로 발생(Integer.MAX_VALUE로 초기화 하면 오류 발생)
  • 간선을 입력받으면서 생기는 사소한 반복문 인덱스 이슈
  • 시간제한 이슈(이는 오버플로 이슈를 우회하다 생긴 이슈)
    • 한번만 수행하면 되는 벨만포드지만 오버플로로 오답이 발생, 그런데 시작지점을 변경하여 여러번 반복수행하면 오버플로 오답이 놀랍게도 해결됨(??)
• 몇일전부터 고민하던 1시작 반복문을 for(i=0; i<n; ++i)로 개선
  • 이를 통해 배열일 경우 선언문에서만 +1 해주고 입력값을 그대로 사용가능

🔍문제

https://www.acmicpc.net/problem/2660

월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.

예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.

4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

회장은 회원들 중에서 점수가 가장 작은 사람이 된다. 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

🤔발상

친구의 친구, 친구의 친구의 친구는 주어진 연결관계 내에서 경유를 통해 연결될 수 있는가를 물어보는 문제로 파악했습니다.
플로이드 워셜로 최단경로를 업데이트 하면 연결관계를 알 수 있고, 이를 이용해 가장 작은 점수, 그리고 그 점수에 해당하는 사람들을 찾으면 되며, 이를 위해 자료구조와 정렬이 필요합니다.

정렬 문제는 정렬이 문제의 핵심키워드일 경우엔 추가적인 시간복잡도, 공간복잡도 고려가 필요하지만 입력수가 50처럼 작은 경우에는 자바에서 기본적으로 제공하는 라이브러리나 스트림 등을 사용해도 큰 이슈 없이 해결되는 경우가 많습니다.

최적화를 위해선 다소 코드가 복잡해도 for문이나 배열을 이용해 직접 조작하는게 좋지만, 간단하게 해결할 수 있는 경우엔 쉬운 방법을 택하는 것도 괜찮은 전략입니다.

🔦입출력

최대 회원의 입력 수는 50이며 종료 입력을 받아 입력을 종료해야 합니다.
100 미만이므로 O(N ^ 3)에 적합합니다.

📃의사코드

- 데이터 입력받기
- 연결관계 업데이트(플로이드 워셜)
- 점수 계산
- 결과 출력(정렬된 결과)

👨‍💻코드

import java.util.*;
import java.util.stream.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int n = Integer.parseInt(br.readLine());
            Election election = new Election(n);

            while (true) {
                String[] input = br.readLine().split(" ");
                int a = Integer.parseInt(input[0]);
                int b = Integer.parseInt(input[1]);
                if (a == -1 && b == -1) {
                    break;
                }
                election.addConnection(a, b);
            }

            election.floydWarshall();
            election.calculateScore();
            bw.write(election.getResult() + "\n");      
        }
  }
}

class Election {

    static final int INF = 10000000;

    int[][] graph;
    Candidate[] candidates;
    int minScore;
    int n;

    public Election(int n) {
        this.n = n;
        this.graph = new int[n + 1][n + 1];
        this.candidates = new Candidate[n + 1];
        this.minScore = INF;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    graph[i][j] = INF;
                }
            }
        }
    }


    public void addConnection(int a, int b) {
        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    public void floydWarshall() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }
    }

    public void calculateScore() {
        for (int i = 1; i <= n; i++) {
            int max = 0;
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] < INF) {
                    max = Math.max(max, graph[i][j]);
                }
            }
            candidates[i] = new Candidate(max, i);
            minScore = Math.min(minScore, max);
        }
    }

    public String getResult() {
        StringBuilder sb = new StringBuilder();
        List<Candidate> list = Arrays.stream(candidates).filter(candidate -> {
            if (candidate == null) {
                return false;
            }
            return candidate.score == minScore;
        }).sorted().collect(Collectors.toList());

        sb.append(minScore).append(" ").append(list.size()).append("\n");
        for (Candidate candidate : list) {
            sb.append(candidate.number).append(" ");
        }
        return sb.toString().trim();
    }
}

class Candidate implements Comparable<Candidate> {

    int score;
    int number;

    public Candidate(int score, int number) {
        this.score = score;
        this.number = number;
    }

    @Override
    public int compareTo(Candidate o) {
        return this.number - o.number;
    }
}

🚀TIL

• 최저 점수인 사람들을 찾고 정렬하는게 번거로워 보여 별도 클래스를 만들고 Comparable을 구현하여 필터링, 정렬을 동시에 해결을 시도했습니다.
• 개인 IDE에선 java 17 을 사용하고 있는데, 문제 사이트는 java 11이다보니, 스트림 api의 toList() 메서드를 지원하지 않아(자바 16부터 지원) 컴파일 에러가 발생하는 이슈가 있었습니다.
• Try-with-resource 문법은 꽤 괜찮았으며, 반복문의 변수를 의미변수로 명명하는 것은 IDE를 사용할 땐 편리하지만 IDE 도움 없이 라이브코딩하는 경우 코드작성이 번거롭고 오타의 위험이 있어 안쓰는게 더 좋을 것 같습니다.

🔍문제

https://www.acmicpc.net/problem/1389

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

🤔발상

문제의 핵심 아이디어는 모든 사람들의 연결 단계 수를 계산하고 그 합인 케빈 베이컨 수 중 최소 값을 출력하는 것입니다.
어제 풀었던 알고리즘인 플로이드 와셜 알고리즘을 활용하기 적절한 문제이며 약간의 후처리 과정으로 답을 얻을 수 있습니다.

🔦입출력

유저의 수가 100 이하이므로 플로이드 와셜 알고리즘의 제한사항 중 하나인 O(N ^ 3)으로 시간 내에 수행 가능할 것으로 생각됩니다.

📃의사코드

- 연결 관계 입력받기
- 플로이드 와셜 -> 연결 관계 업데이트
- 케빈 베이컨 수 계산
- 결과 출력

👨‍💻코드

import java.util.*;
import java.io.*;

public class Main {
    
    /*
    - 모든 사람의 최단경로 계산
    - 한 사람의 최단경로 합 계산
    - 가장 작은 최단경로(케빈 베이컨의 수) 출력
    
    - 입력제한 N (2 <= N <= 100)
    */
    
  public static void main(String args[]) throws IOException{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      KevinBacon kv = new KevinBacon();
      kv.init(br);
      bw.write(String.valueOf(kv.getResult()));
      bw.close();
  }
}

class KevinBacon {
    private int n;
    private int[][] graph;
    private final int INF = 1000000;

    public void init(BufferedReader br) throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        graph = new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i!=j){
                    graph[i][j] = INF;
                }
            }
        }

        for(int i=0;i<m;i++){
            updateGraph(br.readLine());
        }
    }

    private void updateGraph(String input) throws IOException{
        String[] inputs = input.split(" ");
        int a = Integer.parseInt(inputs[0]);
        int b = Integer.parseInt(inputs[1]);

        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    private void floydWarshall(){
        for(int k=1;k<= n;k++){
            for(int i=1;i<= n;i++){
                for(int j=1;j<= n;j++){
                    int newDistance = graph[i][k] + graph[k][j];
                    if(newDistance < graph[i][j]){
                        graph[i][j] = newDistance;
                    }
                }
            }
        }
    }

    public int getResult(){
        floydWarshall();
        int minSum = Integer.MAX_VALUE;
        int result = 0;
        for(int i=1;i<=n;i++){
            int sum = 0;
            for(int j=1;j<=n;j++){
                if (graph[i][j] < INF) {
                    sum += graph[i][j];
                }
            }
            if(sum < minSum){
                minSum = sum;
                result = i;
            }
        }
        return result;
    }

}

🚀TIL

• 이전에 풀었던 문제로 개인적인 학습을 위해 클래스로 만들어 기능을 메서드 별로 분리하였습니다.(TDD 개발방법론 적용)
• 리팩토링 후 결과 제출에 이슈가 있었는데, BufferdWriter의 write 메서드를 사용할 때, int  결과값을 그대로 반환하여 String을 인자로 받는 write 메서드와 파라미터 불일치로 이상값이 출력되어 수정하였습니다.
• 코드 가독성 관련하여 몇가지 개선사항을 확인하여 다음부터 적용할 예정입니다.
  • 매직넘버 로직(graph\[i]\[j] < 10000000) -> INF 상수화 + boolean isConnect() 메서드 추출
  • 문제별로 다른 입출력 시작순서(0 시작 or 1 시작)을 구별하기 위한 1 시작일 경우 i j 관습변수가 아닌 personNumber 등의 의미변수 사용
• BufferedReader와 BufferedWriter가 가독성 측면에서 분리하는게 좋을 것 같아 try-with-resources 문법으로 감싸주면 좋을 것 같습니다.

아는 개발자 분이 알고리즘 스터디를 하신다는 이야기를 듣고 계획에 없었지만 신청하여 진행하게 되었습니다.

혼자 공부할때보단 동기부여도 생기고 다른 사람들과 교류하면서 더 좋은 성과를 얻을 것 같아 시작하였는데, 한동안 쓰지 않던 블로그를 TIL 기록을 해야해서(스터디 참가비를 환급해준다고 한다 😊) 1일 차부터 성과가 보이는 것 같습니다.

오늘의 학습 키워드

- 플로이드 워셜

내용

플로이드 워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘입니다.

다익스트라와 비슷하지만, 다익스트라는 음의 가중치를 가진 경우 사용할 수 없지만 플로이드 워셜 알고리즘은 사용할 수 있다는 차이점이 있습니다.

이에 대해선 아래에서 좀 더 자세히 이야기 해보면 좋을 것 같습니다.

핵심 아이디어

플로이드 워셜 알고리즘의 핵심 아이디어는 

i 정점과 j정점 이 존재할 때, 경유지점 k를 고려하여 최단 거리를 업데이트 하는 것입니다.

수식으로 표현하면 다음과 같습니다.

D[i][j]=min(D[i][j],D[i][k]+D[k][j])

이를 코드로 표현하면 더 보기 쉬워지는데, 2차원 배열로 표현한 그래프를 전체순회하는 2중 반복문을 경유지점 k도 고려하도록 3중 반복문으로 감싸주면 됩니다.

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (distance[i][k] + distance[k][j] < distance[i][j]) {
                distance[i][j] = distance[i][k] + distance[k][j];
            }
        }
    }
}

3중 반복문이면 시간복잡도가 O(N^3)인데 사용해도 괜찮은가? 싶은 생각이 드는데, 전체 노드의 갯수가 크면 매우 느려집니다.

N의 수가 100 이하일 때 사용하는 것이 좋습니다.

연산 시간 예측

아래는 알고리즘 문제 풀이에 사용하는 대략적인 예측방법입니다.

제 pc의 cpu 클럭수는 3.3ghz인데 이는 초당 3,300,000,000 연산이 가능하다는 의미입니다.

이를 위 사례와 연결지어 생각하면 

100 ^ 3 = 1,000,000

1,000 ^ 3 = 1,000,000,000

10,000 ^ 3 = 1,000,000,000,000

으로 개인용 pc에서도 입력값이 10,000이 넘어가면 거의 300초(5분)이 걸린다고 에측할 수 있습니다.

문제 플랫폼에서 제공하는 연산리소스는 가정용 pc보다 낮을테니 100~1000 의 입력값 제한으로 보면 될 것 같습니다.

음의 가중치

위에서 이야기했던 다익스트라 알고리즘과의 차이점인 음의 가중치에 대해 좀 더 고민해보았습니다.

다익스트라 알고리즘은 그리디 알고리즘이 핵심 아이디어이며, 지금까지의 최선해에서 주어지는 정보로 다음 최선해를 계속 개선해 나가는 방식이라 다음 정보로 음의 가중치가 입력된다면 계속 결과값이 줄어들게 됩니다.

반면 플로이드 워셜 알고리즘의 경우 핵심 아이디어는 동적 프로그래밍으로 이전에 계산한 결과값을 바탕으로 다음 결과값을 계산하므로 이전 결과값을 변경하지 않습니다.

사실 말로 풀어쓰는 것보다 코드로 보면 훨씬 이해하기 쉬운데, 다익스트라는 Queue로 구현하며(다른 방법도 있지만 가장 효과적) 무한루프에 빠질 수 있지만 플로이드 워셜은 반복문으로 구현하여 무한루프에 빠지지 않습니다.

회고

알고리즘 공부를 오랫동안 쉬어서 이전에 공부했던 내용을 복습해 나가는게 스터디의 주 목적이 될 것 같습니다.

다른 레벨들의 문제들도 한번씩 보면서 복습 내용을 넓혀가면 좋을 것 같습니다.

안녕하세요. 다메카솔🐿️ 입니다.

얼마전에 계속 공부하고 싶었던 쿠버네티스를 공부하면서, 프로젝트에 사용하는 것 외에 어떻게 더 활용할 수 있을까 고민하다가 공식인증 자격시험인 CKAD를 응시하였습니다.

개발자에게 자격증이 도움이 된다 안된다는 여러가지 의견이 있는데 저는 실무능력도 중요하지만, 장기적으로 봤을 때 이론이 뒷받침 되어야 이해도도 높아지고 더 어려운 문제를 다룰 때 도움이 된다고 생각해서 이론 공부 + 공부 내용을 검증하기 위한 방법으로 자격증 시험 응시를 자주 하는 편입니다. 
CKAD는 기타 국내 자격증이나, AWS 자격증과 비교해도 많이 비싼 가격이라 과연 필요할까? 고민을 많이 했는데, 가장 최근에 봤던 시험이 작년 가을에 보았던 SAA라 시험 본 지 오래되기도 해서 응시하기로 결정하였습니다.

시험 정보

리눅스 재단은 오픈소스 소프트웨어 개발을 위한 공동 작업 환경을 구축하는 비영리 단체입니다. 리눅스 재단은 쿠버네티스 자격증 프로그램을 관리하고 있습니다.
https://www.linuxfoundation.org/

쿠버네티스 자격증은 쿠버네티스 기술에 대한 지식과 숙련도를 검증하는 전문 자격증입니다. 다음과 같은 다양한 종류의 자격증이 있습니다.
- Certified Kubernetes Administrator (CKA): 쿠버네티스 클러스터를 배포, 구성 및 관리하는 데 필요한 기술, 지식 및 역량을 검증하는 자격증입니다.
- Certified Kubernetes Application Developer (CKAD): 쿠버네티스에서 클라우드 네이티브 애플리케이션을 설계, 구축, 구성 및 노출하는 데 필요한 기술, 지식 및 역량을 검증하는 자격증입니다.
- Certified Kubernetes Security Specialist (CKS): 쿠버네티스에서 애플리케이션을 보호하기 위한 관련 보안 원칙을 구현하고 관리하는 데 필요한 기술, 지식 및 역량을 검증하는 자격증입니다.

https://kubernetes.io/ko/training/

이번에 응시한 시험은 CKAD 이며 
- CKAD는 리눅스 재단에서 제공하는 공식 쿠버네티스 자격증입니다.
- 시험은 온라인으로 진행되며, 2시간 동안 16개의 문제를 풀어야 합니다.(시험마다 다른 것 같습니다)
- 시험 점수는 100점 만점이며, 66점 이상을 획득하면 합격입니다.
- 시험 비용은 395달러(2024.05 기준)이며, 쿠폰을 사용하면 할인된 가격으로 응시할 수 있습니다

시험 과목: Certified Kubernetes Application Developer (CKAD)

CKAD는 쿠버네티스 환경에서 애플리케이션을 설계, 구축, 구성 및 노출하는 데 필요한 기술, 지식 및 역량을 검증하는 자격증입니다. 본 시험은 퍼포먼스 기반으로, 실제 쿠버네티스 환경에서 문제를 해결하는 능력을 평가합니다.

시험 범위:
- Core Concepts (13%)
    - 쿠버네티스 기본 아키텍처 이해
    - 쿠버네티스 오브젝트 정의 및 관리 (Pod, Deployment, Service, Namespace 등)
- Pod Design (20%)
    - Pod 생성 및 관리, 컨테이너 환경 설정
    - Pod 및 컨테이너 라이프사이클 관리
    - 리소스 사용량 관리, 헬스 체크, 로깅 및 모니터링 설정
- Configuration (18%)
    - ConfigMap 및 Secret을 사용한 애플리케이션 설정
    - Security Context, Resource Limits 및 Quotas 설정
    - 서비스 디스커버리 및 네트워킹 설정
- Observability (18%)
    - 애플리케이션 로그 수집 및 분석
    - 애플리케이션 및 쿠버네티스 클러스터 모니터링
    - 문제 해결 및 디버깅
- Deployment (20%)
    - Deployment, StatefulSet, DaemonSet 등 다양한 배포 방법 이해 및 활용
    - 롤링 업데이트, 롤백 및 블루-그린 배포 전략 구현
- Services & Networking (11%)
    - 쿠버네티스 네트워킹 기본 사항 이해
    - Service 오브젝트를 활용한 서비스 노출 및 디스커버리
    - Ingress 컨트롤러를 사용한 외부 트래픽 관리
더 자세한 과목 내용은 CKAD Exam Curriculum에서 확인할 수 있습니다.

https://training.linuxfoundation.org/certification/certified-kubernetes-application-developer-ckad/

시험 접수 팁

CKAD 시험은 온라인으로 진행되며, 리눅스 재단 웹사이트에서 접수할 수 있습니다. 시험 접수 시 다음과 같은 정보를 입력해야 합니다.

- 이름, 이메일 주소, 연락처
- 신분증 정보
- 시험 응시 날짜 및 시간

시험 접수 후, 시험 응시를 위한 안내 메일을 받게 됩니다. 안내 메일에 따라 시스템 설정 및 신분 확인 절차를 진행해야 합니다.

쿠폰 할인:
시험 가격이 비싸다보니 할인을 꼭 받으시는 걸 추천드립니다.
쿠폰은 여러 경로로 얻을 수 있는데, 가장 큰 할인폭은 블랙프라이데이의 사이버먼데이 행사에서 50% 할인 쿠폰을 구할 수 있고, 그 외에도 특정 기간마다 쿠폰을 제공하고 있습니다.
최신 정보를 업데이트 하는 사이트들이 많이 있으며, 제가 이용한 사이트는 다음과 같습니다.

https://github.com/techiescamp/linux-foundation-coupon

시험 준비 방법

공식 문서를 활용하여 공부하거나 리눅스 재단에서 CKAD 시험과 함께 판매하는 커리큘럼을 이용하는 방법도 있지만, 저는 많은 후기들이 추천하는 Udemy의 CAKD 강의를 활용하였습니다.

https://www.udemy.com/course/certified-kubernetes-application-developer/?couponCode=KEEPLEARNING

해당 강의에선 따로 실습환경을 구축하지 않아도 명령어들을 실행하면서 숙달시킬 수 있는 실행환경을 제공해주어서 공부에 큰 도움이 되었고, 강의도 핵심을 짚어주는 강의로 학습에 대한 부담을 크게 낮춰주었습니다.

또 Mock 시험을 제공해서 따로 dump를 풀거나 하는 준비과정 없이, 시험에 응시하였습니다.

시험을 접수하면 리눅스재단에서 killer.sh이라는 모의시험 응시 세션을 2회 제공하는데, 하나의 세션을 활성화시키면 총 3일동안 반복해서 응시할 수 있으며, 불합격 시 재시험을 고려하여 2회 제공하는 것으로 보입니다. 난이도가 상당한 것으로 유명한데, 직접 풀어보면 하나의 문제에 여러가지 요구사항이 포함되어 있으며, 쿠버네티스 외에도 기본적인 리눅스 활용능력도 필요하여 체감 난이도가 높게 느껴지는 것 같습니다.

그리고 시험 시간이 생각보다 타이트한데, 그래서 시간을 단축할 수 있는 여러가지 방법들을 준비하시는 것을 추천드립니다.
모든 yaml파일을 직접 작성하는 것보다 --dry-run=client -oyaml 명령어를 통해 기본 문법이 작성된 yaml을 생성하여 수정하거나, 공식 문서에 작성된 예제를 빠르게 찾아 활용하는 것이 큰 도움이 되었습니다.

또 난이도가 쉬운 문제를 틀리지 않는 것이 시험 합격에 도움을 주기 때문에, 조금 까다롭거나 시간이 걸릴 것 같은 문제는 flag 체크 후, 전체 문제를 모두 검토 후에 푸시는 것을 추천드립니다.

시험 후기

정확하게 기억이 나지는 않지만 생각나는 대로 기출문제 내용들을 적어보았습니다.

1. 카나리배포(기존에 deploy가 존재하며, 추가로 신규 버전을 배포할 예정인데 요구하는 비율로 배포되도록 작성)
2. cronjob 설정
3. docker 이미지 빌드 및 압축 (이름, 태그 , tar등)
4. networkPolicy가 구성된 환경에서 networkPolicy를 수정하지 않고 접속 이슈 해결
5. deployment 작성
6. secret 작성 및 container에서 keyRef로 활용
7. configmap 작성
8. container 내에 serviceAccount 설정
9. securityContext 설정 (root 권한상승 금지, 실행 유저 지정)
10. deploy 신버전 배포 및 롤백
11. api deprecation 이슈 해결(구버전 api 제공 후, 배포 이슈 해결, 공식문서 활용하여 문법과 api 버전 확인 필요)
12. log를 확인하고, 파일로 저장
13. ingress, egress 설정
14. 배포된 deployment에 서비스 생성하여 expose하기

다른 블로그 후기를 통해 큰 도움을 얻어 좋은 결과를 얻은 만큼, 다음 CKAD 시험을 준비하는 분들에게 도움이 되었으면 좋겠습니다.

모두 좋은 결과 얻으시길 바랍니다.