L.O.K

18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net ◎ 문제풀이 나이트를 이동시켜 체스말을 잡을 때, 나이트의 최소 이동수를 구하는 문제이다. 그래프의 좌표가 주어지고 이동비용이 동일할 때 최소이동수를 구하는 문제이니, BFS 풀이이다. 이 문제를 풀며, 시간초과가 발생했을 때 시간복잡도를 계산해서 문제를 다시 리빌딩하는 능력이 부족함을 깨달았다. 처음에는 잡아야하는 체스말이 3개 주어지면 DFS 탐색도 3번하는 방식으로 풀었다. 그랬더니 시간초과가 발생했다. 시간복잡도를 계산..

18511번: 큰 수 구성하기 첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 www.acmicpc.net ◎ 문제풀이 개인적으로 DFS의 새로운 활용을 본 문제였다. 정수 N과 k개의 9보다 작거나 같은 자연수가 주어졌을 때, k개로 만든 정수 중 N보다 작지만 최대인 정수를 구하는 문제이다. k개의 자연수의 조합으로 만들어진 경우의 수 중 최대인 정수를 구하는 문제이니, 이것도 '탐색' 문제이다. k가 최대 3이고 N은 1억보다 작거나 같으니 최대 8자리 수이다. 그러므로 나올 수 있는 경우의 수는 3⁸, 6561가지이다. 시간제한..

https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net ◎ 문제풀이 안테나를 어느 집에 설치해야 [ 안테나 - 집 ] 거리의 합이 최소가 되는 지를 묻는 문제이다. 집은 { 1 , 5 , 9 , 9 , 9 , 11 } 에 주어졌다고 가정하자. 안테나의 위치를 x라고 한다면, sum = [ x - 1 ] + [ x - 5 ] + [ x - 9 ] + [ x - 9 ] + [ x - 9 ] + [ x - 11 ] sum의 최솟값을 구하는 문제이다. 안테나가 양 끝에 있으면 안테..

[QueryDSL] Expression( 표현 ) [QueryDSL] QueryDSL 동작원리(3) - fetch QueryDSL은 JPQL 생성 및 실행 권한을 자신에게 위임하여, 개발자가 JPQL을 직접 작성했을 때 발생하는 타입 안정성 체크의 어려움이나 동적 쿼리생성 문제를 해결할 lordofkangs.tistory.com QueryDSL은 JPQL 생성및실행을 담당하는 프레임워크이다. 개발자(클라이언트)가 원하는 JPQL을 QueryDSL에게 요청하려면 적절한 조건을 '표현'(Expression)해야 한다. '표현'(Expression)이라고 말한 이유는 QueryDSL이 실제로 클라이언트가 원하는 JPQL을 Expression 인터페이스로 표현할 수 있는 환경을 제공하고 있기 때문이다. 표현은 ..

[QueryDSL] QueryDSL 동작원리(3) - fetch QueryDSL은 JPQL 생성 및 실행 권한을 자신에게 위임하여, 개발자가 JPQL을 직접 작성했을 때 발생하는 타입 안정성 체크의 어려움이나 동적 쿼리생성 문제를 해결할 수 있다. 개발자는 그저 JPQL 생성 lordofkangs.tistory.com 지난 포스팅에서 QueryDSL의 동작원리를 다루며 fetch의 의미를 알아보았다. 클라이언트 쪽 QueryDSL 코드 public List searchMember(MemberSearchCondition condition){ return queryFactory .select(member) // JPQL 데이터 설정 START .from(member) .leftJoin(member.team,..

[QueryDSL] Expression( 표현 ) [QueryDSL] QueryDSL 동작원리(3) - fetch QueryDSL은 JPQL 생성 및 실행 권한을 자신에게 위임하여, 개발자가 JPQL을 직접 작성했을 때 발생하는 타입 안정성 체크의 어려움이나 동적 쿼리생성 문제를 해결할 lordofkangs.tistory.com 지난 포스팅에서 Expression을 다루어 보았다. 이번 포스팅에서는 where 메소드의 매개변수로 어떤 Expression이 들어가는지 알아보겠다. QueryDSL 코드 public List searchMember(MemberSearchCondition condition){ return queryFactory .select(member) .from(member) .leftJo..

https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net ◎ 문제풀이 입력으로 주어진 수로 만들 수 있는 30의 배수중 가장 큰 값을 구하는 문제이다. 30은 3x10이므로 30의 배수는 항상 뒤가 0으로 끝난다. 그러므로 30의 배수란, 뒤가 항상 0으로 끝나는 수 중 3의 배수가 되는 수를 의미한다. 그럼 3의 배수가 되는 수를 어떻게 구할까? 여기서 중학교 1학년 때 배운 개념이 사용될거라고는 생각도 못했다. 배수 판정법을 이용하면 된다. 어떤 수의..

[QueryDSL] QueryDSL 동작원리(3) - fetch QueryDSL은 JPQL 생성 및 실행 권한을 자신에게 위임하여, 개발자가 JPQL을 직접 작성했을 때 발생하는 타입 안정성 체크의 어려움이나 동적 쿼리생성 문제를 해결할 수 있다. 개발자는 그저 JPQL 생성 lordofkangs.tistory.com QueryDSL은 JPQL 생성 및 실행 권한을 자신에게 위임하여, 개발자가 JPQL을 직접 작성했을 때 발생하는 타입 안정성 문제나 동적쿼리생성 문제를 해결할 수 있다. 개발자는 그저 JPQL 생성을 위한 메타데이터만 설정하면 된다. QueryDSL은 유연한 데이터 설정을 지원하기 위해 빌더패턴 구조로 이루어져 있다. 여기까지가 지난 포스팅에서 다루었던 내용이다. 개발자(클라이언트)가 Q..

https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net ◎ 문제풀이 그래프에서 싸이클을 찾고 싸이클과 노드 사이의 거리를 구하는 문제이다. 풀이과정은 3가지 STEP으로 진행된다. STEP1) 그래프를 인접리스트로 구현 STEP2) 싸이클 DFS 알고리즘으로 탐색하기 STEP3) 싸이클과 노드사이의 거리를 DFS로 구하기 - 싸이클 DFS 알고리즘으로 탐색하기 싸이클은 DFS, BFS로 탐색이 가능하다. 문제에서 싸이클은 1..

[SpringMVC] 웹서비스에서 Request(요청)가 처리되는 원리 ( + Servlet ) JAVA Runtime Enviroment(JRE)는 하나의 프로세스, 다수의 스레드 환경이다. JVM은 하나의 프로세스로 동작하고 다수의 스레드로 병렬처리를 지원한다. 이런 환경은 Web Service에 매우 적합하다. 프로세스A lordofkangs.tistory.com 지난 포스팅에서 웹서비스에서 요청(Request)이 처리되는 원리에 대해서 다루어 보았다. 이번 포스팅에서는 요청은 어떤 형태로 들어오는지를 알아보겠다. 웹서비스에 요청은 여러 형태로 들어오지만 4가지를 기본으로 알고 있으면 된다. 1) GET 방식 2) POST 방식 3) JSON 방식 4) Message Body방식 HTTP는 대략 H..