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

Today's records become tomorrow's assets.

[Programmers] 159993. 미로탈출 (BFS)

2023-12-16

devFancy

Algorithm

성능 요약
구분
Answer Code1(23.10.24)
Answer Code2(23.12.16)
- 문제 풀이(Answer Code1,2)
Review
Reference

문제 링크

성능 요약

메모리: 78.4 MB, 시간: 0.56 ms - 23.10.24
메모리: 82.6 MB, 시간: 0.35 ms - 23.12.16

구분

코딩테스트 연습 > 연습문제 > 미로탈출(BFS)

Answer Code1(23.10.24)

import java.util.*;

class Solution {

    static int[] dRow = {-1, 1, 0, 0}; // 행 기준 - 상,하,좌,우 (좌우로의 이동은 y좌표에 변화가 없으므로 0)
    static int[] dCol = {0, 0, -1, 1}; // 열 기준 - 상,하,좌,우 (상하로의 이동은 x좌표에 변화가 없으므로 0)
    static int[] lever = new int[2];

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

        // 탐색을 위한 2차원 배열과 방문 배열 초기화
        String[][] map = new String[maps.length][maps[0].length()];
        boolean[][] visited = new boolean[maps.length][maps[0].length()];
        int[] start = new int[2];

        // 2차원 배열을 만들며 최초 시작 위치 탐색
        for(int i = 0; i < maps.length; i++) {
            String[] temp = maps[i].split("");
            map[i] = temp;
            for(int j = 0; j < temp.length; j++) {
                if(temp[j].equals("S")) {
                    start[0] = i;
                    start[1] = j;
                }
            }
        }

        // 레버까지 BFS 탐색
        int first = bfs(map, visited, start, "L");
        if(first == -1) {
            return -1;
        }

        // 탈출지점까지 BFS 탐색
        visited = new boolean[maps.length][maps[0].length()];
        int second = bfs(map, visited, lever, "E");
        if(second == -1) {
            return -1;
        }

        answer = first + second;
        return answer;
    }

    public int bfs(String[][] map, boolean[][] visited, int[] start, String target) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start[0], start[1], 0}); // 현재 행, 현재 열, 이동 횟수
        visited[start[0]][start[1]] = true;

        while(!queue.isEmpty()) {
            int[] temp = queue.poll();
            int currentRow = temp[0];
            int currentCol = temp[1];
            int cnt = temp[2];

            for(int i = 0; i < 4; i++) {
                int newRow = currentRow + dRow[i];
                int newCol = currentCol + dCol[i];
                if(newRow >= 0 && newRow < map.length && newCol >= 0 && newCol < map[0].length) {
                    if(map[newRow][newCol].equals(target)) {
                        lever[0] = newRow;
                        lever[1] = newCol;
                        return cnt + 1;
                    }
                    if(!map[newRow][newCol].equals("X") && !visited[newRow][newCol]) {
                        visited[newRow][newCol] = true;
                        queue.add(new int[]{newRow, newCol, cnt + 1});
                    }
                }
            }
        }
        return -1;
    }
}

Answer Code2(23.12.16)

import java.util.*;
import java.io.*;
// 미로탈출
class Solution {
    static int[] dRow = {-1, 1, 0, 0};
    static int[] dCol = {0, 0, -1, 1};
    static int[] lever = new int[2];

    public int bfs(String[][] map, boolean[][] visited, int[] start, String target) {
        visited[start[0]][start[1]] = true;

        Queue<int[]> queue = new LinkedList<>();
        // 현재 행, 현재 열, 이동 횟수
        queue.add(new int[]{start[0], start[1], 0}); 

        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            int curRow = temp[0];
            int curCol = temp[1];
            int count = temp[2];

            for(int i = 0; i < 4; i++) {
                int nextRow = curRow + dRow[i];
                int nextCol = curCol + dCol[i];
                if(nextRow >= 0 && nextRow < map.length
                && nextCol >= 0 && nextCol < map[0].length) {
                    if(map[nextRow][nextCol].equals(target)) {
                        lever[0] = nextRow;
                        lever[1] = nextCol;
                        return count + 1;
                    }
                    if(!map[nextRow][nextCol].equals("X")
                    && visited[nextRow][nextCol] == false) {
                        visited[nextRow][nextCol] = true;
                        queue.add(new int[]{nextRow, nextCol, count + 1});
                    }
                }
            }
        }
        return -1;
    }

    public int solution(String[] maps) {
        // 0. 입력 및 초기화
        int answer = 0;
        
        String[][] map = new String[maps.length][maps[0].length()];
        boolean[][] visited = new boolean[maps.length][maps[0].length()];
        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[0].length(); j++) {
                visited[i][j] = false;
            }
        }
        int[] start = new int[2];

        // 1. 연결정보 채우기 - 2차원 배열을 만들며 최초 시작 위치 탐색 후 저장
        for(int i = 0; i < maps.length; i++) {
            String[] temp = maps[i].split("");
            map[i] = temp;
            for(int j = 0; j < temp.length; j++) {
                if(temp[j].equals("S")) {
                    start[0] = i;
                    start[1] = j;
                }
            }
        }

        // 2-1. 레버까지 BFS 탐색
        int first = bfs(map, visited, start, "L");
        if(first == -1) { // 만약 레버를 발견하지 못했다면 -1을 return
            return -1;
        }

        // 2-2. 탈출 지점까지 BFS 탐색
        visited = new boolean[maps.length][maps[0].length()];
        int second = bfs(map, visited, lever, "E");

        // 3. 출력하기
        if(second == -1 ) { // 만약 탈출할 수 없다면 -1을 return
            return -1;
        }
        answer = first + second;
        return answer;
    }
}

