Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처파티 골드 3 📖 문제 O(N^3) 인 플로이드 워샬은 사용불가능하고,다익스트라로 풀어야하는 문제다. 그런데 X→모든 정점은 구하겠는데 모든 정점→X를 편하게 구하는 법을 몰라서 각 정점에서 다익스트라 알고리즘을 돌려서 X까지의 값을 구하는 식으로 했다.  이 후 다른 사람의 풀이를 봤는데 정말 놀랍다.  단방향이지만 역방향으로 그래프를 만들어서// 기존 X -> AllAll -> X// 다른사람들의 풀이X -> All X 로 X에서 모든정점으로 가는 그래프를 만들고X로 오는 모든 정점으로 가는 역방향 그래프를 만드는 것이다. 좋은 것을 배웠다..  🔅 문제 풀이 [x→ all → x]import java.io.*;import java.util.*;public class Ma..

🧫 문제 분석 ✔️ 출처사전 순 최대 공통 부분 수열 골드 4 📖 문제 삽질을 많이 한 문제그리디 알고리즘인데  처음에는 문자열로 만들어서 하다가 생각해보니 100 같은 건 더 큰 수인데 사전순으로는 매우 낮다.  두번째로 A  수열의 각각의 위치에서 시작해서 LDS 탐색을 해서 여러 LDS를 얻어B  수열에서 또 LDS각각 원소에 대해 맞는지 확인하는 식이였는데 그냥 엉터리였고, 이상한 접근법을 해서 틀렸다. A 수열에서 큰값순으로 값을 저장한다음 단순히 B 수열에서 순차적으로 찾아도 안된다.51 90 100 85 5 5100 90 5 1 2//answer2100 5// wrong3100 90 5 A수열에서 큰 값 순으로 저장했다면100 90 85 5 1이렇게 저장되어있을 것이다.  제일 큰 100..

최근 토비의 스프링 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..