지금의 기록이 미래의 자산이 된다.

Today's records become tomorrow's assets.

[solved.ac] Class3++ 11724. 연결 요소의 개수(DFS)

2023-11-28

devFancy

Algorithm

성능 요약
구분
Answer Code(2023.11.28)
문제풀이
Review

문제 링크

성능 요약

메모리: 113376 KB, 시간: 552 ms

구분

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

Answer Code(2023.11.28)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.io.*;

class Main {
  final static int MAX = 1000 + 10;
  static boolean[][] graph;
  static boolean[] visited;
  static int N, M;
  static int answer;

  static void dfs(int idx) {
    visited[idx] = true;
    for(int i = 1; i <= N; i++) {
      if(visited[i] == false && graph[idx][i]) {
        dfs(i);
      }
    }
  }

  public static void main(String[] args) throws IOException {
    // 0. 입력 및 초기화
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());

    // 1. graph에 연결 정보 채우기
    graph = new boolean[MAX][MAX];
    visited = new boolean[MAX];

    int u, v;
    for(int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      u = Integer.parseInt(st.nextToken());
      v = Integer.parseInt(st.nextToken());
      graph[u][v] = true;
      graph[v][u] = true;
    }

    // 2. dfs(재귀함수 호출) - visited가 모두 true일때까지 방문한다.
    for(int i = 1; i <= N; i++) {
      if(visited[i] == false) {
        dfs(i);
        answer++;
      }
    }

    // 3. 출력
    bw.write(String.valueOf(answer));

    bw.close();
    br.close();
  }
}

문제풀이

아이디어: ‘연결 요소의 개수를 구하는 프로그램’에서 연결되어 있다는 것을 그래프에서 탐색하는 방법으로 풀어야 겠다 -> DFS 사용하자.

Step0. 입력 및 초기화

class Main {
    static final int MAX = 1000 + 10;
    static boolean[][] graph;
    static boolean[] visited;
    static int N, M;
    static int answer;

    public static void main(String[] args) throws IOException {
      // 0. 입력 및 초기화
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());
      ...
    }
}

이전 바이러스 문제와 거의 비슷하기 때문에, 비슷한 부분들에 대한 문제풀이는 생략했다.
N과 M개의 범위를 볼 때, 최대 1000개라고 되어 있어서, MAX라는 변수를 선언했고, 1000 + 10개로 초기화했다.
- static + final = “고정된 + 최종적인”의 의미로, 모든 영역에서 고정된 값으로 상수를 선언하고자 할 때 사용한다. => 불변의 값을 가진다.
- MAX라는 상수를 graph와 visited를 만들기 위해서 사용할텐데, 넉넉하게 10개를 추가했다.
- Tip : 문제를 풀면서 발생하는 시간 낭비와 예외 처리를 한 번에 끝낼 수 있기 때문에, 넉넉하게 10개를 추가하자.
그리고 입력 부분에서 첫번째 줄에 N, M을 띄어쓰기를 기준으로 구분하기 때문에 StringTokenizer.nextToken을 이용하여 값을 저장한다.

Step1. graph에 연결 정보 채우기

class Main {
    final static int MAX = 1000 + 10;
    static boolean[][] graph;
    static boolean[] visited;
    static int N, M;
    static int answer;

    public static void main(String[] args) throws IOException {
      ...
      // 1. graph에 연결 정보 채우기
      graph = new boolean[MAX][MAX];
      visited = new boolean[MAX];

      int u, v;
      for(int i = 0; i < M; i++) {
        st = new StringTokenizer(br.readLine());
        u = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());
        graph[u][v] = true;
        graph[v][u] = true;
      }
      ...
    }
}

위에서 말했던 MAX라는 상수를 배열 크기로 graph와 visited를 선언한다.
그런 다음, M번만큼 반복문을 돌려서 간선의 양 끝점인 u와 v가 연결된 부분은 true로 바꿔준다.

Step2. dfs(재귀함수 호출)

바이러스 문제와 다른 점은, 이 문제는 모든 요소를 방문할 때까지 반복하는 문제이므로, 반복문을 선언해줘야 한다.

class Main {
    ...
    static void dfs(int idx) {
      visited[idx] = true;
      for(int i = 1; i <= N; i++) {
        if(visited[i] == false && graph[idx][i]) {
          dfs(i);
        }
      }
    }
    
    public static void main(String[] args) throws IOException {
        ...
        // 2. dfs(재귀함수 호출) - visited가 모두 true일때까지 방문한다.
        for(int i = 1; i <= N; i++) {
          if(visited[i] == false) {
            dfs(i);
            answer++;
          }
        }
        ...
    }
}

1번부터 N번까지 모든 정점을 방문하기 때문에 1부터 N까지 반복하는 것이고, 한번도 방문하지 않았을 경우에만 dfs를 호출한다.
dfs 함수에서는 N번만큼 반복문을 돌려서, 한번도 방문하지 않은 경우 && idx 번호와 i번호가 연결된 경우에만 dfs를 호출하도록 한다.
해당 예제 1번에서, 아래와 같이 입력 값을 받을 경우

처음에는 1,2,5에서 끝나기 때문에 여기서 연결 요소의 개수가 +1 증가하고

