코드 훔쳐보는 변태 코더
춤 좋아하는 백엔드 개발자(였으면 좋겠다)
분류 전체보기 (95)
백준 19638번 센티와 마법의 뿅망치 (자바) 풀이
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB 1869 625 506 33.488%

문제

센티는 마법 도구들을 지니고 여행을 떠나는 것이 취미인 악당이다.

거인의 나라에 도착한 센티는 자신보다 키가 크거나 같은 거인들이 있다는 사실이 마음에 들지 않았다.

센티가 꺼내 들은 마법 도구는 바로 마법의 뿅망치로, 이 뿅망치에 맞은 사람의 키가 ⌊ 뿅망치에 맞은 사람의 키 / 2 ⌋로 변하는 마법 도구이다. 단, 키가 1인 경우 더 줄어들 수가 없어 뿅망치의 영향을 받지 않는다.

하지만 마법의 뿅망치는 횟수 제한이 있다. 그래서 센티는 마법의 뿅망치를 효율적으로 사용하기 위한 전략을 수립했다. 바로 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다.

과연 센티가 수립한 전략에 맞게 마법의 뿅망치를 이용한다면 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있을까?

입력

첫 번째 줄에는 센티를 제외한 거인의 나라의 인구수 N (1 ≤ N ≤ 105)과 센티의 키를 나타내는 정수 Hcenti (1 ≤ Hcenti ≤ 2 × 109), 마법의 뿅망치의 횟수 제한 T (1 ≤ T ≤ 105)가 빈칸을 사이에 두고 주어진다. 

두 번째 줄부터 N개의 줄에 각 거인의 키를 나타내는 정수 H (1 ≤ H ≤ 2 × 109)가 주어진다.

출력

마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수를 출력한다.

마법의 뿅망치를 센티의 전략대로 남은 횟수 전부 이용하고도 거인의 나라에서 센티보다 키가 크거나 같은 거인이 있는 경우, 첫 번째 줄에 NO를 출력하고, 두 번째 줄에 마법의 뿅망치 사용 이후 거인의 나라에서 키가 가장 큰 거인의 키를 출력한다.

예제 입력 1 복사

1 10 1
20

예제 출력 1 복사

NO
10

예제 입력 2 복사

2 10 3
16
32

예제 출력 2 복사

YES
3

 

풀이

힙 자료구조를 구현해 풀이하면 된다.

우선순위 큐를 이용하여 풀이했다.

 

문제 자체가 힌트가 다 주어져있다. 가장 큰 키부터 망치로 떄려서 절반으로 줄인다고 했으니

단순히 최대힙에서 루트 노드 데이터를 가져와 절반으로 나누고 다시 넣어주면 된다.

그리고 반복문에서 때리려는 거인의 키가 1이거나 센티가 더 크다면 break 해주면 된다.

 

출력문에서 원하는 그대로 루트 노드의 데이터가 센티의 키보다 작다면 yes 와 count 를, 크다면 no와 루트노드의 값을 출력하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Integer.parseInt(st.nextToken());
        long  H = Integer.parseInt(st.nextToken());
        long T = Integer.parseInt(st.nextToken());
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2)-> o2-o1);
        int count =0;
        for(int i=0; i<N; i++){
            queue.add(Integer.valueOf(br.readLine()));
        }
        for(int i=0; i<T;i++){
            if(queue.peek()<H || queue.peek()==1){
                break;
            }
            queue.add(queue.poll()/2);
            count++;
        }
        if(queue.peek()<H){
            System.out.println("YES");
            System.out.println(count);
        }
        else if(queue.peek()>=H){
            System.out.println("NO");
            System.out.println(queue.peek());
        }
    }
}

시간복잡도는 반복문이 상수회 돌고 있기 때문에 O(1) 로 표기할 수 있다.

 

  Comments,     Trackbacks
백준 17478번 재귀함수가 뭔가요? (자바) 풀이
시간 제한메모리 제한제출정답맞힌 사람정답 비율

 

1 초 256 MB 38589 15339 12735 38.831%

문제

평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다.

매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다.

중앙대학교와 자신의 길이 맞지 않다고 생각한 JH 교수님은 결국 중앙대학교를 떠나기로 결정하였다.

떠나기 전까지도 제자들을 생각하셨던 JH 교수님은 재귀함수가 무엇인지 물어보는 학생들을 위한 작은 선물로 자동 응답 챗봇을 준비하기로 했다.

JH 교수님이 만들 챗봇의 응답을 출력하는 프로그램을 만들어보자.

입력

교수님이 출력을 원하는 재귀 횟수 N(1 ≤ N ≤ 50)이 주어진다.

출력

