Graph, Testing

calis_ws·2023년 7월 1일

MST TIL algorithm assert mock test 아기사자반

최소 신장 트리 (MST)

그래프를 통해서 만들수 있는 모든 신장트리 중 해당 트리를 이루는 간선들의 합이 최소인 신장트리를 말한다.

Kruskal

Kruskal 알고리즘은 그래프 간선들을 오름차순을 정렬하여 가장 낮은 가중치의 간선부터 차례로 추가하는 방법이다.

동작 방식

그래프의 간선들을 가중치(비용)의 오름차순으로 정렬한다.
정렬된 간선 리스트에서 가장 작은 가중치를 가진 간선을 선택한다.
선택한 간선을 현재의 신장 트리에 추가했을 때 사이클이 생기지 않는다면 해당 간선을 트리에 추가한다.
위의 과정을 반복하여 신장 트리에 간선을 추가한다. 이 때, 추가되는 간선의 수는 (정점의 개수 -1)이 될 때까지이다.

예제 입력

Kruskal

public class Kruskal {
    int[] parent;
    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer neTokenizer = new StringTokenizer(reader.readLine());
        int nodeCount = Integer.parseInt(neTokenizer.nextToken());
        int edgeCount = Integer.parseInt(neTokenizer.nextToken());

        // Kruskal 알고리즘은 서로소 집합의 개념을 이용해 서로 다른 두 정점을
        // 연결했을 때 사이클이 발생하는지 안하는지 구분한다.
        
				// 배열로 표현한 트리를 만들자
				parent = new int[nodeCount];  // 노드의 부모를 저장하기 위한 배열
        // 처음에는 자기 자신이 대표인 서로소 집합으로 초기화
        for (int i = 0; i < nodeCount; i++) {
            parent[i] = i;
        }
				
				// 간선 정보 해독
        // (시작Node 끝Node 가중치)
        int[][] edges = new int[edgeCount][3];
        for (int i = 0; i < edgeCount; i++) {
            StringTokenizer edgeTokenizer = new StringTokenizer(reader.readLine());
            edges[i][0] = Integer.parseInt(edgeTokenizer.nextToken());
            edges[i][1] = Integer.parseInt(edgeTokenizer.nextToken());
            edges[i][2] = Integer.parseInt(edgeTokenizer.nextToken());
        }

        // 1. 간선을 가중치 기준에서 정렬한다.
        Arrays.sort(edges, Comparator.comparing(edge -> edge[2]));

        // 2. 간선들을 가중치 순서대로 순회하면서 고른다.
        int picked = 0; // N-1개 고르면 끝내기위해 선언한 변수

        // * 알고리즘적으로는 필요 없지만 값을 확인 하기 위한 변수들
				// 가중치의 총 합을 확인 하기 위한 변수
        int totalWeight = 0; 
				// 선택된 간선을 확인 하기 위한 리스트
        List<String> pickedEdges = new ArrayList<>();

        for (int i = 0; i < edgeCount; i++) {
            int start = edges[i][0];
            int end = edges[i][1];

            // 2-1. start의 end를 연결한 간선을 택하면
            // 사이클이 생기지 않는지? findSet, union
            if (findSet(start) != findSet(end)) { // 사이클이 안생긴다면
                // 두 원소를 하나의 집합으로
                union(start, end);
                // 간선을 골랐음을 표시
                picked++;
                // 총 가중치 업데이트
                totalWeight +=  edges[i][2];
                pickedEdges.add(Arrays.toString(edges[i]));
            }

            // 3.고른 간선의 갯수가 N-1개가 될 때 까지
            if (picked == nodeCount - 1) break;
        }

				// 총 가중치 및 선택된 간선들 확인을 위한 출력
        System.out.println(totalWeight);
        System.out.println(pickedEdges);
    }

    // findSet : 내 부모가 나일 때까지 재귀 호출
    public int findSet(int node) {
        if (parent[node] != node)
            return findSet(parent[node]);
        else return parent[node];
    }

    // union : y가 속한 집합을 x가 속한 집합에 합친다.
    public void union(int x, int y) {
				// y가 속한 대표자의 parent 저장소에 = x의 대표자를 넣어줌으로써
        // y가 속한 집합이 x가 속한 집합으로 들어갔음을 표시해 줄수있다.
        parent[findSet(y)] = findSet(x);
    }


    public static void main(String[] args) throws IOException {
        new Kruskal().solution();
    }
}

