기억하고싶은것들

JPA ( Java Persistence API )

- 자바 ORM 기술에 대한 API 표준 명세

- 자바 애플리케이션에서 관계형 데이터베이스를 사용하는 방식을 정의한 인터페이스

ORM ( Object Relational Mapping )

- 객체와 관계형 데이터베이스를 매핑하는 기술

  ( DB Data --- Mapping --- Object ) 

- 비교되는 개념으로는 SQL Mapper가 있다

  ( SQL --- Mapping --- Object )

이 각각의 개념을 머리속에 생각해보면, 

자바에서 ORM기술을 사용하여 애플리케이션을 짜고 싶으면, 그의 표준인 JPA를 사용하여 작성해야 한다. 

( ORM을 사용하기 위해서는 표준인 JPA가 있지만, SQL Mapper를 사용하기 위해서는 표준이라고 딱히 정의된 부분은 없는 것 같다. 그냥 SQL를 통해 실행된 DB Data를 애플리케이션 레벨에 맞는 객체로 전환한다고 생각하면 될 것 같다.) 

위에서 말한것 처럼, JPA는 기술 명세이다.

어떻게 사용할지 가이드만 제공한 것이지, 실제 구현체가 아니다.

단순 인터페이스이다. 

그렇다면, 왜 JPA라는 표준까지 정해 놓으면서, ORM을 사용하려 하는 것인가

- DBMS에 대한 종속성을 줄일 수 있다.

- 객체 지향적인 코드로 더 직관적이고 비즈니스 로직에 더 집중할 수 있다.

더 나아가 JPA 기술 명세의 구현체인 ORM 프레임워크를 사용하면

개발자가 직접 query를 작성하지 않고, 메서드 호출로 원하는 데이터를 조회할 수 있고, 애플리케이션 레벨의 객체로 전환도 해주는 편리함을 누릴 수 있다. 

( ex : Hibernate ) 

Given the root of a binary tree, return the sum of values of its deepest leaves.

binary tree의 root 값이 주어진 상황에서, 가장 끝에 있는 잎들의 합을 반환해라.

dfs를 이용해서 답을 구해 보자. 

dfs를 타고 갈 때마다 level의 값을 하나씩 더해주어 해당 노드의 level을 파악하고

해당 level이 maxLevel보다 큰 경우에는 maxLevel값으로 세팅해 주면서 해결해 나갈 수 있을 것으로 보인다. 

    private void dfs(TreeNode node, int level) {

        if (level  > maxLevel) {
            sum = 0;
            maxLevel = level;
        }

        if (level == maxLevel) {
            sum += node.val;
        }

        if (node.right != null) {
            dfs(node.right, level+1);            
        }

        if (node.left != null) {
            dfs(node.left, level+1);
        }
    }

해당 메서드를 호출하는 내역을 보자

sum, maxLevel은 전역 변수를 사용하였다.

    int sum = 0;
    int maxLevel = 0;

    public int deepestLeavesSum(TreeNode root) {
        int level = 0;

        if (root != null) {
            dfs (root, level);
        }

        return sum;    
    }

문제 출처 

leetcode.com/problems/deepest-leaves-sum/

Given a binary tree, return the sum of values of nodes with even-valued grandparent. 

(A grandparent of a node is the parent of its parent, if it exists.)

If there are no nodes with an even-valued grandparent, return 0.

binary tree가 주어지고, 부모의 부모 ( grand parent) (할아버지)의 value가  짝수인 node의 value합을 구해라 

만약, 부모의 부모의 값이 짝수인 노드가 없다면 0을 반환해라

dfs를 이용하여 해답을 구해보자.

dfs메서드를 호출할때, 해당 노드의 부모와 부모의 부모를 파라미터로 전달하면 특정 노드에서 해당 부모의 부모의 value를 조회할 수 있다. 

    private void dfs(TreeNode node, TreeNode parent, TreeNode grandParent) {
        
        if (grandParent != null && grandParent.val % 2 == 0) {
            rst += node.val;
        }

        if (node.left != null) {
            dfs (node.left, node, parent);
        }

        if (node.right != null) {
            dfs (node.right, node, parent);
        }
    }