출력 예시를 보고 재귀 횟수에 따른 챗봇의 응답을 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
____"재귀함수가 뭔가요?"
____"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
____마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
____그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
________"재귀함수가 뭔가요?"
________"재귀함수는 자기 자신을 호출하는 함수라네"
________라고 답변하였지.
____라고 답변하였지.
라고 답변하였지.

 

풀이

해당 문제는 재귀함수를 사용해 풀이하면 된다...

아무래도 재귀는 어렵게 느껴져서 다른 사람의 풀이를 참고했다.

해당 문제의 언더바가 쌓이고 줄어드는 모습은 스택에 메소드가 쌓이는 모습을 상상해보면 어느정도 이해가 된다.

재귀함수는 메소드가 차곡차곡 쌓이고 조건에 다다를때부터는 차곡차곡 빠지기 때문이다.

이것을 활용해 정적변수 언더바를 선언하고 재귀 함수가 호출될때마다 언더바에 ____를 더해준다면 조건에 다다를때 ____가 더해진만큼 다시 줄어들게 된다.

 

솔직히 이렇게 작성하면서도 크게 와닿는 부분은 없다. 재귀 부분은 브론즈부터 다시 풀어봐야겠다는 생각이 든다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class a17478 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
        recur(N);
    }
    static String underbar ="";
    public static void recur(int N){
        String line = underbar;
        if(N == 0){
            System.out.println(line+"\"재귀함수가 뭔가요?\"");
            System.out.println(line+"\"재귀함수는 자기 자신을 호출하는 함수라네\"");
            System.out.println(line+"라고 답변하였지.");
            return;
        }
            System.out.println(line+"\"재귀함수가 뭔가요?\"");
            System.out.println(line+"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
            System.out.println(line+"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
            System.out.println(line+"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
        underbar+="____";
        recur(N-1);
        System.out.println(line+"라고 답변하였지.");
    }
}

  Comments,     Trackbacks
힙 자료구조에 대해서 알아보자 🤔

힙이란 뭘까 ? 🤔

  • 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리이다.
    • 브랜치가 최대 2개이다. (이진)
    • 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리이다. (완전)
  • 최소값과 최소값을 찾으면 O(logn)이 걸린다.
    • 배열에서 최소값과 최대값을 찾으려면 O(n)이 걸리기때문에 힙이 훨씬 빠르다.
    • 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다.

힙과 이진탐색 트리의 공통점과 차이점  🤔

  • 차이점 ⇒ 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모노드, 그 다음 오른쪽 자식 노드 값이 가장 크지만 힙은 무조건 왼쪽부터 값을 집어넣는다.
    • 이진 탐색트리는 검색을 위한 구조이고, 힙은 최소값 최댓값을 구하기 위한 구조이다.
  • 공통점 ⇒ 모두 이진트리이다. (최대 브랜치가 2개이다.)

최소 힙이냐, 최대 힙이냐에 따라서 추가적인 조건이 존재한다.

  • 최대 힙 → 각 노드의 값이 자식 노드의 값보다 크거나 같다.
  • 최소 힙 → 각 노드의 값이 자식 노드의 값보다 작거나 같다.
    • 따라서 가장 크거나 작은 값은 루트 노드에 존재하게 된다.

힙의 기본 동작

데이터 삽입

  • 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입이 된다.
  • 최대힙이라면 조건이 하나 더 존재한다. 항상 부모 노드가 자식노드보다 큰 값을 가져야한다.
    • 채워진 노드 위치에서 부모 노드보다 값이 클 경우 부모 노드와 위치를 바꿔준다. (계속해서 큰 값을 가진다면 루트노드로 갈때까지 위치를 바꾼다.)
    데이터 삭제
  • 보통 삭제는 루트 노드를 삭제하는 것이 일반적이다.
    • 보통은 최소값/최대값 을 알기 위해서 힙을 사용하기 때문에 루트 노드를 삭제하는것이 일반적이다.
  • 루트 노드가 삭제될시에, 남아있는 데이터의 오른쪽의 끝에 존재하는 노트를 루트 노드로 위치를 변경하고 자식노드와 값을 비교해서 다시 루트노드에 최소/최대값을 배치한다.

힙과 배열

  • 힙에서는 보통 데이터를 배열에 저장한다.
    • 계산을 통해서 자식 노드와 부모 노드를 찾아낸다.
  • 배열은 보통 인덱스가 0부터 시작하지만, 힙을 구현할때는 0번은 null로 만든 후 1번 인덱스부터 루트 노드의 값을 저장한다.
    • 부모노드와 자식 노드는 인덱스 번호만 계산 할 수 있으면 된다.
      • 자식노드의 인덱스 번호를 2로 나눈 몫을 부모 노드의 인덱스 번호로 사용한다.
      • 왼쪽 자식 노드의 인덱스 번호는 부모 노드의 인덱스 번호에 2를 곱한 값을 사용한다.
      • 오른쪽 자식 노드의 인덱스 번호는 부모 노드의 인덱스 번호에 2를 곱한 후 1을 더한 값이 사용된다.

마무리  🤔

  • 우선순위 큐를 사용할때 힙과 기존 이진탐색 트리의 차이점을 설명 못했었는데, 이제 좀 설명을 할 수 있을것 같습니다.
    • 최대힙 같은 경우에는 자식노드가 부모노드보다 값이 작거나 같아야 합니다.
    • 이진 탐색 트리같은 경우에는 검색을 위한 자료구조이고, 완전 이진트리는 최소값 최대값 을 구하기 위한 자료구조라는것을 알게되었습니다.

 

  Comments,     Trackbacks
22-12-13~22-12-19 개발공부 회고록

기존의 주간목표를 작성했던 부분에서 매일 TIL에 일일목표를 작성하는것으로 변경했습니다.

진행했던 것들 🤔

  • 알고리즘 정리
    • 시간복잡도 개념익히기
    • 해시 테이블 익히기
    • 트리 구조 익히고 구현해보기
    • 해시/우선순위 큐 문제 풀이
  • 스프링 토이 프로젝트
    • 전체 코드 리팩토링 
      • 각 메소드별로 중복된 부분 추출후 함수화
      • 기존 DTO 하나로만 전달하던 것에서 필요한 정보만 주고 받을 수 있도록 Request Response DTO를 사용하도록 수정
      • JPA 공부하면서 DB조회 빈도를 줄일 수 있도록 고민 후 수정
    • 테스트 코드 작성/수정
  • JPA 5장,7장,장 정리
    • 연관관계 매핑
    • 고급 매핑
    • 프록시와 연관관계 관리
  • 그룹스터디 워크샵 준비
    • 회의/발표 준비/모의발표/ 워크샵 진행

 

느꼈던 점 🤔

  • 이번 한 주는 유난히 힘들었습니다.
    • 매일 먹고자고싸는 시간 제외 머릿속에 코딩생각과 공부생각으로 살아왔는데, 드디어 한계가 온 것 같았습니다.
    • 생각해보니 내가 춤을 그만둔 이유도 너무 춤에 모든것을 쏟아버린 나머지 흥미를 잃어서 그만둔것이었는데, 이렇게 하면 의미가 있나 라는 생각이 들었습니다.
      • 최대한 붙잡아보려 했지만, 주말은 그냥 쉬도록 날렸고, 일단 우선순위가 가장 높았던 그룹워크샵 준비에 힘을 약간 쏟아 부었습니다.
      • 다행히 좋은 결과가 있었던것 같았습니다.
  • 마인드셋 특강에서 해당 그래프 얘기가 나온적이 있습니다.

  • 지금 절망의 계곡 쯤 온 것 같습니다. 더 열심히 하지 말고 지금처럼 꾸준히만 하자를 목표로 삼아야겠습니다.
  • 이제 주간 회고록에서 목표를 TIL을 꾸준히 작성하는 것으로 변경했습니다.  빈도를 늘려서 일간회고를 습관화 해야겠다는 생각이 들었습니다.

좋았던점  🤔

  • 오랜만에 정말 아무 생각도 안하고 주말을 잘 보낸 것 같습니다.
    • 요즘 신경쓸게 너무 많았는데도 컨디션이 따라주지 않고, 생각보다 혼자 지내는게 외로웠던 한 주였는데 잘 버틴것 같습니다.
  • 힘들어하는 와중에 포기하지 않았습니다. 
    • 하루에 적어도 두시간이상이라도 붙잡았던것 같습니다. 쉴땐 쉬고 놀땐 놀자가 이제 몸에 익은 것 같습니다.
  • 그룹 워크샵 발표는 개인적으로 성공적이었다고 생각합니다.
    • 생각보다 설계가 잘되었다고 생각했습니다. 부족한 부분은 계속 보완해나가며 각 역할별로 최선의 결과를 내려고 노력했던 것 같습니다.
  • 어렵다고 생각했던 알고리즘에 한걸음 더 다가가게 되었습니다.
    • 남은 힙 자료구조만 정리하게 되면, 제가 알고있는 자료구조에 대한 기본적인 개념은 다 나가게 됩니다.
    • 그런데 생각보다? 해당 자료구조 자체가 어렵다는 생각은 들지 않았습니다.
    • 앞으로 그 자료구조들을 어떻게 찜쪄먹을지에 대한 노하우정도만 익히면 코딩테스트 가 아닌 단순 구현에 어려움은 겪지 않을것 같다는 희망이 생겼습니다.
  • 토이프로젝트를 진행하고 리팩토링에 대한 노하우가 살짝 생긴 것 같습니다.
    • 전에는 리팩토링을 한다 할때 겉모습만 바뀌었지 결국 유지보수 하기 쉬운 코드를 작성했다 생각한적이 없었지만 지금은 그래도 관리하기 쉬운 코드를 작성하는 방법을 흉내라도 내는것 같은 착각?이 듭니다.
    • 그 착각을 확신으로 바꾸기 위해서 코딩을 더더욱 습관화 해야겠다는 생각이 들었습니다
      • 마찬가지로 알고리즘 문제 하나를 풀더라도 다른사람들은 어떻게 풀었느냐를 참고하는것도 리팩토링 실력 상승에 영향이 있다고 생각이 들었습니다. 
  • 드디어 기본적인 토이프로젝트는 끝난것 같습니다.
    • 남의 코드를 보고 참고하는것이 아닌 이제 내 자료를 보고 무언가를 새로 시작할 수 있게 되었습니다.
    • 이래서 문서화가 중요하구나 라는 생각이 들었습니다. 다행히 프로젝트를 진행하는 내내 거의 모든 기능 구현에 대한 글을 남겨놓길 잘했다는 생각이 듭니다. 

 

아쉬웠던점 🤔

  • 현타가 온다면 쉬어야하는데 저는 자책을 하고 있습니다. 내가 개발을 당장 그만둬도 내가 먼저인데. 더 제 자신을 사랑해줘야겠습니다.
  • 쉴땐 쉬고 놀땐 놀아라 를 실천하지 못했습니다. 위에는 조금이라도 더 해보려고 노력했다는데, 아닌날에는 쉬어야겠습니다.
  • 생각보다 한 주를 돌아보니 아쉬웠다는 생각은 크게 안듭니다. 제가 그동안 열심히 해와서 덜 찔리나봅니다. 유지라도 열심히 해야겠다는 생각이 듭니다.

 

 

 

  Comments,     Trackbacks
22-12-19 TIL

오늘 진행한 것들 🤔

  • JPA 프록시 객체, 즉시로딩/지연로딩, 영속성 전이와 고아객체 관리 생명주기 정리
 

JPA - 프록시객체와 즉시로딩/지연로딩

프록시 ? 엔티티를 조회할 때 연관된 엔티티들이 항상 사용되는 것은 아니다. 예제 8.3 회원과 팀 정보를 출력하는 비즈니스 로직 public void printUserAndTeam(String memberId) { Member member = em.find(Member.class,

codinghentai.tistory.com

  • 트리 자료구조 코드로 직접 구현해보고 정리 
 

트리 자료구조를 직접 구현해보고 이해해보자 🤔

트리구조 트리는 노드와 연결을 할 수 있는 브랜치를 이용해서 사이클을 이루지 않도록(순회하지 않도록) 구성한 데이터 구조이다. 트리는 넓은 범위로 정의를 한 것이고, 그중에서 익혀야 할

codinghentai.tistory.com

  • 우선순위 큐 알고리즘 2문제, 트리 알고리즘 1문제 풀이  (트리는 정답을 찾지 못해 지금 풀 수 있는 문제를 우선적으로 풀어보자고 생각했다.)
 

백준 15903번 카드 합체 놀이 (자바) 풀이

문제 석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다! 아기

codinghentai.tistory.com

 

백준 2075번 N번째 큰 수 (자바) 풀이

문제 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자. 12 7 9 15 5 13 8 11 19 6 21 10 26 31 16 48 14 28

codinghentai.tistory.com

  • 토이프로젝트 구상
    • Open API를 활용해 정보를 가져와 출력하는 프로젝트를 만들면 재밌을것 같다.
      • 대표적인 예로 OPGG, 던파온, 메이플 등등 각종 게임 API를 사용하는 서비스를 클론하는 프로젝트를 진행하면 재밌을것 같다.
      • 처음부터 방대하게 진행하지 말고 기본 틀을 만들고 차근차근 늘려나가면 될 것 같다.
  • 실시간 강의 데이터베이스 
    • LIMIT,COUNT,DISTINCT,GROUP BY, ORDER BY, AS 문 학습

 

 

오늘의 배운 점 🤔

  • 트리 자료구조에 대해서 공부했습니다.
    • 이진트리와 이진탐색트리 에 대해서 학습했습니다.
    • 단순히 조회 삽입 은 나쁘지 않았지만 삭제가 복잡했습니다.
    • 보니까 해당 트리 구현 만 가지고 풀 수 있는 문제는 별로 없고 , 재귀 , 탐색 , 정렬 등등 여러 용법이 복합적으로 섞인 트리문제가 많은것 같습니다. 
      • 그래도 하나하나 자료구조를 도장깨기 하듯이 공부하고 있는데, 생각보다 이해가 잘됩니다. 이래서 포기하지 말아야하나봅니다🤔
  • 우선순위 큐를 활용한 알고리즘 문제를 풀었습니다.
    • 트리 자료구조 문제를 풀려 했으나, 트리문제는 재귀용법이나 탐색, 구현 등등이 함께 사용되는 문제가 많아서 풀 수 있는 문제로 먼저 눈을 돌렸습니다.
    • 스택/큐 문제는 생각보다 좀 풀었으니, 힙/해시 자료구조 문제를 풀어야겠습니다.
    • 실버2 ,실버1 문제를 풀었습니다. 전에는 절대 제 힘으로 풀지 못했던 문제들을 이제 참고를 하지 않고도 풀 수 있게 되었습니다 🤔
  • JPA 영속성전이, 즉시로딩 지연로딩 에 대해서 공부했습니다.
    • 단순히 의미를 모르고 사용하던 옵션들이 어떤 뜻을 갖고있는지 알게되었습니다.
    • 또한 어떤 상황에 적절한 로딩 방식을 사용해야 하는지도 익혔습니다.
    • 다대다 관계에서의 어노테이션 사용에대한 궁금증이 생겼습니다. 더 읽어봐야겠습니다.
  • 데이터베이스 실시간 강의
    • LIMIT,COUNT,DISTINCT,GROUP BY, ORDER BY, AS 에 대해서 공부했습니다.
    • 결론적으로는 문맥 자체를 살피고 쿼리문을 말하듯이 써내려가면 다 출력이 됩니다.  🤔
  • 토이프로젝트 구상
    • 저는 개인적으로 여러 API를 활용할 수 있는 서비스를 구현하고 싶어하는것 같습니다.
      • Open API를 활용한 프로젝트를 진행하면 재밌겠다는 생각을 했습니다. 빠른 시일 내에 디테일한 설계를 시작해보아도 될 것 같습니다.

 

 

 

내일 목표 🤔

  • 알고리즘 힙구조/재귀용법 정리하기
    • 기존 실버1수준 까지 풀 수 있던 자료구조 골드 하위 문제 도전해보기
  • 이펙티브 자바 한 챕터 읽고 정리하기 / JPA 한 챕터 읽고 정리하기 (챕터 야바위)
  • 게시판 프로젝트 리팩토링 마무리 / 테스트 코드 작성 하고 끝내기
    • 작성한 코드를 왜 그렇게 작성했는지에 대한 이유를 설명할 수 있어야 할 것 같다. 🤔

 

내일도 화이팅! 

 

'TIL' 카테고리의 다른 글

22-12-26 TIL  (0) 2022.12.26
22-12-22 TIL  (0) 2022.12.22
22-12-21 TIL  (0) 2022.12.21
22-12-20 TIL  (0) 2022.12.20
22-12-15 TIL  (0) 2022.12.15
  Comments,     Trackbacks
JPA - 프록시객체와 즉시로딩/지연로딩

프록시 ?

엔티티를 조회할 때 연관된 엔티티들이 항상 사용되는 것은 아니다.

예제 8.3 회원과 팀 정보를 출력하는 비즈니스 로직
public void printUserAndTeam(String memberId) {
    Member member = em.find(Member.class, memberId);
    Team team = member.getTeam();
    System.out.println("회원 이름: " + member.getUsername());
    System.out.println("소속팀: "   + team.getName());
  }

-알라딘 eBook <자바 ORM 표준 JPA 프로그래밍> (김영한 지음) 중에서

해당 코드에서는 멤버 아이디로 엔티티를 호출하면 member 엔티티와 연관된 team 엔티티까지 같이 가져온다.

 

하지만 이 코드에서 팀에대한 출력은 없이 회원 정보만 출력한다면 ? ⇒ 팀 데이터베이스까지 함께 조회해버리니 효율적이지 않다.

해당 문제를 해결하기 위해 엔티티가 실제 사용될 때 까지 데이터베이스 조회를 지연하는 방법을 제공하는데 이것을 지연로딩 이라고 한다. → 말그대로 해당 코드에서 member.getTeam() 메소드가 호출되지 않는다면 팀에대한 데이터베이스 조회는 하지 않는다.

 

지연 로딩 기능을 사용하려면 실제 엔티티 객체 대신에 데이터베이스 조회를 지연할 수 있는 가짜 객체가 필요한데 이것을 프록시 객체라고 한다.

‘Proxy. 대리(행위)나 대리권, 대리 투표, 대리인 등 을 뜻한다.’

프록시 기초 🤔

엔티티를 실제 사용하는 시점까지 데이터베이스 조회를 미루고 싶다면 getReference() 메소드를 사용하면 된다.

해당 메소드를 호출할 때 JPA는 데이터베이스를 조회하지 않고 실제 엔티티 객체도 생성하지 안히는다. 대신 접근을 위임한 프록시 객체를 반환한다.

  • 프록시의 특징
    • 프록시는 실제 클래스와 겉 모양이 같다. 사용하는 입장에서는 구분하지 않고 사용하면 된다.
    • 프록시 객체는 실체 객체에 대한 참조를 보관한다. 그리고 객체의 메소드를 호출하면 프록시 객체는 실제 객체의 메소드를 호출한다.
    • 객체는 처음 사용할 때 한 번만 초기화된다.
    • 객체를 초기화 한다고 프록시 객체가 실제 엔티티로 바뀌는 것은 아니다. 실제 엔티티에 접근 할 수 있는것
    • 원본 엔티티를 상속받은 객체이므로 타입 체크시에 주의해야한다.
    • 영속성 컨텍스트에 찾는 엔티티가 이미 있다면 DB를 조회하지 않고 실제 엔티티를 반환한다.
    • 준영속 상태의 프록시를 초기화 하면 문제가 발생한다.
  • 프록시 객체의 초기화
    • 프록시 객체는 실제로 사용될 때 데이터베이스를 조회해 실제 엔티티 객체를 생성하는데, 이것을 프록시 객체의 초기화 라고 한다. ⇒ 사용될때 실제 객체를 생성하기 때문
      • 메소드 호출→ 초기화 요청→ 영속성 컨텍스트에 엔티티 생성 요청 → DB조회→ 영속성 컨텍스트가 DB를 조회해서 실제 엔티티 생성 / 해당 순서로 프록시 객체의 초기화가 이뤄진다.
  • 프록시와 식별자
    • 프록시 객체는 식별자 값을 보관하기 때문에 식별자 값을 조회하는 메소드를 호출해도 프록시를 초기화하지 않는다.
    • 프록시는 연관관계를 설정할 때 유용하게 사용할 수 있다. → 식별자 값만 사용하기 때문에 데이터베이스 접근 횟수를 줄일 수 있다.
  • 프록시 확인
    • JPA가 제공하는 PersistenceUnitUtil.isLoaded(Object entity) 메소드를 사용하면 인스턴스의 초기화 여부를 확인할 수 있다. ⇒ 인스턴스의 초기화 여부가 분명해야 하는 경우가 있을까 ? 🤔
      • 극각의 성능을 내려면 초기화 여부까지 따져가며 데이터베이스 조회 횟수를 줄이는 방법도 있을거같다.. 🤔

즉시 로딩과 지연 로딩 🤔

JPA는 개발자가 조회 시점을 선택할 수 있도록 두가지 방법을 제공한다.

  • 즉시 로딩
    • 엔티티를 조회할 때 연관된 엔티티도 함께 조회한다.
    • 설정방법 : @ManyToOne (fetch = FetchType.EAGER)
    • 즉시 로딩을 최적화 하기 위해서 조인 쿼리를 사용하기도 한다. → 조인쿼리를 사용하면 쿼리 한번으로 두 엔티티를 모두 조회한다. (외래 키에 NOT NULL 제약 조건을 설정하면 값이 있는것을 보장하기 때문에 내부 조인을 사용할 수 있다. nullable=false 를 설정하면 기본으로 설정되있는 외부조인 대신에 내부조인을 사용한다.)
      • 선택적 관계 → 외부 조인, 필수 관계 → 내부 조인
  • 지연 로딩
    • 연관 엔티티를 실제 사용하는 시점에 DB를 조회한다.
    • 설정 방법 : @ManyToOne (fetch = FetchType.LAZY)
  • 정리
    • 대부분의 애플리케이션 로직에서 연관관계가 맺어져있는 엔티티를 같이 사용한다면 join 을 이용해서 한번에 조회하는것이 더 효율적이다.

지연 로딩 활용 🤔

지연 로딩을 어떻게 활용하면 좋을까? 본인이 기존에 진행하던 프로젝트로 예를 들어보았다.

@Entity
public class Article extends AuditingFields{
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY) // 프라이머리 키
    private Long id;
    //@setter 가 붙은 값이 입력값, 없으면 자동
    @Setter @Column(nullable = false) String title; //n
    // ull 이 아닌 값을 컬럼에 저장 함
    @Setter
    @JoinColumn(name = "userId")
    @ManyToOne(optional = false,fetch = FetchType.EAGER)
    private UserAccount userAccount; // 유저 정보 (ID)

    @Setter @Column(nullable = false,length = 10000) private String content;

    @OrderBy("createdAt")  //id 순서
    @OneToMany(mappedBy = "article", cascade = CascadeType.ALL, fetch = FetchType.LAZY) //양방향 관계 (article이 주체)
    @ToString.Exclude //과부하 발생 예방
    private final Set<ArticleComment> articleComments = new LinkedHashSet<>();

    @OneToMany(mappedBy = "article")
    @ToString.Exclude
    @Setter
    private Set<ArticleHashtag> hashtags = new HashSet<>();

해당 테이블에서 연관관계는 UserAccount ,ArticleComment 와 ArticleHashtag 에 맺어져있다.

해시태그 엔티티는 단독으로 관리되지 않기 때문에 Article 엔티티에 연관관계를 직접 맺어주었고, 마찬가지로 게시글을 작성하거나 댓글을 작성할때 무조건 계정 정보가 들어가고, 댓글 또한 단독으로 관리되지 않기때문에 맺어주었다.

  • UserAccount
    • 게시글이 불러와질때마다 단순히 게시글에 nickname 컬럼이 생성되어있거나 하지 않고 외래 키로 UserAccount 엔티티의 정보를 바로 참조해 출력하기 때문에 EAGER 로 설정해주었다.
  • ArticleComment
    • 댓글은 단독으로 관리되지 않지만, 게시글과 댓글을 한번에 가져오는게 아닌 따로 비동기 통신으로 댓글을 관리한다. 하지만 연관관계는 맺을 수 밖에 없는 상황이기 때문에 키만 참조하고 한번에 조회할 필요가 없기때문에 LAZY로 설정해주었다.
  • ArticleHashtag
    • ArticleHashtag 는 중간 테이블 엔티티가 따로 존재한다. 해당 부분에 지연로딩 즉시로딩을 명시해줬는데, Articled은 LAZY, Hashtag도 LAZY를 명시해주었다.
      • 어차피 게시글을 조회하면 영속성 컨텍스트에서 관리되기때문에 db를 조회해오지 않는다.
      • hashtag 를 즉시로딩 해버리면 해당 해시태그가 등록된 게시글까지 다 불러올것 같다는 생각에 LAZY를 주었다.

이런식으로 각각 엔티티를 조회하는 부분이 달라서 데이터베이스가 무조건 따로 조회되는 경우 말고는 조회 횟수를 신경써가며 즉시로딩, 지연로딩을 활용해주면 좋다.

프록시와 컬렉션 래퍼 🤔

  • 하이버네이트는 엔티티를 영속 상태로 만들 때 컬렉션이 있으면 해당 컬렉션을 추척하고 관리할 목적으로 원본 컬렉션을 하이버네이트가 제공하는 내장 컬렉션으로 변경하는데, 이것을 컬렉션 래퍼라고 한다.
  • 컬렉션을 조회하는 메소드를 호출해도 컬렉션은 초기화 되지 않고, 컬렉션에서 실제 데이터를 조회할 때 데이터베이스를 조회해서 초기화한다.

JPA 기본 Fetch 전략 🤔

  • fetch 속성의 기본 설정값은 다음과 같다.
    • @ManyToOne, @OneToOne : 즉시로딩
    • @OneToMany, @ManyToMany : 지연로딩
  • 추천되는 방법은 모든 연관관계에 지연 로딩을 사용하는것이다.
    • 위에 적용한 로딩 방식을 죄다 지연로딩으로 변경해야겠다. (ㅡ,.ㅡ)
    • 꼭 필요한 곳에만 즉시 로딩을 사용하도록 최적화하면 된다.

영속성 전이 : CASCADE 🤔

  • 연관된 엔티티도 함께 영속 상태로 만들고 싶다면 영속성 전이 기능을 사용하면 된다.
    • 부모 엔티티를 저장할 때 자식 엔티티도 함께 저장할 수 있다.
  • cascade = CascadeType.PERSIST 옵션을 적용하면 부모와 자식 엔티티를 한 번에 영속화 할 수 있다.
  • 영속성 전이는 엔티티를 삭제할때도 부모엔티티만 삭제했을때 자식 엔티티까지 함께 삭제해준다.

고아 객체 🤔

  • JPA는 연관관계가 끊어진 자식 엔티티를 자동으로 삭제하는 기능을 제공하는데 이것을 고아 객체 제거라고 한다.
  • 고아 객체 제거는 참조가 엔티티는 다른 곳에서 참조하지 않는 고아 객체로 보고 삭제하는 기능이다.
  • orphanRemoval 은 @OneToOne, @OneToMany.에만 사용할 수 있다. (삭제한 엔티티를 다른곳에서도 참조하면 문제가 생기기 때문이다.)

마무리

느낀점 🤔

  • 그동안 fetch = FetchType.LAZY 이게 뭔지 전혀 모르고 사용했었는데 지연로딩이라는걸 드디어 알게되었습니다….
  • 중간에 즉시 로딩과 지연로딩을 각각 맞는 상황에 명시하는걸 보고 제 프로젝트에 적용해보았으나 결국엔 확실한 상황 말고는 지연로딩이 좋다는걸 뒤늦게 보고 말았습니다.
    • 지연 로딩을 지원한다는게 결국에는 한번 데이터를 가져올때 최대한 알짜배기만 골라온다는 느낌이라고 단번에 이해가 되었습니다.
  • 양방향 관계에 있어서 영속성 전이를 관리할 수 있으면 좋을텐데, 아직까지는 완전히 이해가 되지는 않은 느낌입니다.
    • 즉시로딩과 지연로딩을 공부한 후 중간 엔티티가 각 엔티티의 부모 엔티티라고 봐야하는것인지.. 헷갈렸습니다.
    • 생각해보니 제 프로젝트에서는 중간 엔티티를 삭제해버리면 각각의 엔티티도 삭제되도록 되있던거 같은데, 해당 부분을 다시 생각하고 구조를 바꿔도 될 것 같습니다 😀
  • 프록시 객체에 대한 개념을 여기서 완벽히 이해한것 같습니다.
    • 여기서 한번 더 getReferenceById 와 findById 의 차이를 짚고 넘어가야 할 것 같습니다.
  • #패스트캠퍼스 #국비지원교육 #메가바이트스쿨 #MegabyteSchool #개발자취업부트캠프 #내일배움카드
  Comments,     Trackbacks
백준 2075번 N번째 큰 수 (자바) 풀이

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력

첫째 줄에 N번째 큰 수를 출력한다.

예제 입력 1 복사

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

예제 출력 1 복사

35

 

풀이

해당 문제는 마찬가지로 우선순위 큐를 사용하는 문제이다.

단순히 N*N의 표가 주어지고, N번째 큰 수를 구하는 것이기 때문에

우선순위 큐를 큰 순서대로 정렬시키고, 말그대로 N-1번을 poll 시킨 후 println에 poll()를 넣어주면 된다.

 

우선순위 큐는 최소 최대값 탐색이 O(1)만에 가능하기 때문에 최댓값 우선으로 정렬한 후 출력하면 된다. (입력은 O(n)인데.. 이부분을 보완하면 좋을거같다는 생각이 든다 🤔)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class a2075 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2-o1);
        int N = Integer.parseInt(br.readLine());
        for(int i=0; i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                queue.add(Integer.valueOf(st.nextToken()));
            }
        }
        for(int i=0; i<N-1;i++){
            queue.poll();
        }
        System.out.println(queue.poll());

    }
}

 

  Comments,     Trackbacks