출력

Prim

Prim 알고리즘은 시작 정점부터 단계적으로 트리를 확장하는 방법이다.

동작 방식

임의의 시작 정점을 선택하고 해당 정점을 현재의 신장 트리에 포함시킨다.
현재 신장 트리에 포함된 정점과 포함되지 않은 정점 사이의 간선 중에서 가장 작은 가중치를 가진 간선을 선택한다.
선택된 간선으로부터 연결된 정점을 현재의 신장 트리에 포함시킨다.
위의 과정을 반복하여 신장 트리에 정점을 추가하고 모든 정점이 포함될 때까지 진행한다.

Prim

public class Prim {
    public int solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer newTokenizer = new StringTokenizer(reader.readLine());

        int nodeCount = Integer.parseInt(newTokenizer.nextToken());
        int edgeCount = Integer.parseInt(newTokenizer.nextToken());

        // 가중치가 저장된 인접 행렬 사용
        int[][] adjMatrix = new int[nodeCount][nodeCount];
        // 인접행렬 가중치 값 초기화
        for (int i = 0; i < edgeCount; i++) {
            StringTokenizer edgeTokenizer = new StringTokenizer(reader.readLine());
            int start = Integer.parseInt(edgeTokenizer.nextToken());
            int end = Integer.parseInt(edgeTokenizer.nextToken());
            int weight = Integer.parseInt(edgeTokenizer.nextToken());

            // 무향 그래프임으로 양방향다 값을 넣어준다.
            adjMatrix[start][end] = weight;
            adjMatrix[end][start] = weight;
        }

        // 방문정보 (선택정보)
        boolean[] visited = new boolean[nodeCount];
        // 현재 선택된 정점들에서 해당 정점까지 도달 가능한 가장 짧은 거리
        int[] dist = new int[nodeCount];
        Arrays.fill(dist, Integer.MAX_VALUE); // dist 의 초기값을 최대치로 초기화

        // 어느 노드에서 도달했는지 정보를 저장
        int[] parent = new int[nodeCount];

        // 1. 임의의 정점 선택 (시작 정점 선택)
        dist[0] = 0;    // 자기 자신까지의 거리 = 0
        parent[0] = -1; // 시작 정점인것을 -1로 표현

        // 2. 모든 정점을 선택할때가지 순회한다.
        for (int i = 0; i < nodeCount; i++) {
            int minDist = Integer.MAX_VALUE;
            int idx = -1;
            // 2-1. 인접한 정점 중 최소 비용 간선으로 연결되는 정점을 찾느다.
            for (int j = 0; j < nodeCount; j++) {
                if(!visited[j] && dist[j] < minDist) {
                    // 선택 후보
                    minDist = dist[j];
                    idx = j;
                }
            }   // 위 for 문이 끝나면 현재 정점에서 갈 수있는 간선들의 정보(dist[])와
                // 그 중 최소 가중치를 가진 정점정보(idx)가 업데이트 되어있을 것이다.

            // 가장 가까운곳 방문 처리
            visited[idx] = true;

            // 2.2 정점 정보를 바탕으로 도달 가능 정보를 갱신한다.
            // idx 로 부터 다른 정점들에 도달할 수 있는지를 확인하고 (adjMatrix)
            // 그 정보를 바탕으로 dist 배열을 업데이트 한다.
            for (int j = 0; j < nodeCount; j++) {
                // 조건 a. 방문하지 않았고,
                //      b. 연결되어 있으며,
                //      c. 본래 최단거리보다 더 짧게 도달 가능할 때
                if(
                        !visited[j] &&
                        adjMatrix[idx][j] != 0 &&
                        dist[j] > adjMatrix[idx][j]) {
                    // dist, parent 갱신
                    dist[j] = adjMatrix[idx][j];
                    parent[j] = idx;
                }
            }
        }

        // Prim 알고리즘의 총 가중치는 dist 배열에 저장됨
        int totalWeight = 0;
        for (int i = 0; i < nodeCount; i++) {
            totalWeight += dist[i];
        }
        System.out.println(totalWeight);

        // 어떤 순서로 연결되있는지즌 parent 배열에 담김
        System.out.println(Arrays.toString(parent));

        return totalWeight;
    }

    public static void main(String[] args) throws IOException {
        new Prim().solution();
    }

Testing

테스트란?

