Treasure House

접근 방법 순서가 있는 노드... 위상 정렬이 절로 떠오르는 문제 설명이다. 위상 정렬 알고리즘을 구현하기만 하면 정답을 맞출 수 있는 문제이다. 입력 제한을 보면 가수가 최대 1000명이 나온다고 하니까 O(N ** 2)까지 두고 풀어도 널널한 느낌이기 때문에, 빈 배열을 찾을 때 그냥 단순 순회하도록 구현한다. 차례대로 뺄 노드를 담을 Queue를 하나 만든다. 각 노드에 대한 조건 노드를 리스트로 둔다. Queue에서 노드를 하나씩 뺄 때마다 모든 노드를 순회하면서 뺀 노드가 존재한다면 리스트에서 빼준다. 위의 단계를 진행한 결과 빈 리스트가 나오게 된다면, 해당 노드를 Queue에 추가해준다. 코드 import java.io.BufferedReader; import java.io.IOExcepti..

0. 목표 Spring Boot 프로젝트에서 Spring Security와 JWT 토큰을 사용해서 회원가입 및 로그인을 구현하는 방법을 알아보자. 1. Spring Security는 어떻게 동작할까? 스프링에 요청을 보내면 먼저 자바 웹 컨테이너가 요청을 수신한 후, 이를 스프링 컨테이너의 Dispatcher Servlet에 릴레이한다. 그 후 Dispatcher Servlet에서 알맞은 컨트롤러를 찾아서 요청을 보내는 과정을 수행한다. 여기서 Spring Security는 서블릿의 Filter 기술을 사용해서 웹 컨테이너가 디스패처 서블릿에 요청을 보낼 때 이를 가로채서 인증 및 인가 로직을 수행한다. 그럼 그 로직은 어떻게 생겼을까? ⁙ 아래의 숫자와 그림의 숫자 단계는 일치하지 않음 아이디와 패스워..

접근 방법 입력 제한을 보면 입력 스트링의 길이가 2500이기 때문에, N ** 2 만큼의 효율성을 가진 알고리즘을 사용하면 되는 것을 유추할 수 있다. 팰린드롬은 연속되는 문자열 중에서 중간 문자를 기준으로, 양옆으로 동일한 문자가 있는 특수한 형태의 문자열을 뜻한다. 문자열의 각 문자를 기준 문자로 두고 순회하는데, 해당 문자를 기준으로 양옆으로 동일한 만큼 이동했을 때 더 이상 동일한 문자가 나오지 않을 때까지 이동한 후, 오른쪽 포인터 값에서 왼쪽 포인터 값을 빼면, 해당 기준 문자의 가장 긴 팰린드롬 길이다. 기준 문자가 한 쌍으로 나올 수도 있기 때문에 순회 기준을 우선 1로 두고, i와 i-1 위치의 문자가 같으면 기준 문자가 i인 경우와 (i, i-1) 쌍이 기준 문자가 되는 경우를 둘 다..

개요 회사에서 사용하는 Spring 서버를 개발하면서 테스트를 하기위해 로컬에서 웹서버를 띄워야 하는데, Spring Boot가 아니기 때문에 Tomcat이 내장되어 있지 않음 외부에서 개발한 후 도입한 프로그램인데, 개발 당시에는 IntelliJ Ultimate 버전을 사용했는지 내장된 Tomcat을 활용한 구축 방법이 안내 되어있음 개발 서버에서도 IntelliJ Ultiamte 버전이 존재하긴 하지만, 너무 오래된 버전인 탓에 Kotlin에 대한 지원이 미흡할 것이라고 판단해서 외부에서 최신 커뮤니티 버전을 들여와서 개발을 진행 로컬에서 테스트를 하기 위해 Smart Tomcat이란 플러그인을 사용해서 서버를 띄우는 작업을 진행 진행 방법 준비물 IntelliJ CE 아무 버전 Smart Tomca..

접근 방법 (자료 구조) 문제의 입력 제한을 보면 scoville 수열에 최대 1 000 000개의 입력이 들어갈 수 있다고 했는데, 이때 차례대로 순회하며 제일 작은 값과 두번 째로 작은 값을 찾으려면 매번 모든 entry를 순회해야 하기 때문에 최대 1 000 000 + 999 999 + ... + 2 + 1 만큼 순회해야 한다 => 어차피 제일 작은 값만 조회하면 되기 때문에 우선 순위 큐를 사용하는 것을 고려할 수 있다. (구현) 모든 scoville 숫자를 pq에 넣어둔 후, 숫자를 두개씩 poll해서 만약 제일 작은 값이 이미 K를 넘은 상태라면 더 이상 수열에 있는 숫자를 볼 필요가 없기 때문에 반복문을 나온다. 이 때 숫자가 두개 이상일 때만 반복하면 되기 때문에 해당 조건을 반복문에 넣는..

https://www.acmicpc.net/problem/13397 접근 방법 (주제 : 최소 값) 주어진 수열을 최대 M 가지의 연속된 수열로 나눌 수 있을 때, 그 연속 수열들의 max - min 값 중 가장 낮은 경우 그 값을 반환해야 함 (효율) 모든 경우의 수를 따져 볼 경우 5000C1 + ... + 5000C5000까지 모두 고려를 해야하기 때문에 더 효율적인 알고리즘을 찾아야 함 최적화 문제를 결정 문제로 바꾸는 이분 파라메트릭 탐색를 사용해서 0 ~ 10000 까지의 범위에서 절반씩 줄여가면서 가능한 가장 낮은 max - min 값을 찾아야 함 전체 수열을 계속 순회하면서, max - min 값이 mid (= right - left) 값을 초과하는 경우, 새로운 부분 수열이 생겨났다고 판..

https://school.programmers.co.kr/learn/courses/30/lessons/161988 접근 방법 몇 번째 요소에서 시작하던지, 수열을 1로 시작한 펄스와 -1로 시작한 펄스가 곱해진 두 개의 수열만 고려하면 됨 index 값에 따라 1과 -1로 값이 교차되는 pulse 변수 사용 최선의 답을 구하기 위해 0 부터 n-1까지 순회를 해야하긴 하지만, 여기서 중요한 점은 어떤 index에서 어떤 선택을 해야 최선의 답이 나올 것인지이다 DP를 사용하여 각 수열에 대해서, a) 현재 index까지의 연속된 누적합 + 현재의 sequence 값 b) 현재의 sequence 값를 비교해서 더 높은 값을 기록한다. dp[i] = max( _sequence[i] , _sequence[i..