문제 풀이(Answer Code1,2)

문제 요약

벽으로 된 칸은 지나갈 수 X, 통로로 된 칸만 이동 가능

통로들 중 한 칸에는 미로를 빠져나가는 문이 있음 -> 이 문은 레버를 당겨서만 열 수 있음

레버가 있는 칸으로 이동 -> 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동

레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있음

결론은 주어진 미로에서 시작점(S)로 부터 레버(L)을 당기고 다시 탈출구(E)를 도달하는데 최단 거리를 구하는 문제다.

로직 구성

먼저 탈출을 하기 위해서는 레버까지 가야한다.

레버까지 BFS를 통해 최단거리 탐색을 진행한다.

레버에 도착하고 다시 한번 탈출지점까지 BFS 탐색을 한다.

탈출 조건이 (시작 지점에서 레버에 도달 && 레버에서 탈출 지점까지 도달) 할때의 최소 시간을 return 해주고,
이러한 조건이 만족하지 못하면 -1를 return 한다.

Review

23.12.16

GPT가 “일반적으로 BFS가 미로, 최단 경로 등을 찾는 데에 더 적합한 알고리즘이기 때문에 BFS를 선호합니다.” 라고 해서
- BFS로 다시 풀었는데, 레버까지 가는 것과 탈출지점까지 가는 것을 분리해서 접근해서 풀었다.
추가적으로 GPT에게 DFS와 BFS에 어떤 유형이 적합하는지 물어봤다.
- DFS는 주로 트리나 그래프에 사용해서 특정 경로를 탐색하는 경우 적합하고,
- BFS는 최단 경로를 찾거나 인접한 노드들을 탐색하는 경우에 적합하다고 답변했다.
지난 3주동안 DFS 기반으로 문제를 풀어서 BFS로 문제를 푸는 방식이 아직 서툴지만,

문제유형에 맞게 두가지 접근 방식을 계속적으로 사용해서 익숙해지자!

Reference

[프로그래머스] 연습문제 > 미로탈출

Read All

[Programmers] 1844. 게임 맵 최단거리(bfs)

2023-12-15

devFancy

Algorithm

성능 요약
구분
Answer Code1(2023.02.14)
- 문제 풀이(Answer Code1)
Answer Code2(23.11.08)
- 문제풀이 - Answer Code2
Review
Reference

문제 링크

성능 요약

메모리: 68.8 MB, 시간: 4.79 ms

구분

코딩테스트 연습 > 깊이／너비 우선 탐색（DFS／BFS）

Answer Code1(2023.02.14)

import java.util.*;

class Solution {
  public class position {
    int x;
    int y;

    public position(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }

