L.O.K

https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net ◎문제풀이 아직 그리디 문제풀이의 감이 부족한것 같다. 최솟값을 구하는 문제라 두 행렬의 차이가 가장 많이 나는 좌표를 추출하여 3X3행렬을 뒤집는 방법으로 풀이를 시도했다. 그런데 이 문제는 그냥 좌표를 차례대로 확인하면서 틀린부분이 있으면 3x3행렬을 뒤집으면 되었다. 현재를 기준으로 최적해를 구하는 것이 그리디 문제이다. 전체에서 가장 많이 차이나는 좌표를 구하여 문제를 푸는 것이 아니다. ◎코드 #BOJ..

JPA에서 조회(SELECT)는 성능최적화가 반드시 고려되어야 한다. 엔티티는 다른 엔티티와 연관관계를 맺고 있기에 엔티티를 조회하는 과정에서 예상치 못한 쿼리가 다량으로 발생할 수 있다.( N+1 문제 ) 이번 포스팅에서는 일대일,대대일 관계(XToOne)에서의 조회API 코드를 단계별로 최적화해보겠다. 일대다관계( XToMany )는 컬렉션 개념이 추가되므로 다음 포스팅에서 다루어 보겠다. 1. 엔티티가 외부로 노출되는 코드 @GetMapping("api/v1/simple-orders") public List orderV1(){ List all = orderRepository.findAll(new OrderSearch()); return all; // 엔티티를 외부로 반환 } 위 Controller ..

스프링은 3계층으로 나뉜다. 프레젠테이션 계층은 Client(화면)과 네트워크 통신을 하며 화면구현을 담당한다. 서비스 계층은 데이터를 처리하는 비즈니스 로직을 가지고 있다. 데이터 엑세스 계층은 DB와 통신하여 데이터를 CRUD하는 역할을 담당한다. JPA의 엔티티(Entity)는 관계형DB의 테이블과 매핑되는 개념으로 데이터 엑세스 계층에서 사용하는 기본단위이다. 엔티티는 테이블 정보가 담긴 클래스로 매우 민감한 정보를 가지고 있다. 그러므로 엔티티가 외부로 노출되는 위험은 없어야 한다. 엔티티의 외부노출을 막기 위해 엔티티를 정제한 클래스를 하나 생성하는데, 그것이 DTO(Data Transfer Object)이다. DTO(Data Transfer Object) DTO는 프레젠테이션 계층에서 화면과..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ◎문제풀이 DP문제를 풀 때, 이차원 리스트를 발상이 어려워 문제풀이가 쉽지 않았다. 각 자리에는 0-9의 수가 들어갈 수 있다. ( 첫번째 자리에는 0이 들어갈 수 없다. ) 8은 두 가지 경우로 생성된다. 1) 7에서 +1 한 경우 2) 9에서 -1 한 경우 두 경우는 독립사건으로 경우의수는 합으로 구한다. d[8] = d[7] +d[9] 1-8까지는 이와 동일하지만 0과 9는 다르다. 0과 9는 한 가지 경우에서 나온다. d[9] = d[8] d[0] = d[1] 여기서 이전 자리와 현재 자리를 구분해야 ..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net ◎ 문제풀이 굉장히 어려운 문제였다. 인터넷에서 풀이법을 찾아보았는데 다른 사람들도 노가다 한 사람을 제외하면 대부분 풀이를 참고해서 푼거 같다. 1. DFS 구현 및 발상 2. 최대값 가지치기 ( 백트래킹 ) 두 가지 요소를 구현하기 어려웠다. 1. DFS 구현 및 발상 완전탐색을 할 때 DFS 알고리즘(재귀호출)을 사용해야 한다. 그 이유는 아래 포스팅에 잘 설명되어 있다. 백준 14500 테..

https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net ◎문제풀이 기저조건( +1, +2, +3)이 주어지고 목표(정수 n)의 구하는 경우의 수를 구하는 문제이므로 DP이다. n이 10이라고 가정하고 +1,+2,+3으로 10을 만드는 방법의 수를 d[10]이라고 해보자. 이때 사건은 총 3가지이다. 첫번째 사건 : +1로 끝나는 경우 = d[9] 두번째 사건 : +2로 끝나는 경우 = d[8] 세번째 사건 : +3으로 끝나는 경우 = d[7] 세 가지 사건은 독립사건이다. 그러므로 점화식은 아래와 같다..

