공부 기록

[Algorithm] 이분 탐색(Binary Search)

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다. 출처 : https://github.com/rhs0266/FastCampus 탐색 수열과 탐색 대상 x가 주어진 경우 x가 존재하는가? x 이하 or 미만 or 이상 or 초과 하는 원소의 개수는? x랑 가장 가까운 원소는 무엇인가? ... 모든 원소를 보면서 x와 비교를 하는 경우 O(N)의 시간복잡도로 위의 질문을 대답할 수 있다. 그런데 만약 정렬이 된 수열이 주어진다면 어떻게 될까? 정렬된 수열과 탐색 대상 x가 주어진 경우 이분 탐색을 이용하면 더 빠르게 위의 질문을 대답할 수 있다. 이분 탐색 (Binary Search) 정렬이 보장되는 배열에서 기준 x를 가지고 범위를 "이분"하면서 탐색하는 방법 정렬이 보장된다는 의미는 무엇일까..

BOJ 1946 - 신입 사원

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 1. 아이디어 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 것은 고등학교때 배운 여사건을 생각해보면 서류 심사 성적와 면접 시험 성적 모두 다른 지원자보다 떨어지는 경우만 탈락한다는 뜻이다. 모든 지원자의 서류 점수와 면접 점수, 그리고 탈락 여부 정보를 volunteer 클래스로 묶어주고 서류..

BOJ 1931 - 회의실 배정

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net --- 아이디어 맨 처음에는 회의 목록들을 먼저 시작 시간들을 오름차순으로 정렬 후 시작 시간이 같은 경우 끝나는 시간을 오름차순으로 정렬했다. 정렬 후 이중 for문으로 최대 회의 수인 경우를 찾았다. Arrays.sort(confs); for (int i = 0; i = pivot.end) { cnt += 1; pivo..

스프링 부트 초기 설정

1. JDK 1.8 2. MySQL 5.7 3. STS4 4.11.0 버전 4. 이클립스 설정 인텔리 J 키맵 UTF-8 5. 스프링 부트 프로젝트 생성 Spring Boot DevTools 프로젝트에서 파일이 수정되면 자동으로 재시작해주는 기능 Lombok Getter, Setter, 생성자 등을 어노테이션을 통해 자동으로 편리하게 생성해주는 기능 Spring Data JPA DB를 JPA로 만들 예정 MySQL Driver pom.xml에서 일단 주석 처리 후 나중에 사용 Spring Security pom.xml에서 일단 주석 처리 후 나중에 사용 OAth2 Client : 사용 안하고 직접 구현해볼 예정 Spring Web 어노테이션을 쓰기 위해 필요 내장형 컨테이너로 톰캣 기본 탑재 6. 추가 ..

[Spring 기초 이론] 스프링부트의 Response 방식

Handler Mapping GET 요청으로 해당 주소 요청이 오면 적절한 컨트롤러의 함수를 찾아서 실행하는 방식이다. 그 후 응답을 할 때 html 파일을 응답할 지 Data로 응답할 지 결정해야 하는데 html 파일을 응답하게 되면 ViewResolver가 관여해서 응답할 파일의 패턴을 만들어준다. 응답할 파일의 경로에 확장자를 붙여서 패턴을 만드는 방식이다. Data로 응답하게 되면 MessageConverter가 작동하게 된다. 메세지를 컨버팅할 때 기본 전략은 json이다. 스프링 동작 과정 ​ ​ 출처 [무료] 스프링부트 개념정리(이론) - 인프런 | 강의 스프링부트를 공부하며 헷갈리는 개념이 많았던 분 스프링부트에 대해 공부하고 싶었던 모든 분, - 강의 소개 | 인프런... www.infl..

[Spring 기초 이론] 애플리케이션 컨텍스트

스프링 컨테이너 DispatchServlet에 의해 생성되어지는 수 많은 객체들은 어디에서 관리될까? 1. ApplicationContext 객체들이 DispatchServlet에 의해 컴포넌트 스캔이 될 때 ApplicationContext에 등록되는 것을 IoC(제어의 역전)이라고 한다. 직접 new를 통해 객체를 생성하면 해당 객체의 레퍼런스 변수를 관리하기 어렵기 때문에 스프링이 직접 해당 객체를 관리한다. 우리는 이 객체의 주소를 몰라도 된다. 필요할 때 DI(의존성 주입)를 통해 사용하면 된다. DI는 필요한 곳에서 ApplicationContext에 접근해 필요한 객체를 가져오는 방법이다. ApplicationContext는 싱글톤이므로 어디에서 몇번을 접근하든 동일한 객체를 보장한다. se..

BOJ 15970 - 화살표 그리기

https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 아이디어 색깔이 같은 점들 중 가장 가까운 점끼리의 거리를 구해야 하니까 일단 색깔별로 ArrayList에 분류한 후 정렬해준다. 정렬의 특성을 생각해보면 정렬 후 각 원소마다 가장 가까운 원소는 자신의 양 옆 중에 있다는 것을 알 수 있다. 가장 가까운 원소를 찾는다는 문구를 보고 정렬의 특성을 떠올려 정렬로 접근할 수 있어야 한다. 가장 가까운 점끼리의 거리를 구해야 하므로 기준 점의..

[Spring 기초 이론] 디스패처 서블릿

FrontController 패턴 문지기가 web.xml에 너무 많은 Servlet/JSP 정의가 들어있으면 매핑하는 내용이 굉장히 많아지기 때문에 web.xml에 다 정의하기가 힘들다. 따라서 최초 앞단에서 request 요청을 받아서 FrontController에 넘겨준다. 여기서 a.do, b.do가 자원에 내부적으로 request를 다시 보내면 기존에 톰캣이 자동으로 생성해준 request, response를 다시 정의해야 한다. 그러면 기존의 정보들이 사라지니까 새로운 기법을 사용해야 한다. 재요청시에 최초의 request, reponse를 다시 새로 정의하는 것이 아니라 기존의 정보를 유지하고 덮어씌우는 requestDispatcher라는 기법을 사용한다. RequestDispatcher 필요..

BOJ 11652 - 카드

https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 1. 아이디어 Int 범위로는 부족하니까 long 자료구조를 사용해야 한다. 최빈값을 구해야 하는 문제이다. 정렬의 특성을 생각해보면 같은 정보들은 인접해있다는 것을 알 수 있으므로 이 특성을 이용해 최빈값을 구한다. 예를 들어 6 7 2 3 2 6 7 6 의 카드가 주어졌을 때 정렬을 하면 2 2 3 6 6 6 7 7 이 된다. 먼저 정렬을 한 후 같은 정보들은 인접해있다는 특성을 이용해 ..

BOJ 1015 - 수열 정렬

https://www.acmicpc.net/problem/1015 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 1. 아이디어 1. 주어진 배열을 인덱스와 함께 정렬 2. 정렬된 배열의 인덱스 값을 P 배열에 저장 2. 시간 복잡도 정렬만 해주면 바로 P 배열을 채워줄 수 있으므로 정렬의 시간복잡도인 O(N log N) 만큼 걸린다. N의 최댓값은 50이므로 1초안에 풀이가 가능하다. 3. 구현 import java.io.*; import java.uti..