두번째에는 3,4,6에서 끝나기 때문에 여기서 연결 요소의 개수가 +1 증가하게 된다.
그래서 dfs가 끝난 뒤에 +1 증가하므로 dfs 뒤에 answer++를 해주는 것이다.

Step3. 출력하기

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

      // 3. 출력
      bw.write(String.valueOf(answer));

      bw.close();
      br.close();
    }
}

출력하기는 연결 요소의 개수, 즉 answer 값을 출력하므로 bw.write(String.valueOf(answer));을 작성한다.

여기서 BufferedWriter를 통해 String으로 전달해줘야 하므로 String.valueOf() 함수를 안에 넣은 것이다.
그리고 BufferedReader, BufferedWriter 모두 버퍼를 잡아 놓았기 때문에 반드시 flush() 또는 close()를 호출해서 뒤처리를 해줘야한다.

flush()는 스트림을 비우는 함수이고, close()는 스트림을 닫는 함수이다.

만약 한번 출력후, 다른 것도 출력하고자 한다면 flush()를 사용하면 된다.

Review

해당 문제는 이전 바이러스 문제와 비슷해서, 조금더 빠르게 풀 수 있었다.
문제를 풀면서, 입출력에 대한 여러 함수를 배울 수 있어서 좋았다.

Read All

[Programmers] 후보키 (2019 카카오 블라인드)

2023-11-27

devFancy

Algorithm

성능 요약
- 구분
문제풀이
Answer Code(23.11.27)
Reference

문제 링크

성능 요약

메모리: 70.4 MB, 시간: 3.66 ms

구분

코딩테스트 연습 > 2019 KAKAO BLIND RECRUITMENT

문제풀이

먼저, 주어진 데이터베이스의 릴레이션에서 후보키의 개수를 찾는 문제입니다.

주어진 String 타입의 2차원 배열 relation에서 후보키의 개수를 찾아 반환합니다.

코드는 재귀적인 방식인 깊이 우선 탐색(DFS)을 사용하여 후보키를 찾습니다.

먼저, 주어진 데이터베이스의 릴레이션에서 후보키의 개수를 찾는 문제입니다. 주어진 String 타입의 2차원 배열 relation 에서 후보키의 개수를 찾아 반환합니다. 코드는 재귀적인 방식인 깊이 우선 탐색(DFS)을 사용하여 후보키를 찾습니다.

전역 변수 및 메서드:
- List<String> candi: 후보키를 저장하는 리스트입니다.
- dfs 메서드: 깊이 우선 탐색을 수행하는 메서드로, 후보키를 찾기 위해 가능한 모든 조합을 탐색합니다.

이 부분은 dfs 메서드로, 깊이 우선 탐색(Depth-First Search)을 수행하여 후보키를 찾아내는 역할을 합니다. 코드를 한 부분씩 살펴보겠습니다.

깊이가 목표 깊이에 도달했을 때:
```
 if (depth == end) {
     // ...
 }
    
```
- depth가 end와 같아지면, 즉, 조합이 완성된 경우입니다.
- 조합을 확인하고 유일성을 검사하는 부분입니다.

조합 확인 및 유일성 검사:

 List<Integer> list = new ArrayList<>();
 String key = "";
 for (int i = 0; i < visited.length; i++) {
     if (visited[i]) {
         key += String.valueOf(i);
         list.add(i);
     }
 }
    

선택된 열의 인덱스를 list에 저장하고, key에는 해당 인덱스를 문자열로 연결합니다.

중복 체크를 위한 Map 생성 및 유일성 검사:

 Map<String, Integer> map = new HashMap<>();
    
 for (int i = 0; i < relation.length; i++) {
     String s = "";
     for (Integer j : list) {
         s += relation[i][j];
     }
    
     if (map.containsKey(s)) {
         return;
     } else {
         map.put(s, 0);
     }
 }
    

조합을 이용하여 만들어진 문자열 s를 이용해 map에 저장하여 유일성을 체크합니다.
이미 존재하는 경우(map.containsKey(s)), 중복된 튜플이므로 함수를 종료합니다.

최소성 검사 및 후보키 추가:
```
 for (String s : candi) {
     int count = 0;
     for(int i = 0; i < key.length(); i++){
         String subS = String.valueOf(key.charAt(i));
         if(s.contains(subS)) count++;
     }
     if (count == s.length()) return;
 }
    
```
- 현재 후보키(key)가 이미 저장된 후보키들 중에서 어떤 것에도 속하지 않는지를 확인합니다.
- count를 통해 일치하는 문자열의 개수를 셉니다.
- 만약 count가 현재 후보키의 길이와 같다면, 현재 후보키는 이미 저장된 후보키의 일부이므로 함수를 종료합니다.
- 그렇지 않으면, candi 리스트에 후보키를 추가합니다.
재귀 호출을 통한 깊이 우선 탐색:
```
 for (int i = start; i < visited.length; i++) {
     if (visited[i]) continue;
    
     visited[i] = true;
     dfs(visited, i, depth + 1, end, relation);
     visited[i] = false;
 }
    
```
- 재귀 호출을 통해 깊이 우선 탐색을 수행합니다.
- 현재 선택한 열을 방문 표시하고, 깊이를 증가시켜 재귀 호출을 합니다.
- 재귀 호출이 끝나면 방문 표시를 해제하여 이전 상태로 돌아갑니다.

