L.O.K

프로그래밍 분야에서는 시간-공간 트레이드-오프(Trade-off) 현상이 자주 일어난다. 처리시간을 줄이면 처리공간이 늘어나고 처리공간이 줄어들면 처리시간이 늘어나는 현상이다. 세그먼트 트리(Segement Tree)는 공간을 늘리고 시간을 줄인 알고리즘이다. 5 8 7 3 2 5 1 8 9 8 7 3 세그먼트 트리가 필요한 이유는 수열의 구간합 테이블을 더 빠른속도로 구현하기 위함이다. 노드의 개수가 N일때 구간합테이블을 배열로 구성하면 N개의 노드가 필요하지만 시간복잡도는 O(N)이다. 반면 세그먼트 트리로 구성하면 최대 4xN개 노드가 필요하지만 시간복잡도는 O(logN)이다. ( 4xN개의 노드가 필요한 이유는 밑에서 다루어 보겠다. ) 그러므로 수열의 변경이 자주 일어나 구간합테이블이 자주 변경..

Spring의 핵심개념은 의존성 주입(DI)이다. 의존이란,A의 기능이 동작하려면 객체B가 존재해야 함을 의미한다. 예를들어, Controller는 웹화면을 구성하는 역할을 한다. 화면을 구성하려면 서비스에 맞는 데이터를 전달 받아야 한다. 그러므로 Controller는 데이터를 서비스에 맞게 처리하는 로직을 가지고 있는 Service에 의존한다. Service는 데이터가 필요하므로 데이터를 가져오는 기능을 갖는 Repository에 의존한다. 이처럼, 객체지향구조는 서로 '의존'하고 있는 구조이다. 그러나 의존을 주입하는 코드를 개발자가 직접 구현하면 객체를 직접 관리해야 하고 객체간 결합도가 증가시킬 수 있다. Spring 프레임워크 존재 이유는 여기에 있다. Spring은 컨테이너라는 공간이 있다...

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net ◎ 문제풀이 채널을 이동하는 경우는 2가지가 있다. 첫번째 경우 : 100번에서 +,-로 이동하는 경우 두번째 경우 : 리모컨 버튼으로 목표채널과 가장 가까운 채널로 이동 후 +,-로 이동하는 경우 두 가지 경우 중 최솟값이 정답이다. 두번째 경우는 브루트포스로 풀어야 한다. 브루트포스는 탐색할 범위를 먼저 정해야 한다. 채널은 0~500,000 까지 있지만 리모컨은 9999.....

[JPA] 영속성 컨텍스트의 이점 [JPA] JPA 동작원리 ( 영속성 컨텍스트 ) [JPA] 패러다임의 불일치 어플리케이션 개발은 주로 객체지향언어로 이루어진다. 객체지향언어는 현실의 많은 문제를 코드로 구현하지만 문제가 있다. 데이 lordofkangs.tistory.com 지난 포스팅에서 영속성컨텍스트의 이점에서 변경감지(DirtyChecking)를 다루어보았다. 엔티티에 변경사항이 감지되면 영속성컨텍스트는 자동으로 UPDATE,DELETE문을 생성하였다. 그러나 이 방법은 변경감지 한 건당 하나의 쿼리문을 생성한다. 만약 100개의 변경감지가 만들어졌다면 100개의 쿼리가 생성되어 실행된다. 이는 성능에 좋지 못하다. 그래서 UPDATE문,DELETE문을 JPQL로 만들어 여러 건의 변경및삭제를 ..

Named쿼리란, 쿼리에 이름을 부여한 쿼리이다. @Entity @NamedQueries({ @NamedQuery(name = "Person.findAll", query = "SELECT p FROM Person p"), @NamedQuery(name = "Person.findByAge", query = "SELECT p FROM Person p WHERE p.age = :age") }) public class Person { @Id private Long id; private String name; private int age; } 엔티티와 관련된 NamedQuery를 사용하면 '이름'으로 편하게 JPQL을 재활용할 수 있다. public class PersonRepository { @Persisten..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net ◎ 문제풀이 한 개의 회의실을 최대로 이용할 수 있는 회의의 개수를 구하는 문제이다. 끝나는 시간이 기준이다. 회의가 언제 끝나는지를 알아야 무엇을 시작할지가 결정된다. 그러므로 가장 빨리 끝나는 것부터 하나씩 회의실을 잡으면 된다. 그래서 정렬을 활용하여 문제를 풀었더니 한 가지 반례가 있었다. 2 9 9 1 9 끝나는 시간을 기준으로 하면 위 반례를 커버하지 못한다. 둘 다 똑같이 9시에 끝나지만 시작시간이 다르다. 그러므로 아래와 같이 풀면 된다. 1) 시작시간으로 먼저 정렬한다. 시작시간으로 정렬하면 같은..

11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net ◎문제풀이 무방향 그래프의 연결요소의 개수를 구하는 문제이다. 연결요소는 끊어짐 없이 연결된 그래프를 의미한다. 무방향 그래프에서 연결요소를 구하는 대표적인 알고리즘은 UNION-FIND 알고리즘이다. [Algorithm] Union-Find 알고리즘이란? ( with 서로소 집합 자료구조 ) 서로소 집합(Disjoint Sets)이란? 공통원소가 없는 두 집합을 의미한다. 이는 그래프(Graph) 구..

https://lordofkangs.tistory.com/390. [JPA] JOIN 과 JOIN FETCH의 차이 JOIN과 JOIN FETCH를 헷갈릴 수 있다. FROM 엔티티A JOIN FETCH 엔티티B FROM 엔티티A JOIN 엔티티B JOIN FETCH를 사용하면 엔티티A,엔티티B 둘 다 영속화 된다. JOIN을 사용하면 엔티티A만 영속화 된다. JOIN은 엔티 lordofkangs.tistory.com 연관관계있는 엔티티는 JOIN을 활용하여 다른 엔티티에 접근한다. 그렇다면 상속관계에 있는 엔티티들은 어떻게 접근할까? JPA는 상속구조에 유용한 함수를 제공한다. 함수를 이용하면 JOIN문을 사용하지 않아도 부모가 자식에 접근할 수 있다. TYPE SELECT i FROM Item i W..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)www.acmicpc.net ◎ 문제풀이 카드팩 안에는 1 ~ N개의 카드가 들어있다. 카드팩의 비용은 개수에 상관없이 제각각이다. 민규가 N개의 카드를 구할 수 있는 비용의 최댓값을 구하는 문제이다. N개 목표가 주어졌고 1~N개가 카드팩으로 묶여 있으므로 기저조건이다. 기저조건으로 목표를 구하는 문제이므로 DP로 풀면된다. 4개의 카드의 최댓값을 구해보자. 4개의 카드를 구할 수 있는 사건은 4개가 있다. 첫번째 사건 : 1개 팩 ..

https://www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net ◎ 문제풀이 개인적으로 어려운 문제라 아래 포스팅을 참고하여 풀었다. 백준[ 1790 | Python ] 수 이어 쓰기 2 구현, 수학 yeoooo.github.io 수를 1부터 n까지 이어붙였을 때 k번째 수를 구하는 문제이다. 단순히 수를 모두 이어붙혀 문자열을 만들고 문자열의 k번째 수를 출력하면 될거 같지만 n이 최대 1억개라 이어붙이는 과정에서 메모리 초과가 발생한다. 그래서 실제로 이어붙이는 것이 아닌 '탐색'을 해야..