[Alogorithm] 세그먼트 트리 ( Segment Tree ) 프로그래밍 분야에서는 시간-공간 트레이드-오프(Trade-off) 현상이 자주 일어난다. 처리시간을 줄이면 처리공간이 늘어나고 처리공간이 줄어들면 처리시간이 늘어나는 현상이다. 세그먼트 트리(S lordofkangs.tistory.com 지난 포스팅에서 세그먼트 트리를 알아보았다. 세그먼트 트리는 수열의 변경이 잦은 경우 구간합을 빠른속도로 구할 수 있는 알고리즘이다. 세그먼트 트리는 재귀호출로 구현되며, 파라미터로 구간과 구간합이 저장된 노드의 위치를 받는다. 이번 포스팅에서는 원하는 구간의 합을 구하는 로직과 세그먼트 트리를 UPDATE하는 로직을 알아보겠다. 원하는 구간의 합 구하기 세그먼트 트리는 각 노드에 구간의 합이 들어가 있..

준영속 엔티티를 수정하는 방법은 두 가지가 있다. 1. merge ( 병합 ) 2. DirtyChecking ( 변경감지 ) 준영속 엔티티 수정은 merge보다는 DirtyChecking이 권고된다. 왜 그럴까? 준영속 엔티티란? 준영속엔티티란 영속성 엔티티의 관리를 받고 있지 않은 엔티티를 의미한다. 예를들어, DB에서 조회한 Book 엔티티 리스트를 추출하여 만든 화면이다. '조회' 작업이 끝나면 트랜잭션이 종료되어 영속성컨텍스트도 종료된다. 여기서 수정 버튼을 클릭해보자. 데이터를 수정하고 Submit 버튼을 누르면, 새로운 Book 엔티티가 생성된다. 근데 다른 점이 하나 있다. 동일한 식별자가 이미 DB에 있다. '생성(create)'이 아닌 '수정(update)'은 식별자가 가리키는 레코드를 ..

https://lordofkangs.tistory.com/406 [Spring] 의존성 주입이란? ( Dependency Injection ) Spring의 핵심개념은 의존성 주입(DI)이다. 의존이란,A의 기능이 동작하려면 객체B가 존재해야 함을 의미한다. 예를들어, Controller는 웹화면을 구성하는 역할을 한다. 화면을 구성하려면 서비스에 lordofkangs.tistory.com 지난 포스팅에서 의존성 주입에 대해서 알아보았다. 의존성 주입(DI)은 세가지 방식으로 이루어진다. 1) 생성자 주입방식 ( final ) 2) 필드 주입방식 ( @Autowired ) 3) 수정자 주입방식 ( Setter ) 세가지 방식 중 '필드주입방식'은 권고되지 않는다. 권고되지 않는 이유를 생성자,수정자 주입..

이분 그래프(Bipartite Graph)란, 서로 다른 두 집합의 노드 간 연결로 이루어진 그래프이다. 같은 집합의 노드 사이에는 간선이 존재하지 않는다. 예를 들어, 사람-취미 관계를 나타내는 그래프라고 해보자. 위 그래프의 노드는 사람집합, 취미집합 두 가지로 나뉜다. 관계를 나타내는 간선은 사람과 집합 사이에 있어야 한다. 사람과 사람, 취미와 취미 사이에 간선이 있어서는 안 된다. 이렇듯, 이분 그래프는 서로 다른 집합 사이의 네트워크를 나타낼 때 사용된다. 연령별 선호 영화 , 어플 이용자와 동네정보로 동네친구 찾기 서비스 그리고 전력회사와 전력소비자로 전력공급 네트워크도 구성할 수 있다. 고로, 이분 그래프는 같은 집합에 있는 노드 사이에 간선이 있으면 안 된다. 지훈이의 취미가 축구인데, ..