Meluu_의 코딩 공부 일지

최근 토비의 스프링 3.1 책을 배우기 시작했다. 김영한 선생님의 강의를 이미 다 들었지만, 뭔가 더 깊게 배우고싶다는 생각이 들었다.  1장 챕터의 내용은 오브젝트와 의존관계로 내가 이해한 바로는 책임, 관심사 분리이다.  해당 부분을 공부하면서 임시로 미리 만든 프로젝트의 필터를 보니 정말 책에서 표현한 대로 난감했다.필터의 역할은 토큰 검증인데 비지니스 로직과, 시큐리티컨텍스트 홀더 저장 로직, 헤더와 토큰 저장 로직등이 들어있었다.이 기회에 배운 내용을 적용해보려한다. 기존 코드@Slf4j@RequiredArgsConstructorpublic class JwtAuthenticationFilter extends OncePerRequestFilter { private final JwtUtils ..

✔️ 출처행렬 제곱 골드 4 📖 문제 1시간 30분 걸렸다.생각할게 많았독 옛날에 행렬 연산 했을때도 구현이 잘 안되서 오래걸렸는데이번에도 마찬가지다.. 행렬 연산에 대해서 자세히 이해하고 구현해볼 예정이다. 설명하기 어렵다.. 🔅 문제 풀이 import java.io.*;import java.util.StringTokenizer;public class Main { static int[][] poweredA; // 제곱된 A 행렬 저장 static int[][] operand; // 제곱된 A 행렬을 복사하여 자기 자신을 곱하도록 만들 피연산 행렬 static int[][][] matrixPowers; // 제곱 연산 결과 행렬 public static void main(Str..

🧫 문제 분석 ✔️ 출처이진 검색 트리 골드 4 📖 문제 노드가 최대 1만개 이며, 완전 이진 트리가 아니기 때문에 한쪽으로 치우쳐진 트리가 될 수 있다.이때 최대 인덱스는 iₙ = 2 * iₙ₋₁ + 1 점화식으로 증가하며, 1만번 반복되므로 상상을 초월하는 값이 나오기 때문에  절대로 배열로 해서는 안된다.  1~10까지를 순서대로 넣게되면1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047로 약 2^11 - 1 까지 커진걸 확인할 수 있다.  즉, 최대 1만개 노드라면 2^10000 - 1 까지 커질 수 있다. 따라서 노드 객체를 만들고 좌우에 노드를 연결하는 방식으로 접근해야한다. 자바에서는 객체의 주소 값을 복사하기 때문에 . 연산자로 접근해서 객체를 생성하여 ..

🧫 문제 분석 ✔️ 출처특정한 최단 경로 골드 4 📖 문제  최단경로 + 정해진 정점을 지나기 많이 고민해보고 처음 설계는 1 -> v1 -> v2 -> N 으로 가면 되지 않나? 싶어서 저 한 가지 경우만 만들어서 했으나 당연히 실패했다. 반례를 보니 v2 -> v1- >N 경로가 더 짧은 경우가 있다. 따라서1 -> v1 -> v2 -> N1 -> v2 -> v1 -> N 두가지에 대해서 풀었다. 근데 바보같이 입력받을때 정점 e만큼 받아야하는데 n만큼 받도록 해서 계속 틀렸다이런 사소한 실수.. 제발 그만좀 하고싶다.   🔅 문제 풀이 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader..

🧫 문제 분석 ✔️ 출처파이프 옮기기 1 골드 5 📖 문제 BFS로 89%에서 시간초과 떠서 별짓을 다 하다가 질문게시판에 map[n][n] == 1일때 예외처리를 하면 된다 해서 했는데 통과했다. DP로 풀 생각은 들었는데 방향을 DP로 어떻게 표현할지 모르겠어서 무작정 BFS로 일단 풀었다.  방향 정하는 방식을 좀 이상하게했다.  DP로 하는 법을 이해해 보고 그림으로 그려봤다 dp로 현재 들어오는 방향에 대해서 다 구하면 된다 . 🔅 문제 풀이import java.io.*;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { static int[] dy =..

🧫 문제 분석 ✔️ 출처LCS 골드 5 📖 문제 최장 공통 부분 수열로 알고리즘 시간에 배웠었다. 근데 배운거랑 직접 구현해본거랑 차이가 심한 것을 느꼈다. 이 문제를 못푸니 배낭문제도 못푼다. LCS에 대한 이해가 있었다면 배낭 문제를 쉽게 풀 수 있을 것이다.  현재 비교하는 두 문자가 같다면 이전 최장 공통 부분 수열 길이에 + 1을 하여 LCS를 갱신한다. 두 문자열의 길이를 각각 n과 m이라 할 때,DP 테이블 dp는 인덱스 i∈[0,n]  j∈[0,m] 범위를 기반으로 구성된다. i-1, j-1까지 진행 했을때 LCS 길이 + 현재 공통 문자가 나왔으므로 길이가 1 증가때문에 dp[i-1][j-1] + 1이 된다.  같지 않다면 dp[i-1][j], dp[i][j-1] 중 큰 값을 유지한다..

🧫 문제 분석 ✔️ 출처N과 M (9) 실버 2 📖 문제 N과 M 9번째 시리즈N개의 자연수 중 M개를 고른 수열이면서 그 수열이 중복되면 안된다.  입력받은 N개의 자연수를 우선 오름차순으로 정렬한 후 백트래킹 탐색을 한다. 수열을 문자열로 만들고 Set에 중복 체크를 한 다음 없다면Queue에 넣어서 저장 탐색이 끝나면 Queue를 다 꺼내서 출력하면 된다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static Set set = new HashSet(); // 수열 중복 체크 static StringBuilder sb = new StringBuilder(); // 수열 만들기용 static List list..

🧫 문제 분석 ✔️ 출처케빈 베이컨 6단계 법칙 실버 1 📖 문제 어디서 많이 봤던 문제촌수 따지는 문제랑도 비슷한 것 같다. 다른점은 모든 사람들의 케빈 베이컨 지수 중 가장 작은 지수를 가진 사람을 찾는 것즉, 모든 사람에 대한 모든 사람의 최단거리, 플로이드 와샬 알고리즘을 쓸 수 있다. BFS로 그냥 풀어도 된다.  🔅 문제 풀이 (플로이드 와샬)import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in..

🧫 문제 분석 ✔️ 출처램프 골드 4 📖 문제  예전에 못풀었다가 정말 잊혀질때 쯤, 바로 오늘 풀게되었다.알고리즘 분류는 브루트 포스지만 나는 그리디 알고리즘이라고 생각한다.  처음 시도때 생각없이 브루트 포스로 모든 경우의 수를 해봤었는데 당연히 시간초과났다. 이번에는 예제를 유심히 보다가 램프 행을 전체적으로 봤을때 똑같은 패턴인 램프 행들이 있었다. 그 패턴들 마다 개수를 저장하고, 개수를 내림차순으로 정렬해서 k번 스위치를 눌렀을 때 가능한지 불가능한지 판별하는 방식으로 짜서 성공했다. 스위치 누름 처리방법가장 많이 나온 패턴이 0001 이라고 하자. 개수는 3개1. 안켜진 상태 즉, 0의 개수를 센다.2. 한 열을 제외한 나머지 0은 다 킨다. (k - 0의 개수 + 1)  (여기서는 01..

🧫 문제 분석 ✔️ 출처불! 골드 3 📖 문제  BFS로 풀 수 있는 문제로문제에서 탈출구는 끝부분 즉, 행이 0이거나 열이 0 인 곳에 가기만 하면 탈출한다. ....J. //여기서는 8곳이 탈출구이다.....##.J# //여기서는 0,0, 1,0 이 탈출구이다.### 또한 매 분마다 불이 퍼지고, 지훈이도 이동하는데불을 먼저 이동시키고 지훈이를 이동시키면 된다.  불이 퍼졌을 때 불에 대한 방문 체크와 벽 체크지훈이는 방문체크, 불과 벽 체크를 하면서 이동하면 된다.  분마다 퍼진 불들을 큐에 넣고 그 시간에 퍼진 불들만 퍼뜨려야한다. 아니면 시간과 상관없이 전부 퍼진다.  ....F. // 0분 초기상태....F. // 1분 전 1,1에 있는 불 하나가 퍼졌으므로 이 1개에 대한 불을 퍼..