이렇게 하면 dfs 메서드는 주어진 릴레이션에서 모든 가능한 후보키를 찾아내는 역할을 합니다.

Answer Code(23.11.27)

import java.util.*;

class Solution {
    List<String> candi = new ArrayList<>();

    public int solution(String[][] relation) {
        int answer = 0;

        for (int i = 0; i < relation[0].length; i++) {
            boolean[] visited = new boolean[relation[0].length];
            dfs(visited, 0, 0, i + 1, relation);
        }
        answer = candi.size();
        return answer;
    }

    public void dfs(boolean[] visited, int start, int depth, int end, String[][] relation) {
        if (depth == end) {
            List<Integer> list = new ArrayList<>();
            String key = "";
            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) {
                    key += String.valueOf(i);
                    list.add(i);
                }
            }

            Map<String, Integer> map = new HashMap<>();

            for (int i = 0; i < relation.length; i++) {
                String s = "";
                for (Integer j : list) {
                    s += relation[i][j];
                }

                if (map.containsKey(s)) {
                    return;
                } else {
                    map.put(s, 0);
                }
            }

            // 후보키 추가
            for (String s : candi) {
                int count = 0;
                for(int i = 0; i < key.length(); i++){
                    String subS = String.valueOf(key.charAt(i));
                    if(s.contains(subS)) count++;
                }
                if (count == s.length()) return;
            }
            candi.add(key);

            return;
        }

        for (int i = start; i < visited.length; i++) {
            if (visited[i]) continue;

            visited[i] = true;
            dfs(visited, i, depth + 1, end, relation);
            visited[i] = false;
        }

    }
}

Reference

https://tmdrl5779.tistory.com/219)

Read All

[Programmers] [1차] 프렌즈4블록(2018 카카오 블라인드)

2023-11-27

devFancy

Algorithm

성능 요약
- 구분
Answer Code(23.11.27)
문제풀이

문제 링크

성능 요약

메모리: 72.6 MB, 시간: 3.40 ms

구분

코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT

Answer Code(23.11.27)

import java.util.*;

class Solution {
    static boolean v[][]; // 체크 배열
    
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        
        char copy [][] = new char[m][n];
        
        for(int i = 0; i < m; i++) {
            copy[i] = board[i].toCharArray();
        }
        
        boolean flag = true;
        while(flag) {
            v = new boolean[m][n];
            flag = false;
            for(int i = 0; i < m-1; i++) {
                for(int j = 0; j < n-1; j++) {
                    if(copy[i][j] == '#') continue; // #은 빈칸을 의미
                    if(check(i, j, copy)) {
                        v[i][j] = true;
                        v[i][j+1] = true;
                        v[i+1][j] = true;
                        v[i+1][j+1] = true;
                        flag = true;
                    }
                }
            }
            answer += erase(m,n,copy);
            v = new boolean[m][n];
        }
        return answer;
    }
    /* 2*2가 같은지 체크 */
    public static boolean check(int x, int y, char[][] board) {
        char ch = board[x][y];
        
        if(ch == board[x][y+1] && ch ==board[x+1][y] && ch == board[x+1][y+1]) {
            return true;
        }
        return false;
    }
    public static int erase(int m, int n, char [][] board) {
        int cnt = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(v[i][j]) {
                    board[i][j] = '.';
                }
            }
        }
        /* 큐를 이용해 세로로 제거 작업 진행 */
        for(int i = 0; i < n; i++) {
            Queue<Character> q = new LinkedList<>();
            for(int j = m-1; j >=0; j--) {
                if(board[j][i] == '.') {
                    cnt++; // 지우는 블록 카운트
                } else {
                    q.add(board[j][i]);
                }
            }
            int idx = m-1;
            // 삭제한 블록 위의 블록들 내리기
            while(!q.isEmpty()) {
                board[idx--][i] = q.poll();
            }
            // 빈칸 채우기
            for(int j = idx; j >=0; j--) {
                board[j][i] = '#';
            }
        }
        return cnt;
    }
}

문제풀이

시뮬레이션 유형으로 특정 규칙에 따라 블록이 지워지고 이동하는 과정을 반복하며 최종적으로 몇 개의 블록이 지워지는지를 구하는 것이 목표다.

문제에서는 다음과 같은 매개변수가 주어지고, 2가지를 기준으로 코드를 작성하면 된다.
- 판의 높이 = m
- 폭 = n
- 판의 배치 정보 = board

2*2블록이 같은지 체크하는 함수
- 현재 블록을 기준으로 오른쪽, 아래, 오른쪽 아래가 같은지 체크하면 된다.
- 이때 조심할 것은 배열의 범위를 벗어나지 않도록 해야 한다.
- 만약 2*2 블록이 같다면 이를 기록할 boolean[][] 배열에 따로 표시를 한다.
- 직접적으로 board 배열을 바꾸지 않는 이유는 모든 블록을 조사한 후에 일괄적으로 처리해야 하기 때문이다.
블록을 제거하는 함수
- 큐를 이용해 세로로 블록을 제거하는 방법을 사용했다.
- 맨 아래에서부터 큐에 집어넣고, 제거해야 하는 블록이라면 개수만 세고 큐에 넣지 않는다.
- 이후에 큐에 있는 원소를들 빼내서 아래부터 차곡차곡 블록을 쌓아준다.
- 빈 블록은 ‘#’으로 표시해준다.

