L.O.K

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ◎ 문제풀이 가중치 없는 그래프에서 최단거리를 구하는 문제는 BFS로 푼다. DFS는 깊이우선탐색으로 최악의 경우를 먼저 탐색할 가능성이 있어서 처리시간이 오래 걸린다. 넓이 우선 탐색으로 해야 최악의 경우를 사전에 방지할 수 있다. ◎ 코드 Python #BOJ2178 미로탐색 (bfs) import sys from collections import deque input = sys.stdin.readline n,m = map(..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net ◎ 문제풀이 이 문제는 어렵게 느껴진다. 현재를 목표로 만드는데 한 개의 스위치가 여러 개의 전구에 영향을 주어, 경우를 복잡하게 만들기 때문이다. n번 스위치를 눌러 n번 전구를 목표와 일치시켰는데, n+1 스위치가 눌리면 다시 원위치이다. 그러므로 위 문제는 복잡하게 얽힌 경우를 얼마나 단순히 풀어낼 수 있는가를 묻는 문제이다. 경우를 나누어 보자. 1) 첫 번째 ..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net ◎ 문제풀이 n까지의 정수 중 최대의 연속된 합을 구하는 문제이다. n까지의 정수 중에 연속된 최대의 합은 두 가지 경우가 있다. 1) 연속된 합이 n까지 연속되는 경우 2) 연속된 합이 n까지 연속되지 않은 경우 2가지 경우 중 최대값을 구하면 된다. ◎ 코드 #BOJ1912 연속합 (dp) import sys input = sys.stdin.readline n = int(input()) arr = lis..

람다는 메서드 참조로 깔끔하게 표현될 수 있다. 리스트를 정렬하는 코드를 람다로 표현하면 아래와 같다. 람다표현식 List str = Arrays.asList("a","b","A","B"); str.sort((s1,s2)-> s1.compareToIgnoreCase(s2)); List 인터페이스의 sort 메소드는 Comparator 함수형 인터페이스를 인수로 갖는다. 그럼 람다는 Compartor의 유일한 메서드인 compare()를 람다표현식으로 표현해야 한다. (s1,s2)-> s1.compareToIgnoreCase(s2) 컴파일러는 함수형인터페이스의 함수디스크립터와 람다표현식이 호환되는지 검사한다. 메서드 참조 List str = Arrays.asList("a","b","A","B"); str...

Spring은 3계층으로 나뉜다. JPA는 ORM 프레임워크로 트랜잭션이 시작되는 서비스계층과 데이터 엑세스 계층을 위해 존재한다. 그러나 엔티티(Entity)는 DB로부터 CRUD 데이터를 전달하기 위해, 프레젠테이션 계층에도 존재할 수 있다. 이를 위해, 트랜잭션과 영속성 컨텍스트의 생존범위를 달리 할 필요가 있다. 데이터 엑세스 계층에서 엔티티A를 로드했는데, 프레젠테이션 계층에서 엔티티A를 DTO로 변환하는 과정에서 엔티티A와 연관된 엔티티B가 필요하여 LAZY 전략으로 로딩할 수가 있다. 그러므로 엔티티 로딩을 담당하는 영속성 컨텍스트는 트랜잭션이 끝나도 프레젠테이션 계층(View)의 호출이 종료될 때까지 살아있어야 한다. DB는 단순조회의 경우, 트랜잭션 없이도 조회가 가능하기 때문이다. 이와..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ◎ 문제풀이 DP는 수열에서 나올 수 있는 부분수열의 모든 경우에서 조건에 맞는 경우를 구하는 문제이다. 이때, 부분수열의 조건이 '가장 길고'(Longest) '증가하는'(Incresing) 부분수열(Subsequence)를 구하는 문제라면, LIS( Longest Increasing Subsequence) 알고리즘 ..

[JPA] 조회 API 성능 최적화하기 ( XToMany ) (1) [JPA] 조회 API 성능 최적화하기 ( XToOne ) JPA에서 조회(SELECT)는 성능최적화가 반드시 고려되어야 한다. 엔티티는 다른 엔티티와 연관관계를 맺고 있기에 엔티티를 조회하는 과정에서 예상치 못한 lordofkangs.tistory.com [JPA] 조회 API 성능 최적화하기( XToMany ) (2) - default_batch_fetch_size [JPA] 조회 API 성능 최적화하기 ( XToMany ) (1) [JPA] 조회 API 성능 최적화하기 ( XToOne ) JPA에서 조회(SELECT)는 성능최적화가 반드시 고려되어야 한다. 엔티티는 다른 엔티티와 연관관계를 맺고 있기에 lordofkangs.tist..

[JPA] 조회 API 성능 최적화하기 ( XToMany ) (1) [JPA] 조회 API 성능 최적화하기 ( XToOne ) JPA에서 조회(SELECT)는 성능최적화가 반드시 고려되어야 한다. 엔티티는 다른 엔티티와 연관관계를 맺고 있기에 엔티티를 조회하는 과정에서 예상치 못한 lordofkangs.tistory.com 지난 포스팅에서는 JOIN FETCH로 조회API 성능최적화를 해보았다. JOIN FETCH의 문제는 일대다 관계에서 컬렉션을 페이징하지 못함에 있다. 페이징이 필요없다면 상관없지만 페이징이 필요하다면 다른 방법이 필요하다. 4. default_batch_fetch_size로 최적화하기 JOIN FETCH로 일대다 연관관계의 페이징이 안되면 깔끔히 포기하자. 대신 Lazy 페치전략을 ..

[JPA] 조회 API 성능 최적화하기 ( XToOne ) JPA에서 조회(SELECT)는 성능최적화가 반드시 고려되어야 한다. 엔티티는 다른 엔티티와 연관관계를 맺고 있기에 엔티티를 조회하는 과정에서 예상치 못한 쿼리가 다량으로 발생할 수 있다.( N+1 문 lordofkangs.tistory.com 조회(SELECT)는 성능 최적화가 반드시 고려되어야 한다. 엔티티는 다른 엔티티와 연관관계를 맺고 있어, 엔티티를 메모리에 로딩하는 과정에서 연관된 엔티티 로딩하는 전략을 생각해야 한다. 지난 포스팅에서는 일대일,다대일 관계(XToOne)에서 조회 API를 성능최적화를 해보았다. 이번 포스팅에서는 컬렉션 개념이 등장하는 일대다, 다대다 관계( XToMany )에서 조회 API의 성능을 최적화 해보겠다. ..

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net ◎ 문제풀이 단순히 +1 씩 증가시켜 탐색하면 시간초과 나오는 문제이다. 는 x에 M개, y에 N개가 들어갈 수 있으므로 총 M*N개의 경우의 수를 갖는다. M과 N은 최대 40,000이므로 M*N은 1,600,000,000이다. 시간제한 1초는 2억-3억 연산을 수행할 수 있는데 최대연산횟수가 16억이므로 아득히 넘어간다. 위 문제는 수학으로 접근해야 풀린다. M,N이 주어졌을 때, 가 몇 번째에서..