노출되지 않은 숨어있는 결함(Fault)을 찾기 위해 소프트웨어를 작동시키는 일련의 행위와 절차
오류 발견을 목적으로 프로그램을 실행하여 품질을 평가하는 과정
개발된 소프트웨어의 결함과 문제를 식별하고 품질을 평가하며 품질을 개선하기 위한 일련의 활동
일반적으로 테스트 케이스에 따라 SW를 동적으로 실행시켜 예상결과치와 비교 분석
SW의 동작과 성능, 안정성이 요구되는 수준을 만족하는지 확인하기 위한 결함을 발견하는 메커니즘
시스템이 정해진 요구를 만족하는지, 예상과 실제 결과가 어떤 차이를 보이는지 수동 또는 자동 방법을 동원하여 검사하고 평가하는 일련의 과정 - IEEE, 1993

테스트 단계

Mock

Mockito란 단위 테스트를 위해 사용되는 인기있는 mocking 프레임워크이며 사용하면 의존성 객체를 가짜(mock) 객체로 대체하여 테스트의 격리성을 확보하고, 테스트 중에 원하는 동작을 가짜 객체에 지정할 수 있다.

@Mock : 테스트할 때 실제 데이터베이스에 의존하지 않고 테스트를 진행하기 위해, Mock 객체를 사용하여 Repository의 동작을 대신 모방할 수 있다.

테스트 작성 형식

Given - When - Then 패턴

소프트웨어 테스트에서 사용되는 구조적인 접근 방식이다.
테스트 케이스를 설명하고 구성하는 데 도움을 주며, 테스트의 명확성과 가독성을 높이는 데에 유용하다.

given : 테스트가 진행되기 위한 전제 조건을 준비
when : 테스트하고 싶은 실제 기능을 작성
then : 실행한 결과가 기대한 것과 같은지 확인

assert문

테스트 코드에서 특정 조건이 참임을 검증하는 데 사용되는 메서드이며, 사용하여 예상된 결과와 실제 결과를 비교하여 테스트를 수행할 수 있다.

출처 : 멋사 5기 백엔드 위키 5팀 '오'로나민 C, 11팀 11번가

인사이트 타임

홀짝에 따라 다른 값 반환하기

https://school.programmers.co.kr/learn/courses/30/lessons/181935

class Solution {
    public int solution(int n) {
        int sum = 0;
        for (int i = 0; i <= n; i += 2) {
            if (n % 2 != 0) sum += i + 1;
            else sum += i * i;
        }
        return sum;
    }
}

각도기

https://school.programmers.co.kr/learn/courses/30/lessons/120829

class Solution {
    public int solution(int angle) {
        if (angle == 180) return 4;
        else if (angle < 180 && angle > 90) return 3;
        else if (angle == 90) return 2;
        else return 1;
    }
}

나머지가 1이 되는 수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/87389

class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i = n; i > 1; i--){
            if (n % i == 1) answer = i;
        }
        return answer;
    }
}

자릿수 더하기

https://school.programmers.co.kr/learn/courses/30/lessons/12931

import java.util.*;

public class Solution {
    public int solution(int n) {
        int answer = 0;
        while (n != 0) {
            answer += n % 10;
            n /= 10;
        }
        return answer;
    }
}

아기사자반

REST API
1. URI는 정보의 자원을 표현해야한다.
2. 자원에 대한 행위는 HTTP Method(GET, POST, PUT, DELETE)로 표현한다.

잘못된 예시
GET /members/delete/1 -> X

트랜잭션 ACID : 면접 단골질문
영속성 컨텍스트

{} -> @PathVariable
? -> @RequestParam

review

매일매일 어렵다. 점점 리뷰가 짧아지는건 기분탓이 아니다. 오늘 배웠던 것중에서 이해한건 하나도 없었다. 이상 리뷰 마침.

calis_ws

반갑습니다람지

이전 포스트

인텔리제이 콘솔 한글 깨짐

다음 포스트

Graph, Testing

최소 신장 트리 (MST)

Kruskal

동작 방식

예제 입력

Kruskal

Prim

동작 방식

Prim

Testing

테스트란?

테스트 단계

Mock

테스트 작성 형식

Given - When - Then 패턴

assert문

인사이트 타임

홀짝에 따라 다른 값 반환하기

각도기

나머지가 1이 되는 수 찾기

자릿수 더하기

아기사자반

review

인텔리제이 콘솔 한글 깨짐

Logging, Profiles

0개의 댓글