Meluu_의 코딩 공부 일지

백준 9252번 : LCS2 [자바]

🧫 문제 분석 ✔️ 출처LCS 2 골드 4 📖 문제 LCS 문제와 다른 점은 LCS를 출력해야한다는 것이다.단순히 순차적으로 탐색하면서LCS에서 길이가 1인 처음 만나는 문자LCS에서 길이가 2인 처음 만나는 문자이런식으로 풀면 안된다. 문자열이 같은 문자가 연속으로 주어지는 경우 잘못된 LCS를 구하게 되기 때문이다. AAACCCAACCA A A C C AA 1 1 1 1 1A 1 2 2 2 2 A 1 2 2 2 3C 1 2 3 3 3C 1 2 3 4 4C 1 2 3 4 4 이렇게 위에서부터 순차적으로 for문 탐색시 AAAC가 되버린다.답은 AACC 이다. 때문에 가장 마지막 위치에서 이전 대각위, 왼쪽, 위쪽을 탐색하여 같은 길이 값이면 그 곳으로 이동하고3곳이 다 다르다면 현재 자신이..

🧫 문제 분석✔️ 출처다각형의 면적 골드 5 📖 문제 신발끈 공식 이라는 특이한 다각형 면적 구하는 공식이 있다.문제에서 다각형을 이루는 순서대로 N개의 점 좌표가 주어진다하였으므로 그대로 신발끈 공식을 적용한다. 계산을 할때 long 형으로 받아야하는 점, 출력을 소수점 둘째 자리에서 반올림하여야하는 점을 고려하면된다.String.format을 사용해서 %.1f 를 사용하면 내부적으로 둘째자리까지 반올림해서 문자열을 만들어준다. 🔅 문제 풀이import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.StringTokenizer;public class Main { /..

🧫 문제 분석 ✔️ 출처마인크래프트 실버 2 📖 문제 완전탐색 문제로 땅 고르기를 하면된다. 주어진 땅 높이들의 최소, 최댓값을 구한 후최소~최대 높이까지 탐색을 해서 최단 시간이면서 가장 높은 높이를 구하면된다. 나는 잘못 푼게 있는데 맵 탐색중 2번 작업시 인벤토리내에 블록이 없으면 바로 불가능하다고 판단하고 멈췄는데 생각이 짧았다..현재 위치에서 인벤토리가 비어있더라도다른 위치에서 1번 작업을 통해 블록을 인벤에 저장하고 현재 위치에서 사용할 수 있는데이걸 생각못한게 정말 .. 눈물이난다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int totalTime = Integer.MAX_VALUE; s..

🧫 문제 분석✔️ 출처N-Queen 골드 4 📖 문제 많은 깨달음을 준 문제다. 퀸의 특성상 상하좌우대각을 원하는 만큼 이동이 가능하기에 그에 따른 검증을 해야한다. 처음에는 이중 배열로 만들어서 각 퀸의 위치를 리스트에 저장하고 리스트를 순회하면서 검증하고 놨는데 시간복잡도가 너무 크게 나와서 O((N^2)^N) 힌트를 보고 풀었다. 퀸 특성상 n개의 체스판에서는 각 행에 하나씩 둬야 n개의 퀸을 둘 수 있다.때문에 퀸을 두고 다음 행을 탐색한 후 돌아온 다음 다시 퀸을 지울 필요없이 덮어씌우면된다. (백트래킹에서) 나의 잘못된 생각은검증시 0~n 행까지 전부 다 해서 쓸모없는 연산이 늘고, 잘못된 검증이 되어 값이 증가한 것이다. 말했듯이 n개의 퀸을 놓을려면 0행부터 순서대로 n행까지 하나..

🧫 문제 분석 ✔️ 출처치즈 골드 3 📖 문제 외부 공기를 기준으로 BFS 탐색하여 치즈와 맞닿으면 카운팅해준다.  그런데 다른 풀이를 보고 했는데 치즈가 가장자리 (0,0)에서 시작할 수도 있지 않나 싶은데0,0 부터 외부 공기 찾는 로직이 있어도 다 통과해서 치즈가 가장자리에는 위치하지 않나보다. 나는 치즈의 처음 만나는 지점과 마지막 지점을 구하고, 안쪽 방향을 제외한 3방향을 탐색해서 공기외부 좌표를 구한다음BFS 탐색을 하여 공기 접촉 탐색을 했다. 공기를 2번 이상 접촉하면그 지점을 공기로 만들면 된다.   7 71 1 1 0 0 0 01 0 1 1 0 0 01 0 1 0 1 0 00 1 0 1 0 1 00 0 1 0 1 0 00 0 0 1 0 0 00 0 0 0 0 0 0//answer ..

🧫 문제 분석 ✔️ 출처파티 골드 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 까지 커질 수 있다. 따라서 노드 객체를 만들고 좌우에 노드를 연결하는 방식으로 접근해야한다. 자바에서는 객체의 주소 값을 복사하기 때문에 . 연산자로 접근해서 객체를 생성하여 ..