Read All

[내 코드가 그렇게 이상한가요?] 13 - 16장 정리

2023-11-26

devFancy

GoodCode
이 글은 내 코드가 그렇게 이상한가요? 책을 읽고 정리한 내용을 바탕으로 작성하였습니다.

13장. 모델링: 클래스 설계의 토대

시스템, 모델, 모델링
- 시스템
  - 사전 정의: 수많은 구성 요소로 이루어진 집합체로, 각각의 부분이 유기적으로 연결되어, 전체적으로 하나의 목적을 갖고 움직이는 것
  - 시스템은 목적 달성을 위한 수단
- 모델: 특정 목적 달성을 위해서, 최소한으로 필요한 요소를 갖춘 것
- 모델링: 모델의 의도를 정의하고, 구조를 설계하는 것
모델링
- 모델은 대상이 아니라 목적 달성의 수단이다.
  - 목적 중심으로 이름을 잘 설계하면, 목적을 달성하기에 적절한 모델을 설계할 수 있다.
- 단일 책임 원칙 == 단일 목적 원칙
  - 특정 목적에 특화되게 설계해야, 변경하기 쉬운 고품질 구조를 갖게 된다.
- 모델을 검토할 때 목적 이외에 요소가 들어가 있다면 다시 수정한다.
- 모델 != 클래스 => 모델 하나는 여러 개의 클래스로 구성된다. (1:N)
  - 예를 들어, 모델 - 상품이면, 클래스 - 상품 ID, 상품명, 판매 가격, 재고 수량
  - 클래스 설계와 구현에서 무언가를 깨닫는다면, 이를 모델에 피드백해야 한다.
  - 피드백 사이클을 계속 돌리는 것이 설계 품질을 높이는 비결이다.
기능성과 모델링의 관계
- 기능성은 소프트웨어의 품질 특성 중 하나로, 고객의 니즈를 만족하는 정도를 말한다.
- 숨어있는 목적 파악하기
  - 상품 구매를 하면, ‘상품 구입’과 ‘구매 품목’에 대해서만 생각할 수 있지만, 법적인 요소도 고려해야 한다.
  - 위처럼 기능을 제대로 발휘하려면, ‘개념의 정체’와 ‘뒤에 숨어 있는 중요한 목적’을 잘 파악해야 한다.
  - 목적 달성 수단으로 해석하면, 추상화 했을 때 모델의 확장성이 커진다.
  - 예를 들어, 이동 수단이라는 목적을 추상화 했다면, 구체화로는 이족 보행, 마차, 전차, 전기 자동차, 비행기가 있다.
14장. 리팩터링
- 리팩터링이란 실질적인 동작은 유지하면서, 구조만 정리하는 작업이다.
리팩터링의 흐름
- 중첩을 제거하여 보기 좋게 만든다.
- 의미 단위로 로직을 정리한다. -> 조건 확인과 값 대입 로직을 각각 분리해서 정리한다.
- 조건을 읽기 쉽게 한다. -> 논리 부정 연산자 !를 사용하는 것처럼 한번 더 생각하게 되는 요소가 있으면 메서드로 추출해서 읽기 쉽게 한다.
- 목적을 나타내는 메서드로 만들어서 사용한다. -> 보유 포인트가 부족한지 리턴하는 메서드 = isShotOfPoint
실수 줄이는 방법: 단위 테스트
- 단위 테스트는 작은 기능 단위로 동작을 검증하는 테스트를 의미하며, 일반적으로 ‘테스트 프레임워크와 테스트 코드를 활용해서 메서드 단위로 동작을 검증하는 방법’이라 한다.
  - (참고로, 이 책에서는 테스트 프레임워크로는 JUnit을 사용한다)
- ‘리팩터링을 할 때 단위 테스트는 필수다!’라는 말이 있을 정도로 리팩터링과 단위 테스트는 항상 세트이다.
테스트 코드를 사용한 리팩터링 흐름
1. 이상적인 구조의 클래스 기본 형태를 어느 정도 잡는다.
2. 이 기본 형태를 기반으로 테스트 코드를 작성한다.
3. 테스트를 실패시킨다.
4. 테스트를 성공시키기 위한 최소한의 코드를 작성한다.
5. 테스트가 성공할 수 있도록, 조금씩 로직을 이상적인 구조로 리팩터링한다.
리팩터링 시 주의 사항
- 기능 추가와 리팩터링을 동시에 하지 않는다.
  
  작업을 할 때는 ‘기능 추가(adding function)’와 ‘리팩터링(refactoring)’ 중에서 하나만 쓰고 있어야 한다. - 리팩터링 2판, 17.1.3절 -
  
  리포지토리에 커밋할 때 기능 추가와 리팩터링을 따로 구분해야 한다.
- 작은 단계(small step)로 실시하는 것이 좋다.
  
  리팩터링으로 메서드 이름 변경과 로직 이동을 했다면, 커밋을 따로따로 구분하는 것이 좋다. -> 커밋1: 메서드 이름 변경, 커밋2: 로직 이동
  
  여러 번 커밋했다면, 풀 리퀘스트(Pull Request) 를 작성하는 것이 좋다.
- 리팩터링 시 언어와 프레임워크의 특성을 고려한 설계와 적용 방법을 생각해 보는 것이 중요하다.
15장. 설계의 의의와 설계를 대하는 방법