  int[] nx = {-1, 1, 0, 0};
  int[] ny = {0, 0, -1, 1};
  public int solution(int[][] maps) {
    int h = maps.length;
    int w = maps[0].length;

    Queue<position> q = new LinkedList<>();
    q.add(new position(0,0));

    boolean[][] visited = new boolean[h][w];
    visited[0][0] = true;

    position p;
    while (!q.isEmpty()) {
      p = q.poll();
      int x = p.x;
      int y = p.y;

      for(int i=0; i<4; i++) {
        int next_x = x + nx[i];
        int next_y = y + ny[i];

        if (0 <= next_x && next_x < h && 0 <= next_y && next_y < w){
          if(visited[next_x][next_y] == false && maps[next_x][next_y] > 0) {
            visited[next_x][next_y] = true;
            maps[next_x][next_y] = maps[x][y] + 1;
            q.add(new position(next_x, next_y));
          }
        }
      }
    }
    return maps[h-1][w-1] == 1 ? -1 : maps[h-1][w-1];
  }
}

문제 풀이(Answer Code1)

최소의 길을 구하기 위해서는 BFS를 사용하는게 더 효율적이다. DFS는 깊게 탐색하는 탐색 알고리즘으로 잘못된 길을 탐색하다간 오히려 효율적이지 못할 수도 있다.
반면에 BFS는 너비를 탐색하는 알고리즘으로 주변부터 탐색하기 때문에 DFS보다는 최소의 길을 찾을 수 있다.
참고로, DFS는 Stack, 재귀함수를 이용하여 구현하며, BFS는 Queue를 이용하여 구현한다.
Queue는 데이터를 꺼낼 때마다 항상 첫 번째 지정된 데이터를 삭제하므로, 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다.

Answer Code2(23.11.08)

import java.util.*;

class Solution {
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    
    public int solution(int[][] maps) {
        int answer = 0;
        // 행의 길이, 열의 길이
        int[][] visited = new int[maps.length][maps[0].length];
        visited[0][0] = 1; // 시작 위치 방문체크
        
        // bfs 탐색
        bfs(maps, visited);
        
        // 도착지 값을 넣어주기
				// 배열의 인덱스는 0부터 시작하므로, 도착 위치(n-1, m-1)이 된다.
        answer = visited[maps.length -1][maps[0].length -1];
        
        // 갈 수 없다면 -1 리턴
        if (answer == 0) {
            answer = -1;
        }
        return answer;
    }
    public void bfs(int[][] maps, int[][] visited) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0,0});
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            int x = now[0];
            int y = now[1];
            
            // 4방 탐색
            for(int i = 0; i < 4; i++) {
                // 이동했을 때 위치
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 범위 벗어나는지 체크
                // 방문했는지 체크
                // 갈 수 있는 곳인지 체크
                if(nx >= 0 && nx < maps.length && ny >= 0 && ny < maps[0].length && visited[nx][ny] == 0 && maps[nx][ny] == 1) {
                    // 방문했다고 체크해주기
                    visited[nx][ny] = visited[x][y] + 1;
                    // 큐에 넣기
                    q.add(new int[]{nx, ny});
                } 
            }
        }
    }
}

문제풀이 - Answer Code2

풀이 접근 방법

4방 탐색을 위한 dx, dy 배열을 만들어준다.
방문 체크를 위한 배열을 만들어준다.
시작 위치를 1로 만들어 방문 체크를 해준다.
bfs 탐색을 한다.
범위를 벗어나는지, 방문 했는지, 갈수 있는 곳인지를 체크한다.
체크해서 문제가 없다면 해당 위치까지 방문한 수 + 1을 넣어준다.
bfs를 추가적으로 탐색한다.
결과를 answer에 넣는다.
answer가 0이라면 도착할 수 없는 곳이므로 -1로 넣어준다.
결과를 출력한다.

visited[nx][ny] = visited[x][y] + 1;: 여기서 nx, ny는 현재 위치에서 이동한 새로운 위치를 나타냅니다. visited[x][y]는 현재 위치까지의 이동 횟수를 나타내고, 여기에 1을 더해 visited[nx][ny]에 저장한다. 이렇게 하면 새로운 위치까지의 이동 횟수가 기존 위치보다 1 더 많아지게 된다.

예를 들어, 현재 위치에서 (nx, ny)로 이동했을 때, 이동 횟수가 3이었다면, visited[nx][ny]에는 4가 저장된다.
q.add(new int[]{nx, ny});: 새로운 위치 (nx, ny)를 큐에 추가합니다. 이렇게 하면 다음에 이 위치를 기준으로 탐색이 이어지게 된다.

이 두 단계를 통해, BFS 알고리즘이 현재 위치에서 갈 수 있는 모든 이동 가능한 위치를 탐색하고, 그 위치들을 큐에 추가하여 계속해서 탐색을 진행합니다. 이 과정을 통해 최단거리를 찾게 된다.

Review

BFS 개념은 알았지만 구현 방식에 있어서 알고리즘이 어떻게 짤지 구체적으로 떠오르지 못했다.
두번째로 할 때가 첫번째보다 이해가 더 쉬웠다.
다음에는 바로 생각날 수 있도록 + 접근 방식대로 풀어보도록 하자!

23.12.04

