L.O.K

1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net ◎ 문제풀이 카드 묶음을 비교하여 하나로 만들 때, 비교횟수의 최솟값을 구하는 문제이다. 비교횟수가 최소가 되려면 카드묶음이 큰 거를 가장 마지막에 비교해야 한다. 그리고 두 개의 카드묶음을 하나로 합치면 또 하나의 카드 묶음이 만들어진다. 비교횟수가 최소가 되려면 새로 생성된 카드묶음을 포함한 가장 개수가 적은 카드묶음 두 개를 합쳐야 한다. 다시말하여, 새로운 카드묶음이 추가될 때 마다 카드묶음 자료구조에서 매번 최솟값을 구해야 한다는 의미다...

클라이언트로부터 요청(Request)이 들어오면, 요청 데이터는 가장 먼저 Controller에 도착한다. 그러므로 Controller에서 적합한 데이터인지 검사해야 한다. 적합하지 않은 데이터가 서버 내부로직으로 들어오는 것을 방지하기 위해서다. 실무에서는 주로 Bean Validation을 사용한다. 요청이 들어오면 요청에 맞는 DTO 객체에 요청데이터가 담긴다. DTO 필드에는 @NotNull, @NotEmpty 같은 어노테이션이 선언되어 있는데, BeanValidator는 선언되어 있는 어노테이션을 토대로 필드에 담긴 데이터를 검증한다. 그리고 검증결과를 Controller에 넘긴다. Controller는 검증결과에 따라 클라이언트에 적절히 응답하면 된다. 실무에서는 주로 이런 방식으로 요청데이터..

1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net ◎ 문제풀이 문제마다 데드라인이 정해져 있을 때, 컵라면을 최대로 몇 개까지 받을 수 있는지를 구하는 문제이다. 이 문제는 그리디 풀이에 HeapQueue를 떠올리면 간단히 풀리는 문제이다. ( 나는 떠올리지 못했다.. ) 단위시간이 1씩 늘어가면 컵라면을 받을 수 있는 개수도 바뀐다. 시간의 변화에 따른 최적해를 구해야 하므로 그리디로 접근해야 한다. 단위시간 1을 하루로 생각해보자. 한 문제를 푸는데 하루가 걸린다. 데드라인이 2일이라면 이틀 안에 풀면 된다. 최적해..

2655번: 가장높은탑쌓기 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차 www.acmicpc.net ◎ 문제풀이 벽돌이 100개 이하로 주어질 때, 벽돌을 쌓아 올릴 수 있는 최대 높이를 구하는 문제이다. 이 문제가 까다로운 이유는 두 개의 조건을 고려해야 하기 때문이다. 1) 밑면의 넓이 2) 무게 이런 경우, 밑면의 넓이로 정렬해준 다음 무게로 DP 풀이를 하면 된다. 먼저, N개의 벽돌을 밑면의 넓이가 작은 순서대로 오름차순 정렬을 한다. 그리고 밑면의 넓이가 작은 것부터 하나씩 DP 테이블을 만들 것이다. DP테이블은 N번째 블록을 가장 밑으로 하는..

1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net ◎ 문제풀이 공장1에서 공장2로 한번에 이동가능한 최대중량을 구하는 문제이다. BinarySearch와 BFS를 모두 떠올려야 하는 고난도 문제였다. 처음 이 문제를 접했을 때, DFS가 떠올랐다. 공장1에서 공장2까지 가는 모든 경로를 완전탐색해야 한다고 생각했기 때문이다. 그러나 DFS로 풀면 시간초과가 난다. visited[bridge.nextNode] = true; // 역행방지 dfs(bridg..

MVC 패턴으로 화면을 구성하다 보면 한 가지 문제가 발생한다. 상품을 등록하는 과정을 예로 들어보자. Client가 /add 경로를 GET방식으로 요청하면 Server는 상품등록 페이지를 Client에게 전달한다. 상품등록 페이지를 받은 Client는 데이터를 입력하고 상품등록 버튼을 누르면 /add 경로를 POST 방식으로 Server에 요청한다. 요청을 받은 Server는 상품등록 비즈니스 로직을 처리하고 그 결과를 담은 상품상세 페이지를 Client에게 전달한다. Client는 등록된 결과를 상품상세 페이지로 전달받으며 마무리된다. 그러나 여기에는 한 가지 문제가 있다. Client의 마지막 요청은 /add 경로의 Post 방식 요청이다. Client가 브라우저를 새로고침하면 /add 경로의 Po..

[SpringMVC] HTTP 요청 파라미터 - @ModelAttribute [SpringMVC] HTTP 요청 파라미터 - @RequestParam [SpringMVC] 요청(Request)의 종류 ( GET, POST, JSON ) [SpringMVC] 웹서비스에서 Request(요청)가 처리되는 원리 ( + Servlet ) JAVA Runtime Enviroment(JRE)는 하나의 프로세스, 다 lordofkangs.tistory.com 지난 포스팅에서 @ModelAttribute에 대해서 알아보았다. @ModelAttribute는 Get이나 Post 방식으로 들어온 Request 데이터를 특정 객체에 담아 파라미터로 넘겨받는 어노테이션이다. @ModelAttribute 파라미터 선언 @Post..

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net ◎ 문제풀이 다익스트라 알고리즘 문제로 알려져 있는데, 문제를 보니 플로이드 워셜 알고리즘이 더 어울린다고 생각했다. 시작점이 정해져 있지 않았고 모든 노드를 기준으로 하기 때문이다. 플로이드 워셜은 삼중for문을 구현하므로 시간초과를 조심해야 하는데, 시간제한이 1초이고 n이 1000이하라 삼중for문을 돌리면 얼추 시간초과가 걸리지 않는다고 생각했다. [Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘이란?..

1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net ◎ 문제풀이 일직선상에서 책을 놓을 때 최소 걸음을 구하는 문제이다. 어떤 경우가 최소가 될 수 있는지 정확히 따져야 한다. 최소 걸음으로 갈 수 있는 경우는 다음과 같다. 1) 좌우를 번걸아 이동하면 안된다. 좌측으로 갔다가 우측으로 이동하면 0을 거친다. 0을 거치면 어차피 또 다시 책을 들고 갈 수 있으니 최소가 아니게 된다. 자료구조를 좌우로 분리하는 것이 좋다. 2) 가장 멀리 떨어져 있는 책을 가장 마지막에 놓아야 한다. 마지막 조건을 보면 마지막에 책을 ..

1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net ◎ 문제풀이 개인적으로 이렇게 넓은 범위의 경우의 수를 갖는 DP 문제를 푼 것이 처음이기에 풀이를 잘 이어가지 못했다. 볼륨은 매 곡마다 정해진 크기만큼 올리거나 내릴수 있다. 시작볼륨이 5라고 했을때, 곡이 진행되면 진행될수록 그 경우의 수는 2배씩 증가한다. 볼륨의 최대 크기도 정해져 있으니 무조건 매 곡 볼륨을 증가한다고 최대 볼륨이 되는 것 또한 아니다. 모든 경우의 수가 최대 볼륨이 될 수 있는 가능성이 있는 것이..