어떤 설계를 주제로 집필했는가 : 유지 보수성
- 소프트웨어의 제품과 관련된 품질 특성은 다음과 같다.
  - 기능 적합성, 성능 효율성, 호환성, 사용성, 신뢰성, 보안, 유지 보수성, 이식성
- 설계는 ‘어떠한 문제를 효율적으로 해결하는 구조를 만드는 것’을 의미한다.
  
  그렇다면 소프트웨어에서 설계 란, ‘어떤 소프트웨어의 품질 특성을 향상시키기 위한 구조를 만드는 것’이라고 말할 수 있다.
- 이 책은 소프트웨어 개발에서 나타날 수 있는 악마를 퇴치하는 설계 방법을 설명했다.
  
  이러한 악마의 설징과 가장 관련 있는 품질 특성은 유지 보수성이다.
  
  유지 보수성은 시스템이 정상 운용되도록 유지 보수하기가 얼마나 쉬운가를 나타내는 정도를 말한다.
  
  유지 보수성 중에서도 특히 변경 용이성을 목적으로 하는 설계 방법을 다루어 온 것이다.
개발 생산성을 저하되는 요인
- 변경 용이성 설계를 하지 않으면, 개발 생산성이 저하되는데, 저하 요인으로는 크게 2가지가 있다.
  - 요인 1: 버그가 발생하기 쉬운 구조
  - 요인 2: 가독성이 낮은 구조
- 제대로 설계하지 않으면, 로직 변경과 디버그에 많은 시간을 소비하게 된다.
소프트웨어와 엔지니어의 성장 가능성
- 소프트웨어의 성장 가능성을 높이는 것이 바로 이 책의 핵심 주제이자 의의.
- ‘엔지니어’에게 ‘자산’이란 기술력이라고 생각함.
- 레커시 코드는 프로젝트 발전과, 고품질 설계 경험을 막는다. 또한 시간을 낭비하게 만든다.
  
  이러한 레거시 코드는 기술 향상을 막고, 엔지니어에게 정말 중요한 자산이라고 할 수 있는 기술력의 축적을 막는다.
문제 해결
- 문제는 항상 이상과 현실의 차이 때문에 발생한다.
  - 따라서 이상이 무엇인지 알고 있다면, 현실과 비교하며 차근차근 문제를 해결할 수 있다.
  - 이와 같이 설계에서도 이상적인 설계와 현재 설계를 비교하면, 기술 부채를 인식할 수 있다.
코드의 좋고 나쁨을 판단하는 지표
- 루비의 코드 분석 라이브러리 RuboCop에 따르면, 줄 수 상한이 메서드를 기준으로 10줄 이내이고, 클래스를 기준으로는 100줄 이내로 판단한다.
  - 줄 수가 너무 많으면, ‘메서드와 클래스 분할’을 검토하자.
  - 분할했으면, 분할한 클래스 하나하나가 일관되고 정상적인 동작을 하는 구조를 가져야 한다.
  - “클래스를 분할하면 읽기 어려워질까?” -> 클래스를 분할한 이후에, 클래스 하나하나가 정상적으로 동작하도록 설계하게 되면, 신뢰성이 높아져서 내부 로직에 대해 신경이 줄어들게 된다. -> 읽기가 더 쉬워지게 된다.
- 순환 복잡도는 코드의 구조적인 복잡함을 나타내는 지표이다.
  - 조건 분기, 반복 처리, 중첩이 많아지면 복잡도가 커진다.
  - 순환 복잡도가 10이하 -> 굉장히 좋은 구조이고 버그가 발생할 확률은 25%이하이다.
- 응집도는 모듈 내부에서 데이터와 로직이 관련되어 있는 정도를 나타내는 지표이다.
  - 클래스로 해석하면, 클래스 내부에서 데이터와 로직의 관계가 얼마나 강한지 나타내는 지표이다.
  - 응집도가 높을수록 변경 용이성이 높고 좋은 구조이다.
- 결합도는 모듈 간의 의존도를 나타내는 지표이다.
  - 클래스로 해석하면, 결합도는 ‘어떤 클래스가 호출하는 다른 클래스의 수’라고 볼 수 있다. (A라는 클래스가 B, C, D를 호출하고 있다라고 하면, 3개를 의존하게 된다)
  - 의존하고 있는 클래스가 많으면 많을수록, 즉 결합도가 높을수록 더 넓은 범위를 고려해야 하므로, 유지 보수와 사양 변경이 어렵다.
  - 결합도가 너무 높으면 단일 책임 원칙을 위배하므로, 의존을 더 줄일 수 없는지, 클래스를 더 적게 분할할 수 없는지 검토해봐야 한다.
16장. 설계를 방해하는 개발 프로세스와의 싸움

커뮤니케이션
- 커뮤니케이션이 부족하면 버그가 많아지는 경향이 있다.
- 콘웨이 법칙이란 ‘시스템의 구조는 그것을 설계하는 조직의 구조를 닮아 간다’는 접근 방법을 말한다.
  
  예를 들어 개발 부문이 3개의 팀으로 구분되어 있다면 모듈이 수도 팀의 수와 동일하게 3개로 구성되는 시스템이 만들어진다는 것이다.
  
  즉, 시스템의 구조가 릴리스 단위, 즉 팀 단위의 구조처럼 구성된다.
  
  반대로, 역콘웨이 법칙은 ‘소프트웨어의 구조를 먼저 설계하고, 이후 소프트웨어의 구조에 맞게 조직을 편성한다’는 접근 방법을 말한다.