항상 dfs로만 풀어왔어서 bfs로 푸는 방법이 기억이 나질 않아, 결국 이전 풀이를 참고하게 되었다.
해당 풀이 방식보다 조금 더 나은게 있을 거 같은데, 생각나면 업데이트를 해보자!

Reference

https://blackvill.tistory.com/177 - Answer Code2

Read All

[JPA] 값 타입

2023-12-15

devFancy

JPA
이 글은 [자바 ORM 표준 JPA 프로그래밍 - 기본편] 강의를 듣고 정리한 내용입니다.

기본값 타입
- 엔티티 타입
  - @Entity 로 정의하는 객체이다.
  - 데이터가 변해도 식별자로 지속해서 추적이 가능하다.
  - ex) 회원 엔티티의 키나 나이 값을 변경해도 식별자로 인식이 가능하다.
- 값 타입
  - int, Integer, String 처럼 단순히 값으로 사용하는 자바 기본 타입이나 객체이다.
  - 식별자가 없고 값만 있으므로 변경시 추적 불가능하다
  - ex) 게시판의 내용(content)
값 타입 분류
- 기본 값
  - 자바 기본 타입(int, double)
  - 래퍼 클래스(Integer, Long)
  - String
```
// 기본 값 타입 - 예시) - id, userName
@Entity
public class Member {

    @Id
    @GeneratedValue
    @Column(name = "member_id")
    private Long id;

    private String userName;
}
```
- 임베디드 타입(Embedded type, 복합 값 타입) - ex) 우편번호
- 컬렉션 값 타입(Collection value type)
임베디드 타입
- 임베디드 타입는 복합 값 타입으로 새로운 값 타입을 직접 정의할 수 있다.
- 주로 기본 값 타입을 모아서 만들어 복합 값 타입이라고도 한다.
- 임베디드 타입 역시 직접 정의를 할 뿐, int, String과 같은 타입으로 이루어진다.
- 예를 들어, 회원 엔티티에 이름, 근무기간, 집 주소를 가질 때 -> 아래와 같이 Address 클래스 임베디드 타입으로 바꿀 수 있다.
- 임베디드 타입을 사용하려면 값 타입을 정의하는 곳(Address)에 기본 생성자를 필수로 생성해야 한다.
임베디드 타입 사용법
- @Embeddable : 값 타입을 정의하는 곳에 표시한다. -> Address 클래스
- @Eembedded : 값 타입을 사용하는 곳에 표시한다. -> Member 클래스 안에 Address 객체를 필드로 선언한 뒤, 그 위에 표시해준다.
임베디드 타입의 장점
- 재사용성과 높은 응집도
- 임베디드 타입을 포함한 모든 값 타입은, 값 타임을 소유한 엔티티에 생명주기를 의존한다.
임베디드 타입과 테이블 매핑
- 임베디드 타입은 엔티티의 값일 뿐이다. 그래서 임베디드 타입을 사용하기 전과 후에 매핑하는 테이블은 같다.
- 객체와 테이블을 아주 세밀하게 매핑하는 것이 가능하다.
- 잘 설계한 ORM 애플리케이션은 매핑한 테이블의 수보다 클래스의 수가 더 많다.
@AttributeOverride: 속성 재정의
- 한 엔티티에서 같은 값 타입을 사용하면 컬럼명이 중복될때, @AttributeOverrides, @AttributeOverride를 사용해서 컬러명 속성을 재정의한다.
- 아래 그림과 같이 주소라는 컬럼명을 재정의하기 위해 workAddress 변수를 만들고, 그 위에 @AttributeOverrides, @AttributeOverride을 사용했다.
값 타입과 불변 객체
- 값 타입 공유 참조 - 임베디드 타입 같은 값 타입을 여러 엔티티에서 공유하면 위험함 → 부작용이 발생할 수 있다.
- 따라서 부작용을 피하기 위해서는 값 타입을 복사해준다.
  - 값 타입의 실제 인스턴스인 값을 공유하는 것은 위험하다.
  - 대신 값(인스턴스)를 복사해서 사용한다.
값 타입의 한계
- 항상 값을 복사해서 사용하면 공유 참조로 인해 발생하는 부작용을 피할 수 있지만, 문제는 임베디드 타입처럼 직접 정의한 값 타입은 자바의 기본 타입이 아니라 객체 타입이다.
- 객체 타입을 수정할 수 없게 만들기 위해서는 값 타입을 불변 객체로 설계해야 한다.
  - 불변 객체: 생성 시점 이후에 절대 값을 변경할 수 없는 객체를 말한다.
