Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처특정한 최단 경로 골드 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개에 대한 불을 퍼..

🧫 문제 분석 ✔️ 출처여행 가자 골드 4 📖 문제 서로소 집합 또는 BFS-DFS 알고리즘 둘중 하나로 풀 수 있는 문제다. 주어진 섬들을 여행 시작점을 출발로 탐색해서여행 계획 섬들을 전부 방문했는지만 따지면된다.  서로소 집합의 경우 여행 계획 섬들의 부모가 모두 같으면 여행 가능하다. 🔅 문제 풀이 [BFS]import java.io.*;import java.util.*;public class Main { static boolean[] visited; static boolean[][] graph; // 방문한 곳을 여행 계획에서 체크하면 된다. // 여행계획 섬을 방문하지 않았다면 이는 불가능한 것 public static void main(String[] args..

🧫 문제 분석 ✔️ 출처문자열 폭 골드 4 📖 문제 문제에 나온대로 반복해서 삭제 시도 --- 메모리, 시간 초과Stack으로 풀어보면 되지 않을까 싶어서 Stack으로 풀었다.  그리고 바로 더 좋은 방법이 있나 생각해봤는데 StringBuilder에 문자 하나씩 넣고 폭발 문자 끝단어와 현재 탐색하는 단어가 같으면 폭발 문자가 있을 가능성이 있으므로 StringBuilder.length - 폭발문자 길이 부터 끝까지를 추출해서 폭발 문자와 같은 지 확인하고 맞다면 삭제하는 식으로 하면된다.  🔅 1차 Stack 문제 풀이 (600ms)import java.io.*;import java.util.*;public class Main { public static void main(String[]..

1. 정의JWT(JSON Web Token) : JSON 기반의 토큰 인증 방식 보안이 필요한 시스템에서 사용자 인증 및 정보를 안전하게 교환하거나세션을 사용하지 않는 무상태(stateless) 인증 시스템 에서 주로 사용 - 별도의 세션 저장소 강제 X   2. 구조JWT는 . 으로 구분된 세가지 부분으로 구성된다. Header.Payload.Verify_Signature(서명) Header 서명 알고리즘 (HMAC SHA256, RSA 등을 사용)토큰의 타입Payload Claim에 대한 property를 key-value 형태로 저장Claim은 일반적으로 사용자 정보 및 토큰에 대한 정보를 포함SignatureHeader와 Payload를 조합한 후 비밀키를 이용해 해싱한 값 해당 서명으로 토큰 위..