- 팀원 간 관계 개선에는 심리적 안정성이 중요하다.
  
  심리적 안정성이란 어떤 발언을 했을 때, ‘부끄럽거나 거절당하지 않을 것이라는 심리 상태’, ‘안심하고 자유롭게 발언 또는 행동할 수 있는 상태’ 등으로 정의한다.
  
  성공적인 팀을 구축할 때 매우 중요한 개념이라고 알려져 있다.
설계
- ‘빨리 끝내고 싶다’는 심리로 인해 설계 품질을 저하되게 만드는데, 이는 바람직하지 않다.
  
  품질에 신경쓰지 않으면, 시간이 지날수록 구현 속도가 느려지게 된다. 나쁜 코드로 인한 구현 때문에 코드 수정이 다른 곳에 영향을 미치기 때문이다.
- TDD를 기반으로 클래스 설계와 구현 피드백 사이클을 돌리면서 설계 품질을 향상 시킨다.
- 한 번에 완벽하게 설계하지 않고 사이클을 돌려가며 완성한다. (한 번에 완벽하게 설계하려는 욕심 버리기!)
  
  피드백 사이클을 돌며 개발 할 때는 개발 방식에 대해 처음부터 확실하게 합의하고 시작하는 것이 좋다.
- 너무 빠른 최적화(premature optimization)는 지양하자. - 병목이 어디인지 모른 채 성능이 빠른 코드를 작성하려고 하는 것
  
  대부분의 경우에서 클래스 쪼개기가 성능에 미치는 영향이 전혀 없거나 거의 없다.
- 다수결로 설계 규칙을 만들지 말자.
  
  설계 규칙을 정할 때 시니어 엔지니어처럼 설계 역량이 뛰어난 팀원이 중심이 되어 규칙을 만드는 것이 좋다.
  
  다수결로 코드와 설계를 결정하려고 하면, 아무래도 수준이 낮은 쪽에 맞춰서 하향평준화되기 쉽기 때문이다.
  
  각각의 설계 규칙에는 이유와 의도를 함께 적는 것이 좋다. -> 아무런 의미를 갖지 않는 상황을 막기 때문
  
  팀의 설계 역량이 성숙하지 않으면, 개인에게 맡기지 말고, 설계를 어느 정도 아는 팀원이 설계 리뷰와 코드 리뷰를 하도록 해서, 설계 품질을 관리할 수 있게 한다.
  
  팀 구성원의 설계 역량이 어느 정도 성숙해지면, 다시 한번 설계 규칙에 대해 논의해보는 것도 좋다.
Read All
[JPA] 고급 매핑 (상속관계 매핑, BaseEntity)

2023-11-24

devFancy

JPA
- 상속관계 매핑
- @MappedSuperclass
  - 실제 예시
이 글은 [자바 ORM 표준 JPA 프로그래밍 - 기본편] 강의를 듣고 정리한 내용입니다.

상속관계 매핑
- 관계형 데이터베이스에는 상속 관계가 없다.
- 대신에 관계형 데이터베이스는 슈퍼타입 서브타입 관계라는 모델링 기법이 객체 상속과 유사하다.
- 왼쪽이 슈퍼타입 서브타입 논리 모델이고, 오른쪽이 객체 상속 모델이다.
- 상속관계 매핑이란 관계형 데이터베이스의 슈퍼타입 서브타입 논리 모델을 실제 물리 모델로 구현하는 방법을 말한다.
- 상속관계 매핑하는 방법에는 3가지 방법이 있다.
  - 조인 전략: 각각 테이블로 변환
  - 단일 테이블 전략: 통합 테이블로 변환
  - 구현 클래스마다 테이블 전략: 서브타입 테이블로 변환
주요 어노테이션
- @Inheritance(strategy=InheritanceType.XXX)
  - JOINED : 조인 전략 (InheritanceType.JOINED)
  - SINGLE_TABLE : 단일 테이블 전략 (InheritanceType.JOINED)
  - TABLE_PER_CLASS : 구현 클래스마다 테이블 전략 (InheritanceType.TABLE_PER_CLASS)
- @DiscriminatorColumn(name=“DTYPE”) : 부모에서 구분 컬럼을 지정할 때 사용한다. 기본값이 DTYPE이므로 name 속성은 생략 가능하나, 작성하는 것이 협업하기 있어서 좋다.
- @DiscriminatorValue(“XXX”) : 자식에서 구분 컬럼에 입력할 값을 지정할 때 사용한다. 기본값은 엔티티 이름이다.
- @PrimaryKeyJoinColumn(name = "Book_ID") : 기본 값으로 자식 테이블은 부모 테이블 id 컬럼명을 그대로 사용하나, 변경 시 해당 설정값을 추가해줘야 한다.
조인 전략
- 조인 전략은 엔티티마다 모두 테이블로 만들어주고 부모의 기본키를 기본키 + 외래키로 사용한다.
- 그래서 조회할 때 조인을 사용한다.
- 다만 객체는 타입이 있는데 테이블은 타입에 개념이 없어서 따로 컬럼을 추가해줘야 한다.
  - ex) @DiscriminatorColumn(name = "DTYPE")