- 불변 객체로 설계하기 위해서는 생성자로만 값을 설정하고, 수정자(Setter)를 만들지 않으면 된다.
- 참고로, Integer, String은 자바가 제공하는 대표적인 불변 객체이다.
- 불변이라는 작은 제약으로 부작용이라는 큰 재양을 막을 수 있다.
값 타입의 비교
- 값 타입을 비교할 때 동일성 비교(==) 보다는 동등성 비교(equals)을 이용하여 비교한다.
- 동일성(identity) 비교: 인스턴스의 참조 값을 비교해서, ==을 사용한다.
- 동등성(equivalence) 비교: 인스턴스의 값을 비교해서, equals()을 사용한다.
- 동등성 비교(equals())을 사용하기 위해서는 해당 메서드를 적절하게 재정의 해줘야 한다.
- 해당 체크를 통해 필드에 직접 접근이 아닌 getter를 통해서 동등성을 비교하도록 한다. 그래야 프록시 객체에 접근할 수 있도록 하여 비교가 가능해진다.
값 타입 컬렉션
- 값 타입을 하나 이상 저장할 때에는 값 타입 컬렉션을 사용한다. 그래서 컬렉션의 경우 1대다 관계로 되어있다.
- 테이블로 보면 아래와 같이 favoriteFoods, addressHistory와 같이 되어있다.
- 값 타입을 하나 이상 저장할 때, @ElementCollection, @CollectionTable 을 사용한다.
- @ElementCollection 어노테이션을 사용하여 값 타입 컬렉션을 지정하고(fetch 전략 기본이 지연 로딩(LAZY)임), @CollectionTable 어노테이션을 통해 값 타입 컬렉션이 사용할 테이블을 지정해준다.
값 타입 컬렉션의 제약사항
- 하지만 값 타입 컬렉션은 다음과 같은 제약사항이 있다.
  - 값 타입은 엔티티와 다르게 식별자 개념이 없고, 값을 변경하면 추적이 어렵다.
  - 값 타입 컬렉션에 변경 사항이 발생하면 주인 엔티티와 연관된 모든 데이터를 삭제하고, 값 타입 컬렉션에 있는 현재 값을 모두 저장하게 된다.
  - 그리고 값 타입 컬렉션을 매핑하는 테이블은 모든 컬럼을 묶어서 기본 키를 구성해야 한다. -> null 입력X, 중복 저장X
- 따라서 값 타입 컬렉션을 사용하는 걸 추천하지는 않는다.
값 타입 컬렉션의 대안
- 대신, 값 타입 컬렉션의 대안으로 실무에서는 상황에 따라 값 타입 컬렉션 대신에 일대다 관계를 고려한다.
- 일대다 관계를 위한 엔티티를 만들고 여기에서 값 타입을 사용한다.
- 영속성 전이(Cascade) + 고아 객체 제거(orphan remove) 를 사용해서 값 타입 컬렉션 처럼 사용하는 방법이 있다. ⇒ ex) AddressEntity
- 아래와 같이 AddressEntity 라는 엔티티 테이블을 만들고, Member 테이블과 연관관계를 맺어준다.
- 값 타입 컬렉션은 select box 처럼 멀티로 체크하는 등 단순한 경우에만 사용하는 것을 권장한다.
엔티티 타입과 값 타입의 특징
- 엔티티 타입의 경우 식별자가 있고, 생명 주기를 관리하며, 공유가 된다.
- 값 타입의 경우 식별자가 없고, 생명 주기를 엔티티에 의존하고 공유하지 않는 것이 안전하다. -> 복사해서 사용하거나 불변 객체로 만드는 것이 안전하다.
=> 정리하면, 식별자가 필요하고, 지속해서 값을 추적, 변경해야 한다면 그것은 값 타입이 아닌 엔티티를 사용하는 걸 권장한다.

Reference
- 자바 ORM 표준 JPA 프로그래밍 - 기본편
Read All
[JPA] 프록시와 연관관계 관리

2023-12-15

devFancy

JPA
이 글은 [자바 ORM 표준 JPA 프로그래밍 - 기본편] 강의를 듣고 정리한 내용입니다.

프록시
- JPA에서 프록시는 실제 엔티티 객체를 대신하여 데이터베이스 조회를 지연할 수 있는 가짜 객체를 의미한다.
- 가짜 객체라 해서 실제 엔티티의 동작을 수행하지 못하는 것은 아니다.
  - 실제 엔티티 클래스로부터 상속받아 생성하기 때문에, 실제 클래스와 겉 모양은 같으므로 (이론상) 사용하는 입장에서는 구분하기 않고 사용하면 된다.
