오답 노트 & 새로 알게 된 점 해당 문제는 우선순위 큐를 만들 때, comperator를 잘 구현할 수 있는지 물어보는 문제였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; public class Main { static int atoi(String str) { return Integer.parseInt(str); } static int N; s..

오답 노트 & 새로 알게 된 점 처음에 이 문제를 이해하는데 어려웠다. a가 0일 때마다 정렬을 하고 거기서 최대값을 뽑아야한다. 이 때, 시간 복잡도는 N^2log(N)이 예상 되어 TLE가 날 것 같다. 그래서 우선순위 큐를 이용하여 정렬하는데 logN을 사용하고 NlogN이 되어 TLE가 안난다. 0이면 pq에서 poll하고 0이 아니면 그 개수만큼 pq에 offer하는 것이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 package Data_Structure; import java.io.BufferedReader; import java...

오답 노트 & 새로 알게 된 점 항상 두 포인터 문제를 풀면 연속 부분 수열, 순서를 지키며 차례대로 라는 말이 문제에서 나왔다. 하지만 이 문제에서는 그러한 힌트가 없었다. 그래서 나는 코테에서 이런 문제가 나온다면 내가 풀 수 있을까?라는 생각이 들었다. 아마 처음에 접근했을 때는 완탐으로 생각을 할 것이다. 그렇다면 타겟을 하나 고르고 -> O(N) 더해서 타겟이 되는 두 수를 구한다 -> O(N^2) 그래서 O(N^3)이다. 당연히 TLE가 난다. 그렇다면 여기서 어떤 방법을 사용해야 시간 복잡도를 줄일 수 있을까? 두 포인터를 사용하여 타겟을 하나 정하고 O(N) 두 수를 정할 때, O(N)을 사용하면 된다. 두 수를 정하고 합이 target보다 작으면 최소 입장에선 최대를 더했는데 작기 때문에..

오답 노트 & 새로 알게 된 점 문제에서 연속한 1개 이상의 수를 뽑았을 때 라는 말로 투 포인터 힌트를 줬다. 투 포인터를 구현하는 코드는 어렵지 않았지만 경우의 수를 계산할 때 생각이 필요하다. 1 2 3 1 2 에서 처음에 1에서 3까지 e가 이동할 수 있다. 그렇다면 경우의 수는 1 1 2 1 2 3 이 있다. 이 점을 보았을 때, e - s + 1를 하게 되면 경우의 수를 계산할 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 package TwoPointers; import java..

오답 노트 & 새로 알게 된 점 문제에서 최대 N개의 연속된 문자열로 투 포인터에 대한 힌트를 주었다. 처음에 문제 접근을 할 때, possible 배열을 boolean으로 했다. 그러나 abbcc와 같은 경우 b의 개수는 2개이므로 b를 하나 없애도 결국 하나 남기 때문에, b가 모두 없어져야 알파벳의 한 종류가 사라지게 된다. 그래서 boolean으로 하면 틀리게 된다!! 처음부터 int로 할껄 그랬나보다.. 아무튼 위에서 말했듯이 b의 개수가 2개라면 0개가 되야지 한 종류의 알파벳이 사라지게 된다. 따라서 s를 움직일 때, possible의 값이 0이 되야지 cnt(종류의 개수를 나타냄)를 -1 할 수 있다. 또한, e를 움직이면서 possible값을 ++ 해줄 때, possible이 1이 되면 ..

오답 노트 & 새로 알게 된 점 문제에서 차이가 M이상이면서 제일 작은 경우를 구하라고 했다. 그렇다면 e를 움직이면서 A[e] - A[s] >= M 되는 순간에 while문을 종료하고 최소값을 갱신하면 된다. 배열은 정렬되어있기 때문에 조건을 만족하는 순간 현재 s에서 구할 수 있는 최소값이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 package TwoPointers; import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..

오답 노트 & 새로 알게 된 점 이 문제는 이분 탐색으로도 풀었던 문제이다. 투 포인터를 이용해서도 풀 수 있기 때문에 투 포인터 공부할 겸 풀어보았다. 당연히 일일이 계산하는 O(N^2) 는 TLE다. O(N)인 투포인터를 생각하게 되었다. 처음에 여기서 i < j 를 보고 정렬하면 안되는건가? index를 유지하라는 말인가?라고 생각했다. 하지만 그게 아니였고, 단지 중복 계산을 막기 위해서이다. 예로 12 + 1과 1 + 12는 서로 같은 것임을 나타낸 것 같다. (나의 생각) 그래서 정렬하고 처음과 끝에서부터 각각 시작하여 투 포인터를 하면 해결할 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ..

강의를 듣다가 @RequestParam과 @PathVariable 의 차이를 알고 싶어 검색하는 도중에, URL과 URI 관련 내용이 있었다. 그래서 URL과 URI의 개념을 공부하는 중에 spring의 getRequestURI와 getRequestURL과 다른 것을 발견했다. URI 안에 URL이 포함되어 있다고 하는데, spring에서는 반대이다. 코드와 로그를 보면 URL이 전체 주소를 나타내고, URI는 /request-param-v1만 반환하는 것을 볼 수 있다. 왜 그런건지 잘 모르겠다.. 나중에 공부해봐야지 @RequestMapping("/request-param-v1") public void requestParamV1(HttpServletRequest request, HttpServletR..

오답 노트 & 새로 알게 된 점 이때까지 두 포인터 문제를 풀 때마다 항상 s와 e가 왼쪽 끝에서 시작하여 오른쪽 끝까지 가는 문제만 풀어보았다. 그래서 해당 문제를 보고 투 포인터로 풀어야겠다라는 생각이 들고, 한 시간동안 어떻게 풀어야하지 생각했다. 이 문제는 s와 e가 양쪽 끝에서 시작하는 투 포인터이다. i * j의 최댓값을 구하려면 A도 최대, B도 최대여야한다. 여기서 그러면 s와 e 중에 어떤 기준으로 움직여야할까? 라는 생각을 해야한다. A[i]와 A[j], 둘 중에 최대값을 움직여본다고 생각해보자. 그렇다면 결국에 min값은 그대로이거나 더 작아지게된다. 마찬가지로 둘의 사이가 가까워져 값이 줄어들게 된다. 결국 최대값을 움직일 필요가 없다. 코드 1 2 3 4 5 6 7 8 9 10 1..

오답 노트 & 새로 알게 된 점 문제에서 홀수를 K개 없애면서 짝수로 이루어진 연속된 수열 중 가장 긴 길이를 구하는 것이다. 만약에 K개의 홀수를 골라 길이를 구한다고 생각하면 바로 TLE가 난다. 그래서 투 포인터를 사용하여 앞에서부터 홀수이면 cnt를 증가시키면서 cnt가 K개 이하일 때까지 e를 늘리면서 길이의 max값을 구하면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 import java.io.BufferedReader; import java.io.IOException; import java.io..

오답 노트 & 새로 알게 된 점 투 포인터 공부를 하고 있어서 이 문제는 무조건 투 포인터로 풀어야한다는 생각을 버리고 풀었다. 처음에 접근할 때, O(N^2)로 풀면 바로 TLE가 나기 때문에 아마 O(NlogN)이하로 풀어야한다. 그리고 연속 부분 수열의 길이라는 힌트를 줬기 때문에 투 포인터로 접근할 수 있다. 여기서 아마 중복 처리를 어떻게 해줬냐가 중요한 것 같다. possible이라는 배열을 만들어 A[i] 배열의 value들을 index에 넣어 ++ 해주었다. 그 중 K값을 넘지 않게 탐색하면서 길이의 최댓값을 구해주면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..

MVC 전체 구조 실제 SpringMVC 구조는 이전 수업부터 계속해서 만들어왔던 MVC 프레임워크 구조와 매우 유사하다. 하지만 FrontController 부분이 MVC에서는 DispatcherServlet라고 하는데 공식 문서에서도 보면 '스프링 MVC는 중앙 서블릿인 DispatcherServlet이 모든 컨트롤러 패턴을 중심으로 설계되었다'고 했다. DispatcherServlet에서는 doDispatch 메서드에서 handler를 조회하고 adapter를 가져와서 핸들러를 호출하게 된다. 이 때, Special Bean Types를 제공한다. ex) HandlerMapping, HandlerAdapter, ViewResolver .. 위의 bean types들을 사용하여 handler, ada..