```
// Item 엔티티
@Entity
@Inheritance(strategy = InheritanceType.JOINED)
@DiscriminatorColumn(name = "DTYPE")
public abstract class Item{
	@Id @GeneratedValue
	@Column(name = "ITEM_ID")
	private Long id;
	
	private String name;
	private int price;
	
	...
}

// Album 엔티티
@Entity
@DiscriminatorValue("A")
public class Album extends Item {
	private String artist;
	...
}

// Movie 엔티티
@Entity
@DiscriminatorValue("M")
public class Movie extends Item {
	private String director;
	private String actor;
	...
}

// Book 엔티티
@Entity
@DiscriminatorValue("B") 
public class Book extends Item {
    private String author;
    private String isbn;
}
...
```
- Item 엔티티에서 상속 매핑을 하기 위해서 @Inheritance 추가하고, 조인 전략을 사용하기 위해 InheritanceType.JOINED을 추가한다.
- 그리고 부모에서 구분 컬럼을 지정한다. -> @DiscriminatorColumn(name = "DTYPE")
- 자식들은 구분 컬럼을 어떻게 저장할지 작성한다.
  - Album 엔티티는 부모로부터 DTYPE에 A라는 값으로 저장된다. -> @DiscriminatorValue("A")
  - Movie 엔티티는 부모로부터 DTYPE에 M라는 값으로 저장된다.
  - Book 엔티티는 부모로부터 DTYPE에 B라는 값으로 저장된다.
- 자식 엔티티에는 Id가 없는데 부모 테이블에서 Id를 자식 테이블에서 그대로 사용한다.
  - 만약 자식 테이블 기본 컬럼명을 따로 설정하려면 @PrimaryKeyJoinColumn을 사용한다.
```
// Book 엔티티
@Entity
@DiscriminatorValue("B")
@PrimaryKeyJoinColumn(name = "BOOK_ID")
```
- 위처럼 Book 테이블에서 Id 컬럼명은 BOOK_ID(이전: ITEM_ID)로 된다.
조인 전략 장단점
- 장점
  - 테이블이 정규화가 된다.
  - 외래 키 참조 무결성 제약조건을 활용할 수 있다. -> 외래 키 참조로 ITEM_ID로 ITEM 테이블만 확인해도 된다.
    - 참조 무결성 제약조건이란 자식 릴레이션의 외래 키의 값은 참조된 부모 릴레이션의 기본 키 값과 같아야 하며, 자식 릴레이션의 값이 변경될 때 부모 릴레이션의 제약을 받는다는 조건을 말한다.
    - 외래 키는 NULL 값이거나 또는 부모 테이블의 기본 키 or 고유 키 값과 동일해야 한다.
  - 저장공간을 효율적으로 사용할 수 있다.
- 단점
  - 조회시 조인을 많이 사용해서 성능이 저하된다.
  - 조회 쿼리가 복잡하다.
  - 데이터 저장시 INSERT SQL을 2번 호출한다.
단일 테이블 전략
- 단일 테이블 전략은 말 그대로 테이블을 하나로 합치는 전략이다.
- 구분 컬럼(DTYPE)을 통해 어떤 자식 데이터가 저장되었는지 알 수 있다.
- 조인 전략과 형식은 비슷한데, 부모 테이블에 @Inheritance에 (strategy = InheritanceType.SINGLE_TABLE)을 지정한다.
- 또한 모든 테이블이 하나로 통합되어 있기 때문에 구분 컬럼은 필수다.
```
// Item 엔티티
@Entity
@Inheritance(strategy = InheritanceType.SINGLE_TABLE)
@DisciminatorColumn(name = "DTYPE")
...

// 자식 엔티티
@Entity
@DiscriminatorValue("A")
...

@Entity
@DiscriminatorValue("M")

@Entity
@DiscriminatorValue("B")
...
```
단일 테이블 전략 장단점
- 장점
  - 테이블이 하나이므로 조인이 필요없기 때문에 일반적으로 조회 성능이 빠르다.
  - 조회 쿼리가 단순하다.
- 단점
  - 자식들을 모두 하나의 테이블로 만들었기 때문에, 자식들마다 컬럼이 달라서 null 값이 많을 수 있다. -> null 값 허용 예) Album 엔티티에는 ACTOR 컬럼을 쓰지 않아 null 이다.
  - 단일 테이블에 모든 것이 저장되므로 테이블이 커질 수록 조회 성능이 오히려 느릴 수 있다.
구현 클래스마다 테이블 전략
- 구현 클래스마다 테이블 전략은 자식 테이블이 부모 테이블의 모든 것을 다 가지고 있는 형태이다. 그래서 자식 엔티티마다 테이블을 다 만들어준다.
- 이 전략은 데이터베이스 설계자와 ORM 전문자 둘다 추천하지 않는 전략이다.
```
// Item 엔티티
@Entity
@Inheritance(strategy = InheritanceType.TABLE_PER_CLASS)
...

// 자식 엔티티
@Entity
@DiscriminatorValue("A")
...

@Entity
@DiscriminatorValue("M")

@Entity
@DiscriminatorValue("B")
...
```
- 부모 테이블에 @Inheritance에 (strategy = InheritanceType.TABLE_PER_CLASS)을 지정한다.
구현 클래스마다 테이블 전략 장단점
- 장점
  - 서브 타입을 구분해서 처리할 때 효과적이다.
  - not null 제약조건을 사용할 수 있다. (각각의 테이블을 가지고 있기 때문)
