LIS LIS는 Longest Increasing Subsequence 의 약자로 한글로는 ‘최장 증가수열’, 또는 ‘최대 증가 부분수열’로 불린다. 이것은 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분수열 중 가장 긴 수열을 말하는데 이때 부분수열의 숫자들은 원 배열에서 위치가 이어져 있지 않아도 된다는 주요한 특징이 있다. 예를 들어 원 배열이 [1,4,6,8,3,5,6,7]일 때 [1,6,8], [4,6,8], [1,7]은 증가 부분수열인데, 이 중 가장 긴 부분수열은 [1,3,5,6,7]이 된다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작..
상속관계 매핑 객체와 달리 RDB에는 상속관계가 존재하지 않는다. 그래서 DB에서는 슈퍼타입-서브타입 관계라는 모델링 기법을 이용해서 객체의 상속관계를 나타낸다. 코드상에서 상속관계 설정은 부모클래스에 @Inheritance 어노테이션을 추가함으로서 설정 가능하다. 1. 부모테이블과 자식테이블을 JOIN하여 연관관계를 맺는다. 2. 부모, 자식 모두를 한개의 테이블로 합치고 TYPE정보를 통해 구분한다. 3. 자식테이블만 만들고 부모테이블의 필드를 포함시켜준다. 1. JOIN을 통한 연관관계 매핑 : @Inheritance(strategy = InheritanceType.JOINED) 부모, 자식객체 각자의 데이터를 저장하는 대신, 자식객체의 테이블에 부모객체의 id를 fk로 두고 관리한다. 이때 jpa..
0. 설계시 생각할것 - 다중성 - 단방향, 양방향 - 연관관계 주인 사실 테이블에서는 외래키 하나로 양쪽 join이 가능하기 때문에 방향성이 의미를 갖지는 않는다. 반면 객체는 참조용 필드가 존재하는 쪽에서만 참조가 가능하기때문에, 한쪽만 참조하면 단방향, 양쪽이 서로 참조하면 양방향 연관관계를 가진다. 그래서 저번 포스트에서 언급했듯이, 테이블과 연관된 단방향 연관관계를 가지는 객체들을 설계한 뒤 양방향 연관관계가 필요하다면 연관관계의 주인을 정하고, 추가적인 메소드를 작성해주면 된다. 따라서 아래에는 기본이 되는 단방향 매핑만 정리하도록 하겠다. 또한(당연한 얘기이지만) 객체 상호간에는 대칭관계를 갖는다 (한쪽이 다대일이면 반대쪽은 일대다). 1. 다대일([N:1]) DB와 매핑하기 - @ManyT..
JOIN JOIN은 두개 이상의 테이블에 대해서 결합하여 나타낼때 사용한다. 결합을 위해서 조건을 지정해줄 수도 있는데, 이 조건은 각 테이블의 열이 일치하는지 여부를 기준으로 한다. 내부 조인은 두 테이블 모두에서 일치하는 값을 가진 행만 골라서 테이블을 만들어서 반환한다. A와 B라는 두 개의 테이블이 있다고 하자. 위 사진에서 볼 수 있듯이 JOIN은 SELECT FROM TABLE A JOIN TABLE B ON 라고 하면 A의 col_a와 B의 col_b가 같은 열들의 경우 A와 B의 선택한 columns 정보를 합쳐서 새로운 테이블을 생성해준다. 위와 같은 두 개의 테이블이 있다고 할 때, SELECT A.ID, A.NAME, B.KNAME FROM A INNER JOIN B ON A.ID=B..
0. 연관관계 매핑하기 앞에서 배웠던 내용들을 바탕으로 이번에는 쇼핑몰을 만드는 코드를 작성해보자. 회원이 상품을 주문하는 단순한 기능을 구현하기 위해서 다음과 같이 테이블을 설계하였다. 테이블의 구조를 설계했으면 JPA 구성을 위해 엔티티를 설계하고 매핑해보자. 한개의 Member객체는 여러개의 Order를 만들 수 있고(일대다 매핑), Order와 Item사이에는 다대다 매핑이 가능하도록 설계했다(하나의 order에 여러개의 item이 들어갈수도, 한 item이 여러 order에 들어갈수도 있으므로). 그런데 이렇게 객체의 설계를 테이블 구조에 맞춰서 설계하면, 테이블의 fk를 객체에 그대로 가져오게 되고, Order객체에서 객체를 주문한 객체를 찾고싶다면 memberId를 통해서 Member객체의 ..
문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 ..
엔티티에 식별자를 할당하는 데에는 4가지 방법이 있는데, 그 중에 SEQUENCE 전략이 있다. @GeneratedValue(strategy = GenerationType.IDENTITY) : DB에 위임하면 알아서 auto_increment해줌 @GeneratedValue(strategy = GenerationType.SEQUENCE) : DB sequence object 사용 @GeneratedValue(strategy = GenerationType.TABLE) : 키생성 전용 테이블 만들기 @GeneratedValue(strategy = GenerationType.AUTO) : 위의 세가지 전략중 적절하게 지정 SEQUENCE전략 사용 설정 @SequenceGenerator 에노테이션은 시퀀스 생성..
설계적인 측면 (객체와 관계형 데이터베이스를 어떻게 매핑해서 사용하는지)에 관한 공부 객체와 테이블 매핑 - @Entity : JPA가 관리하는 객체 명시 - 클래스와 테이블을 매핑하기 위하여 클래스에 @Entity를 명시해준다. @Entity가 명시되지 않은 클래스는 JPA가 관리대상으로 생각하지 않기 때문에 JPA를 사용해서 테이블과 매핑하려면 @Entity 어노테이션을 반드시 명시해주어야 한다. - 기본(public/protected) 생성자가 필수적으로 요구된다. - DB에 저장할 필드에 final 사용이 불가능하다. - @Table : 엔티티와 매핑할 테이블 지정 - @Table(name = " ")와 같이 매핑할 테이블의 이름을 변경할 수 있다. 데이터베이스 스키마 자동 생성이란? JPA는 애..
백트래킹 백트래킹이란 말 그대로 '되추적'의 의미를 가진다. 즉 어떤 노드의 유망성을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드로 돌아가서 다른 자식 노드를 찾는 방법을 의미한다. 브루트 포스 알고리즘과 다른 점은, 모든 경우의 수 중에서 가능성이 존재하지 않는다면(=더 이상 유망하지 않다면) 더이상 탐색하지 않는다는 점이다. 이를 위해서는 상태공간트리를 그려 DFS와 같은 탐색 알고리즘을 통해서 구현할 수 있다. DFS의 특징 자기 자신을 호출하는 순환형태의 알고리즘 형태를 가진다. (재귀 호출이 이루어진다) 상태공간트리에서 탐색한 노드에 대한 정보를 검사해야 한다. 상태공간트리에서 탐색할 노드가 유망한지를 검사해야 한다. 트리의 branch의 끝까지 탐색해야 다음 branch를 탐색하기 때문..
문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 해결 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른다고 했으니, dfs를 이용한 백트래킹으로 구현하면 되겠다고 생각이 들었다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열. int N = sc.nextInt(); int M = sc.nextInt(); boolean[] isVisited = ne..
개요 - DB와 객체를 어떻게 설계하여 매핑(Mapping)할 것인가? - 내부에서 JPA는 어떻게 동작할까? 어플리케이션의 개발시 하나의 EntityManagerFactory를 통해서 고객의 요청(트랜잭션)이 올때마다 EntityManager가 생성되고 커넥션을 통해서 DB와 상호작용이 이루어진다. 이때 EntityManager마다 1대1로 영속성 컨텍스트가 생성된다. 영속성 컨텍스트란? 엔티티를 영구 저장하는 환경이라는 의미 애플리케이션과 데이터베이스 사이에서 객체를 임시 보관하는 가상의 캐시, 데이터베이스같은 역할을 한다. 엔티티매니저를 통해서 엔티티를 저장/조회!!하면 엔티티매니저는 영속성 컨텍스트를 통해서 엔티티를 보관하고 관리한다. >> 저장 뿐 아니라 조회시에도 DB의 데이터는 영속성 컨텍스..
문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8..