전체 글

세그먼트 트리는 sum, sub 연산 말고도 min, max, gcd, lcm과 같은 다양한 연산이 가능한 자료구조이다. Segment Tree 주어지는 연속된 데이터에 대한 구간 연산(Update, query)을 O(logn) 시간에 할 수 있는 자료구조이다. 다음과 같은 배열이 있다고 하자. (index는 왼쪽부터 0이다) SUM 연산을 위한 세그먼트 트리는 위 배열을 다음과 같이 표현한다. 표현 방식은 굉장히 간단한데, 각 노드의 자식 노드를 더해서 해당 노드의 값으로 표현한다. 즉 루트 노드는 전체 원소의 합이라고 볼 수 있다. 전체 원소의 합이라는 것은 전체 원소를 cover 한다는 뜻으로 생각하면 된다. 즉, root에서 leaf로 내려갈수록 cover 범위가 줄어든다고 보면 된다. 그리고 루..

문제 발생 응답 메시지에 포함된 한글이 깨져서 테스트에 어려움을 겪음 해결 방법 기존의 @AutoConfigureMockMvc를 사용하는 새로운 어노테이션을 생성하고 CharacterEncodingFilter를 추가하여 해결할 수 있다. 기존 코드에서 @AutoConfigureMockMvc를 새롭게 생성한 어노테이션으로 대체해주자. @Target(ElementType.TYPE) @Retention(RetentionPolicy.RUNTIME) @Documented @AutoConfigureMockMvc @Import(EnableMockMvc.Config.class) public @interface EnableMockMvc { class Config { @Bean public CharacterEncoding..

풀이 만약 a, b, p, q 가 다음과 같다고 한다면 [3, 9, 2, 3] a(3) : b(9) = p(2) : q(3)를 만족해야 한다. (여기서 a, b의 값은 재료의 질량이다) 즉 pb * x == qa * y를 만족해야 한다. 그럼 (lcm은 최소공배수, gcd는 최대공약수이다) x = lcm / pb = (qa * pb) / gcd / pb = qa / gcd = 1 y = lcm / qa = (qa * pb) / gcd / qa = pb / gcd = 2 위처럼 x, y를 구할 수 있다. 그런데 이때 x, y에 최대공약수가 존재할 수 있다. 우리는 최소가 되는 결과값을 원하기 때문에 최대공약수가 있다면 해당 값으로 나누어줘야 한다. 따라서 x, y의 gcd를 구하여 나누어준다음 다른 비율들..

https://solved.ac/profile/seaworld0125 solved.ac 알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 난이도 및 티어 정보 제공 solved.ac 약 두 달 넘는 기간 동안 백준을 풀었고 오늘 후기를 남기려고 한다. 일단 기록을 보면 알 수 있지만 초반에 중요한 코딩 테스트가 예정되어 있어서 뜻하지 않게 시작되었던 1일 1 백준 도전이었다. 초반에 미친 듯이 알고리즘을 풀었고 하루에 5문제는 기본으로 풀었던 것 같다. 그때쯤 블로그에 알고리즘 개념도 많이 정리해서 포스팅했었다. 그 이후에는 다른 중요한 일정들이 있어서 병행하다 보니 하루에 많은 문제를 풀지는 못했다. 그리고 두 달이 지난 지금 돌아보면 알고리즘 공부는 미친 듯이 하는 게 실력 ..

코딩 컨벤션 프로젝트에서 사용할 JAVA 코딩 컨벤션을 설정한다. intellij에 google-style-guide 적용 자동완성 코딩 스타일을 적용한다. 1. https://github.com/google/styleguide/blob/gh-pages/intellij-java-google-style.xml 다운 2. intellij -> File -> Settings -> Editor -> Code style -> Java -> Scheme -> 톱니바퀴 버튼 -> Import Scheme -> Intellij IDEA... 선택 3. 다운 받은 xml 파일 선택 및 적용 4. 해당 설정 화면에서 Tab size, Indent는 4로 변경, Continuation indent는 8로 변경 및 적용 5...

웹 스코프는 웹 환경에서만 동작하는데, 스프링이 해당 웹 스코프의 종료 시점까지 관리한다. 따라서 프로토타입 스코프와 다르게 종료 메서드가 호출된다. 웹 스코프의 종류는 다음과 같다. request : HTTP 요청이 들어오고 나갈 때까지 유지되는 스코프이다. 각각의 HTTP 요청마다 별도의 빈 인스턴스가 생성되고 관리된다. session : HTTP Session과 동일한 생명주기를 가지는 스코프 application : 서블릿 컨텍스트(ServletContext)와 동일한 생명주기를 가지는 스코프 websocket : 웹 소켓과 동일한 생명주기를 가지는 스코프 웹 스코프를 테스트해보기 위해서는 웹 환경을 추가해줘야 한다. 다음 의존성을 추가하자. implementation 'org.springfram..

스프링은 다음과 같이 다양한 스코프를 지원한다. 싱글톤 : 기본 스코프, 스프링 컨테이너의 시작과 종료까지 유지되는 가장 넓은 범위의 스코프이다. 프로토타입 : 스프링 컨테이너는 프로토타입 빈의 생성과 의존관계 주입까지만 관여하고 더는 관리하지 않는 매우 짧은 범위의 스코프이다. (생성 ~ 초기화까지만 관여) 웹 관련 스코프 Request : 웹 요청이 들어오고 나갈 때까지 유지되는 스코프이다. Session : 웹 세션이 생성되고 종료될 때까지 유지되는 스코프이다. Application : 웹의 서블릿 컨텍스트와 같은 범위로 유지되는 스코프이다. 스프링 빈은 스프링 컨테이너의 시작과 함께 생성되어서 스프링 컨테이너가 종료될 때 까지 유지되므로 싱글톤 스코프이다. 스프링을 사용하면 대부분 싱글톤 스코프만..

이 문제를 풀면서 어려웠던 건.. 이 문제가 DP가 맞는가? 였다. 요즘 (DP, 그리디, 브루트포스) 종류의 문제를 만나면 갈피를 잡지 못하는 것이 가장 힘들다. 배낭 문제라는 사실을 알았을 땐, 아.. 그치 배낭 문제지..라고 금방 이해되지만 혼자서 그 생각을 해내는 게 가장 어려운 것 같다. 이 문제는 최근에 만난 DP 문제들처럼 약간의 응용이 필요하다. 문제의 목표는 M이상의 메모리를 확보하면서 가장 적은 Cost를 사용하는 것이 목표이다. 그렇다면 DP 관계(?)를 설정할 때 다음과 생각해 볼 수 있다. DP 배열은 2차원 배열로 구성하고 배낭 문제 처럼 접근한다고 하자. 그렇다면 1, 2 선택지 중에 어떤 것을 골라야할까? DP[앱의 index][앱의 memory] 로 구성 DP[앱의 inde..

펜윅 트리는 값이 변경되어도 구간의 합을 빠르게 구할 수 있는 자료구조이다. 기존의 구간 합을 구하는 방법은 값의 변경이 있을 때 매번 O(n)의 시간이 걸리지만 펜윅 트리는 O(logn)의 시간이 걸린다. 어떻게 가능한 걸까? 우선 펜윅 트리의 구조를 먼저 그려보고 살펴보자. 펜윅 트리의 특징은 다음과 같다. 펜윅 트리는 화살표가 가리키는 곳에 각 구간의 합이 저장된다. 조금 헷갈릴 수 있는 부분이 BIT 배열의 인덱스는 0이 아닌 1부터 시작한다. 즉 BIT[1] 에는 원래 배열 arr[0]이 저장된다. BIT[4] 에는 원래 배열 arr[0]~arr[3]의 구간 합이 저장된다. BIT 자료구조를 사용하는 가장 큰 이유는 값의 업데이트와 구간 합을 구하기 위함일 것이다. 값을 어떻게 업데이트하고 합을..