em.find() vs em.getReference
- em.find() 는 데이터베이스를 통해 실제 엔티티 객체를 조회하는 메서드이다.
- em.getReference()는 데이터베이스 조회를 지연하는 가짜 객체(프록시)를 조회한다. -> DB에 쿼리가 안나가는데 조회가 된다.
  - 실제 엔티티 클래스로부터 상속받지만, 내부는 null 값을 가지고 있다.
  - 하이버네이트가 내부의 라이브러리를 써서 프록시라는 가짜 엔티티를 주게 된다.
- 프록시 객체는 실제 객체의 참조(target)를 보관한다.
- 프록시 객체를 호출하면, 프록시 객체는 실제 객체의 메서드를 호출한다.
프록시 객체의 초기화
- 위의 그림을 통해 프록시 객체의 초기화하는 과정은 다음과 같다.
1. getName() 메서드를 호출하면 처음에 Member target에 값이 없다. (만약 1차 캐시가 존재한다면 프록시 객체가 아닌 실제 객체를 반환한다)
2. 그래서 JPA가 영속성 컨텍스트에 진짜 Member 객체를 가져오기 위해 초기화를 요청한다.
3. 영속성 컨텍스트에는 DB를 조회한다.
4. 그런 다음 실제 엔티티 객체를 생성해서 Member 엔티티에 넘겨준다.
5. 그리고 MemberProxy에 있는 Member target을 실제 Member 엔티티(진짜 객체)와 연결시켜준다.
- 정리하면 getName()을 영속성 컨텍스트를 총해 초기화 요청 및 DB에서 조회한 다음, 가짜 객체를 실제 객체와 연결시켜서 값을 받아온다.
코드로 확인하면 아래와 같다.
```
public class JpaMain {

    public static void main(String[] args) {
        EntityManagerFactory emf = Persistence.createEntityManagerFactory("hello");
        EntityManager em = emf.createEntityManager();
        EntityTransaction tx = em.getTransaction();

        tx.begin();

        try {
            Member member = new Member();
            member.setName("woochang");
            em.persist(member);

            em.flush();
            em.clear();

            // 실제 엔티티를 조회하는 경우
            Member findMember = em.find(Member.class, member.getId());
            // 프록시를 사용하는 경우
            Member findMember = em.getReference(Member.class, member.getId());
            System.out.println(findMember.getClass().getName());

            tx.commit();
        } catch (Exception e) {
            tx.rollback();
        } finally {
            em.close();
        }

        emf.close();
    }

}
```
- EntityManager의 getReference() 메서드를 통해 프록시 객체를 가져온다.
- 실행 결과로 package명.Member$HibernateProxy$chd0xZ3 이라는 형태로 출력하게 되는데, 이를 통해 프록시 객체임을 확인할 수 있다.
- 프록시 객체는 메서드 호출(getName()) 과 같이 실제 사용될 때 데이터베이스를 조회해서 실제 엔티티 객체를 생성 후 해당 객체를 참조로 가지게 된다.
- 이를 프록시 객체의 초기화 라고 한다.
프록시의 특징
- 프록시 객체는 처음 사용할 때 한 번만 초기화한다.
- 프록시 객체를 초기화 할 때, 프록시 객체가 실제 엔티티로 바뀌는 것은 아니다.
  - 초기화되면 프록시 객체를 통해서 실제 엔티티에 접근이 가능한 것이다. -> 교체되는게 아니라 프록시는 유지되고 내부에 값이 채워진 것이다.
- 프록시 객체는 원본 엔티티를 상속받는다. 따라서 타입 체크시 주의해야 한다. -> == 로 비교하는 대신, instanceof로 사용해야 한다)
```
class ProxyEx {
    private static void logic(Member m1, Member m2) {
        System.out.println("m1 == m2: " + (m1 instanceof Member)); // true
        System.out.println("m1 == m2: " + (m2 instanceof Member)); // true
    }
}
```
- 영속성 컨텍스트에 찾는 엔티티가 이미 있으면(1차 캐시), em.getReference()를 호출해도 실제 엔티티를 반환된다.
  - JPA에서는 같은 트랜잭션 안에서 영속 엔티티의 동일성을 보장한다.
- 초기화는 영속성 컨텍스트의 도움을 받아야 하기에 준영속 상태의 프록시를 초기화하면 문제가 발생한다.
프록시 확인

해당 객체가 프록시인지 확인하는 방법은 다음과 같다.
- PersistenceUnitUtil.isLoaded(Object entity) : 프록시 인스턴스의 초기화 여부 확인
- entity.getClass().getName() : 프록시 클래스 확인하는 방법
- org.hibernate.Hibernate.initialize(entity); : 프록시 강제 초기화 (JPA 표준은 강제하는 초기화가 없다)
즉시 로딩과 지연 로딩