해당 메서드를 호출하는 내역을 보자

전역 변수를 사용하여 해결하는 방법이다.

    static int rst = 0;
    public int sumEvenGrandparent(TreeNode root) {
        if (root != null) {
            dfs (root, null, null);
        }
        return rst;
    }

만약, 전역 변수를 사용하지 않고 메서드에서 result를 반환하고 싶은 경우에는 아래와 같이 하면 해결 가능하다.

( 위의 방법과 거의 동일하다. 메서드의 반환타입만 추가되고 해당 값을 반환해주면 된다.)

    public int sumEvenGrandparent(TreeNode root) {
        int rst = 0;
        if (root != null) {
            rst = dfs (root, null, null);
        }
        return rst;
    }
    private int dfs(TreeNode node, TreeNode parent, TreeNode grandParent) {
        
        int rst = 0;
        if (grandParent != null && grandParent.val % 2 == 0) {
            rst += node.val;
        }

        if (node.left != null) {
            rst += dfs (node.left, node, parent);
        }

        if (node.right != null) {
            rst += dfs (node.right, node, parent);
        }

        return rst;
    }    

Flood Fill 알고리즘에 대한 정의를 찾아보면 보통 아래와 같이 나온다.

주어진 시작점으로부터 연결된 영역들을 찾는 알고리즘 
다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘

주변에서 해당 알고리즘을 사용하는 케이스는 보통 아래와 같다

• 그림판 프로그램의 "채우기" 기능 - 해당 영역의 주변에 모든 셀을 같은 색으로 색칠
• 지뢰 찾기 프로그램 - 특정 셀을 클릭 시 주변에 지뢰가 없는 모든 셀을 찾아 줌

Flood Fill 알고리즘은 보통 DFS 알고리즘을 이용하여 재귀 함수를 통해 구현하거나

BFS 알고리즘을 이용하여 Queue를 이용하여 구현한다.

이번에는 2차원 배열에서 DFS를 사용하여 Flood Fill 관련 알고리즘 문제를 푸는 예제를 하나 보도록 하겠다. 

DFS는 2차원 배열의 경우에서 인접한 배열을 ( 위 - 오른쪽 - 아래 - 왼쪽 )의 순서로 방문한다고 가정하자.

그러면 해당 내용을 간단하게 의사 코드로 표현하면 아래와 같다.

void DFS_array( int x, int y) {

	visit(x,y);
    
    if (isValid(x, y +1)) { // 위의 배열 방문 
    	DFS_array ( x, y+1);
    }
    if (isValid(x+1, y)) { // 오른쪽 배열 방문 
    	DFS_array ( x+1, y);
    }
    if (isValid(x, y -1)) { // 아래 배열 방문 
    	DFS_array ( x, y-1);
    }
    if (isValid(x-1, y)) { // 왼쪽 배열 방문 
    	DFS_array ( x-1, y);
    }
}    

이동 순서 ( 위 - 오른쪽 - 아래 - 왼쪽 ) 

 9번에서 4방향 모두 방문한 상태로 return 

 8번에서 - > 10번으로 이동하여 계속 DFS 진행 

이러한 방식으로 기본적으로 2차원 배열에서 DFS가 어떻게 동작하는지 파악하였으니 

이러한 내용을 응용하여 Flood Fill 알고리즘에 적용해 보도록 하자

해당 그림에서 검은색은 벽이고 하얀 부분을 방문 가능한 영역이라고 했을 때, 

최종적으로 방문 할 수 있는 영역의 개수를 구하는 문제를 푼다고 해보자 

    int floodFill(int[][] metrics) {
        int cnt = 0;
        for (int i = 0; i < metrics.length; i++) {

            for (int j = 0; j < metrics[0].length; j++) {

                if (isValid(metrics[i][j])) { // 벽이 아닌 영역인지 판단, 이미 방문했는지 판단
                    cnt++;
                    DFS_array(i, j);
                }
            }
        }

        return cnt;
    }