백준 15903번 카드 합체 놀이 (자바) 풀이

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

  1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
  2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

예제 입력 1 복사

3 1
3 2 6

예제 출력 1 복사

16

예제 입력 2 복사

4 2
4 2 3 1

예제 출력 2 복사

19

 

 

 

풀이

해당 문제는 우선순위 큐로 풀이하면 되는 문제이고 x,y를 가장 작은 수로 가져와서 더한 후 덮어씌우면 된다.

우선순위 큐는 같은값으론 정렬이 안되고 기본 정렬이 작은것부터 내려오게 데이터를 삽입하기 때문에 단순히 우선순위 큐를 만들어주고 값을 넣어준후, 큐에서 수 2개를 poll 하고 더한 후 그 두 수를 다시 add 해주면 된다 .

 

여기서 주의해야할것은 데이터 타입을 long 으로 선언해주어야 한다.

단순히 int 로 한다고 치면 , 조건에 나와있는대로 더하면 범위를 넘어갈것이다.

 

해당 문제는 바로 최소값을 구할 수 있기 때문에 O(1)의 시간복잡도를 가진다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class a15903 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Integer.parseInt(st.nextToken());
        long M = Integer.parseInt(st.nextToken());
        PriorityQueue<Long> queue = new PriorityQueue<>();
         st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            queue.add(Long.valueOf(st.nextToken()));
        }
        for(int i=0;i<M;i++) {
            long a = queue.poll();
            long b = queue.poll();
            queue.add(a + b);
            queue.add(a + b);
        }
        long sum = queue.stream().mapToLong(Long::longValue).sum();
        System.out.println(sum);
    }
}

 

 

  Comments,     Trackbacks