즉시 로딩
- 즉시로딩은 엔티티를 조회할 때 연관관계가 있는 실제 엔티티도 함께 조회하는 방법이다.
- 즉시 로딩을 사용하기 위해서는 fetch 속성을 FetchType.EAGER 으로 지정하면 된다.
```
@Entity
public class Member {
    // ...
    @ManyToOne(fetch = FetchType.EAGER) // 즉시 로딩
    @JoinColumn(name = "TEAM_ID")
    private Team team;
    // ...
}
```
- 즉시 로딩을 사용하면, JPA 구현체가 가능하면 조인을 사용해서 SQL에서 한번에 함께 조회하게 된다.
  - 이때 외부 조인(left outer join) 을 사용하는 것을 확인할 수 있는데, 이는 Null 가능성 때문이다.
  - 내부 조인이 외부 조인보다 좋은 이유는 성능이 좋기에 최적화에 유리하지만, 이때 외래키에 NOT NULL 제약조건이 필요하다.
```
@Entity
public class Member {
    // ...
    @ManyToOne(fetch = FetchType.EAGER) // 즉시 로딩
    @JoinColumn(name = "TEAM_ID", nullable = false)
    private Team team;
    // ...
}
```
지연 로딩
- 지연 로딩 은 연관된 엔티티를 실제 사용할 때 조회하는 방법이다.
- 지연 로딩을 사용하기 위해서는 fetch 속성을 FetchType.LAZY 으로 지정하면 된다.
- 지연 로딩을 사용하게 되는 경우 실제 엔티티 객체 대신 앞에서 설명한 프록시 객체가 들어가게 된다.
- 아래에서 team이라는 연관된 엔티티를 실제 사용할 때 (ex. team.getName()), 그 시점에 초기화, 즉 DB 조회가 이루어진다는 의미이다.
```
@Entity
public class Member {
    // ...
    @ManyToOne(fetch = FetchType.LAZY) // 지연로딩
    @JoinColumn(name = "TEAM_ID")
    private Team team;
    // ...
}
```
- 지연 로딩은 연관된 엔티티(team)를 사용할 때에만 프록시 객체를 통해 조회하는 반면, 즉시 로딩은 연관된 엔티티를 사용하지 않더라도 실제 객체를 통해 함께 조회가 된다.
- Member에만 조회하는 경우가 많으면 지연 로딩을 사용하고, Member와 Team을 같이 사용하면 즉시 로딩을 사용하는 걸 권장한다.
프록시와 즉시로딩 주의
- 실무에서는 가급적 지연 로딩만 사용한다.
  - 즉시 로딩을 적용하면 예상하지 못한 SQL이 발생한다.
  - 즉시 로딩은 JPQL에서 N+1 문제를 일으킨다. -> select로 Member만 가져오는 SQL을 작성했지만, 해당 SQL의 개수만큼 필요하지도 않은 Team select SQL가 발생하게 될 수도 있다.
- 로딩 전략 - 테이블이 복잡하게 얽혀있는 경우에는 지연 로딩을 사용하는 것을 권장한다.
  - @ManyToOne, @OneToOne은 기본이 즉시 로딩 -> 실무에서 지연 로딩으로 바꾸고 진행한다.
  - @OneToMany, @ManyToMany는 기본이 지연 로딩
예시 - 지연 로딩 활용
- Member와 Team(다대일)은 자주 함께 사용 -> 즉시 로딩
- Member와 Order(일대다)는 가끔 사용 -> 지연 로딩
- Order와 Product(다대일)는 자주 함께 사용 -> 즉시 로딩
영속성 전이: CASCADE

참고로 영속성 전이는 위에서 다룬 프록시 객체와 로딩 전략과 연관이 없는 개념이다)
- 영속성 전이란 특정 엔티티를 영속 상태로 만들 때, 연관된 엔티티도 함께 영속 상태로 만들고 싶을 때 사용한다.
- 예를 들어 아래 그림처럼 부모 엔티티를 저장할 때 자식 엔티티도 함께 저장하는 경우에 사용한다.
코드로 적용하면 아래와 같다.

```java @Getter @Entity public class Parent {
```
@Id @GeneratedValue
@Column(name = "PARENT_ID")
private Long id;