- 단점
  - 여러 자식 테이블을 함께 조회할 때 성능이 느리다. (SQL에 UNION을 사용한다)
  - 자식 테이블을 통합해서 쿼리하기가 어렵다.
@MappedSuperclass
- 위에서는 부모-자식 클래스 모두 데이터베이스 테이블과 상속 관계로 매핑했는데, 여기선 다르다.
- 객체 입장에서 부모 클래스를 자식 클래스에게 매핑 정보만 제공하고 싶을때, @MappedSuperclass 를 사용한다.
- @Entity가 있는 클래스의 경우 실제 테이블과 매핑되지만, @MappedSuperclass를 사용한 클래스는 실제 테이블과 매핑되지 않고, 공통 매핑 정보가 필요할 때 사용할 목적으로만 사용된다.
- 아래 그림처럼 id, name과 같은 공통 매핑 정보가 필요할 때 BaseEntity 클래스를 만들어서 Member와 Seller로부터 상속받게 설계를 한다.
```
// BaseEntity
@MappedSuperclass
public abstract class BaseEntity{
	@Id @GeneratedValue
	private Long id;
	
	private String name;
	...
}

// Member 엔티티
@Entity
public class Member exteds BaseEntity{
	// ID, NAME 상속
	private String email;
	...
}

// Seller 엔티티
@Entity
public class Seller exteds BaseEntity{
	// ID, NAME 상속
	private String shopName;
	...
}
```
- @MappedSuperclass 특징을 정리하면 아래와 같다.
  - 상속관계 매핑이 아니다.
  - 그래서 엔티티도 아니고 테이블과 매핑하지도 않는다.
  - 부모 클래스를 상속 받은 자식 클래스에 매핑 정보만 제공해준다.
  - 직접 생성해서 사용할 일이 없기 때문에 추상 클래스로 사용하는 것을 권장한다.
  - 엔티티와 다르게 BaseEntity 추상 클래스에는 조회나 검색이 불가능하다.
- 정리하면, @MappedSuperclass는 테이블과 관계 없고, 단순히 엔티티가 공통으로 사용하는 매핑 정보를 모으는 역할이고,
  
  주로 등록일, 수정일, 등록자, 수정자와 같은 전체 엔티티에서 공통적으로 적용하는 정보를 모을 때 사용한다.
실제 예시

굿프렌즈 프로젝트에서 몇몇 테이블에 등록 시간과 수정 시간이 공통적으로 필요해서, @MappedSuperclass을 사용했다.
- 회원, 상품, 주문, 신고 테이블에 등록 시간과 수정 시간이 필요해서 BaseTimeEntity 추상 클래스를 만들어서 상속받도록 했다.
  
  프로필, 신고 테이블에는 등록 시간만 필요해서 BaseCreateTimeEntity 추상 클래스를 만들어서 상속받도록 했다.
- 굿프렌즈 프로젝트에서는 공통으로 쓰는 클래스를 global -> common 패키지에 넣어두었다.
  - 참고로 @EntityListeners(AuditingEntityListener.class)에 대한 부분은 나중에 다른 포스팅에서 설명할 에정이다.
BaseTimeEntity - 등록 시간, 수정 시간

```java package woorifisa.goodfriends.backend.global.common;
Read All

12/58

지금의 기록이 미래의 자산이 된다.

[solved.ac] Class3++ 11724. 연결 요소의 개수(DFS)

성능 요약

구분

Answer Code(2023.11.28)

문제풀이

Step0. 입력 및 초기화

Step1. graph에 연결 정보 채우기

Step2. dfs(재귀함수 호출)

Step3. 출력하기

Review

[Programmers] 후보키 (2019 카카오 블라인드)

성능 요약

구분

문제풀이

Answer Code(23.11.27)

Reference

[Programmers] [1차] 프렌즈4블록(2018 카카오 블라인드)

성능 요약

구분

Answer Code(23.11.27)

문제풀이

[내 코드가 그렇게 이상한가요?] 13 - 16장 정리

13장. 모델링: 클래스 설계의 토대

시스템, 모델, 모델링

모델링

기능성과 모델링의 관계

14장. 리팩터링

리팩터링의 흐름

실수 줄이는 방법: 단위 테스트

리팩터링 시 주의 사항

15장. 설계의 의의와 설계를 대하는 방법

어떤 설계를 주제로 집필했는가 : 유지 보수성

개발 생산성을 저하되는 요인

소프트웨어와 엔지니어의 성장 가능성

문제 해결

코드의 좋고 나쁨을 판단하는 지표

16장. 설계를 방해하는 개발 프로세스와의 싸움

커뮤니케이션

설계

[JPA] 고급 매핑 (상속관계 매핑, BaseEntity)

상속관계 매핑

주요 어노테이션

조인 전략

조인 전략 장단점

단일 테이블 전략

단일 테이블 전략 장단점

구현 클래스마다 테이블 전략

구현 클래스마다 테이블 전략 장단점

@MappedSuperclass

실제 예시