private String name;
```
Read All

[Programmers] 43162. 네트워크(DFS)

2023-12-14

devFancy

Algorithm

성능 요약
구분
Answer Code1(23.11.08)
- 문제풀이(Answer Code1)
Answer Code2(23.12.14)
Review(23.12.14)
Reference

문제 링크

성능 요약

메모리: 71.4 MB, 시간: 0.10 ms

구분

코딩테스트 연습 > 깊이/너비 우선 탐색 > 네트워크

Answer Code1(23.11.08)

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[computers.length];

        // 노드 방문 초기화
        for (boolean visit : visited) {
            visit = false;
        }

        for(int i = 0; i < computers.length; i++) {
            if(visited[i] == false) { // 해당 노드를 방문하지 않았을 경우
                answer++; // 새로운 네트워크 찾았으므로 +1 증가
                dfs(i, visited, computers);
            }
        }

        return answer;
    }
    // node: 현재 노드, visited: 방문여부, computers: 컴퓨터간의 연결 정보를 나타내는 2차원 배열
    public void dfs(int node, boolean[] visited, int[][] computers) {
        visited[node] = true;

        for(int i = 0; i < computers.length; i++) {
            // 아직 방문하지 않는 노드 && 현재 노드와 연결된 경우
            if(visited[i] == false & computers[node][i] == 1) {
                dfs(i, visited, computers);
            }
        }
    }
}

문제풀이(Answer Code1)

DFS에 대한 알고리즘 개념을 안 상태로 해당 문제에 접근하면,

(1) 처음에 노드 방문을 boolean 배열을 만들어서 컴퓨터의 개수(n)만큼 for문을 돌려서 초기화해주고,

(2) visited[i] 값이 false이면 깊이 우선 탐색(dfs) 메서드를 호출하고 answer++ 해준다.

(3) 전달받은 파라미터인 visited[i] 값을 true로 바꿔준다.

(4) computers[] 길이만큼 반복문들 돌면서

(5) 아래 조건을 모두 만족하면 재귀 호출을 한다.

자기 자신이 아니며 (i != j)
visited 배열 i의 위치 값이 false이며
computers 배열의 값이 1인 것

(6) 2번으로 돌아간다.

(7) answer을 리턴한다.

Answer Code2(23.12.14)

// 프로그래머스 - 네트워크
class Solution {
    static boolean[] visited;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[computers.length];

        // 노드 방문 초기화
        for(boolean visit : visited) {
            visit = false;
        }

        for(int i = 0; i < computers.length; i++) {
            if(visited[i] == false) {
                answer ++;
                dfs(i, computers);
            }
        }

        return answer;
    }

    /*
     * node: 현재 노드
     * visited: 방문여부
     * computer: 컴퓨터간의 연결 정보를 나타내는 2차원 배열
     */
    public void dfs(int node, int[][] computers) {
        visited[node] = true;

        for(int i = 0; i < computers.length; i++) {
            if(visited[i] == false && computers[node][i] == 1) {
                dfs(i, computers);
            }
        }
    }
}

Review(23.12.14)

첫번째 풀이와 다른 점은 visited 배열을 static으로 선언해서 dfs를 호출할 때, visited 매개변수를 없애주었다.
해당 문제는 연결된 요소 찾기 유형과 흡사해서, 이전에 풀었던 문제와 비슷했지만, 아직은 익숙치 않아서 더 자주 풀어봐야겠다.

Reference

https://beaniejoy.tistory.com/41

Read All

8/58

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

[Programmers] 159993. 미로탈출 (BFS)

성능 요약

구분

Answer Code1(23.10.24)

Answer Code2(23.12.16)

문제 풀이(Answer Code1,2)

Review

Reference

[Programmers] 1844. 게임 맵 최단거리(bfs)

성능 요약

구분

Answer Code1(2023.02.14)

문제 풀이(Answer Code1)

Answer Code2(23.11.08)

문제풀이 - Answer Code2

Review

Reference

[JPA] 값 타입

기본값 타입

임베디드 타입

임베디드 타입 사용법

임베디드 타입의 장점

임베디드 타입과 테이블 매핑

@AttributeOverride: 속성 재정의

값 타입과 불변 객체

값 타입의 비교

값 타입 컬렉션

값 타입 컬렉션의 제약사항

값 타입 컬렉션의 대안

Reference

[JPA] 프록시와 연관관계 관리

프록시

프록시 객체의 초기화

프록시의 특징

프록시 확인

즉시 로딩과 지연 로딩

즉시 로딩

지연 로딩

프록시와 즉시로딩 주의

영속성 전이: CASCADE

[Programmers] 43162. 네트워크(DFS)

성능 요약

구분

Answer Code1(23.11.08)

문제풀이(Answer Code1)

Answer Code2(23.12.14)

Review(23.12.14)

Reference