Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처열쇠 골드 1 📖 문제 BFS 탐색 + 구현 상근이가 빈 공간을 다니면서 문서를 훔친다.열쇠는 줍고 열쇠가 있는 문이라면 연다. 처음풀이시도에서는열쇠를 얻자마자 해당하는 문에 이동하고그 문의 상하좌우를 탐색해서 한번이라도 방문한 빈 공간이 있다면 이 문은 이동 가능한 문으로 판단하여 탐색했는데 이 풀이의 문제점은 문의 상하좌우의 빈 공간이 방문이 가능함에도 열쇠를 얻은 시점이 더 빨라서 해당 열쇠가 있음에도 이동 할 수 없는 문이라 판단하여 열지 않는다. 따라서 우선 빈 공간을 먼저 다 탐색하면서갖고 있는 열쇠가 있다면 문을 열고 열 수 없는 문은 따로 저장해두고새로운 열쇠는 추가한다. 기존에 갖고 있는 열쇠로 다 탐색을 끝냈다면추가된 키로 열 수 있는 문이 있는지 확..

🧫 문제 분석 ✔️ 출처문제집 골드 2 📖 문제 위상정렬 + 우선순위 큐 문제 먼저 푸는게 좋은 문제들은 위상정렬로 진입차수를 저장해준다. a b 로 a가 먼저 푸는게 좋은 문제면b의 진입차수 1을 늘려준다. 그리고 진입차수가 0인 문제들을 전부 우선순위 큐에 저장하고 하나씩 꺼내서 문제를 푼다. (우선순위 큐 기본 정렬을 사용했으므로 오름차순 정렬되어 난이도가 낮은 순으로 나온다.)풀고 해당 문제가 먼저 푸는게 좋은 문제였다면 연결되어있는 뒤 문제들의 진입차수를 -1 해준다. 이때 연결된 문제들의 진입차수가 0이 되었다면 더이상 먼저 푸는게 좋은 문제는 존재하지 않으므로해당 문제도 우선순위 큐에 저장한다. 🔅 문제 풀이import java.io.*;import java.util.*;import..

🧫 문제 분석✔️ 출처보석 도둑 골드 2 📖 문제 우선순위 큐 문제 주어진 가방을 무게 기준 오름차순 정렬하여 가장 작은 가방부터 보석을 담는다. 가장 작은 가방이 담을 수 있는 보석들 중 최대 값어치인 보석을 해당 가방에 담는식으로 하면 된다. 우선순위 큐를 가격이 높은순으로 사용한다.현재 선택한 가방이 담을 수 있는 보석들을 우선순위 큐에 다 담고하나를 꺼낸다. 이때 꺼낸 보석이 현재 가방이 담을 수 있는 최대 가격의 보석이 된다. 그리고 정답 범위가 30만 * 100만이기에 long타입으로 가격을 계산해야한다. 🔅 문제 풀이import java.io.*;import java.util.*;import java.util.stream.IntStream;public class Main { st..

🧫 문제 분석 ✔️ 출처카드 게임 플래티넘 5 📖 문제 이분탐색 + 유니온 파인드 (서로소 집합)문제 문제의 핵심은철수는 카드를 조작해서 낼 수 있고, 같은 수여러개를 낼 수 도 있음민수는 철수의 카드를 미리 알고 철수가 낸 카드 중 더 큰 수에서 가장 작은 수를 낸다. 문제에서 민수가 카드를 내지 못하는 경우가 없다고 가정하였으므로철수가 낸 카드보다 작거나 같은 카드만 남을 경우가 없다는 의미이다.즉, 철수보다 항상 더 큰 카드 k 개 만큼 내어 항상 승리한다 철수가 낸 카드에 맞게 민수는 자신의 카드에서 적절한 카드를 이분탐색으로 찾아서 낸다.찾은 카드가 철수가 낸 카드와 같다면 그 다음 카드를 가리킨다. 사용한 카드는 그 다음 카드의 대표 집합에 연결한다. 다음 카드의 대표 집합을 연결하는 ..

🧫 문제 분석 ✔️ 출처가장 긴 증가하는 부분 수열 5 플래티넘 5 📖 문제 LIS 시리즈중 마지막 문제기존 이분탐색 LIS에 역추적이 추가된 문제다. 실제 LIS를 구하려면 LIS를 기록해야한다.단순히 덮어씌운 값이 아닌 실제 증가하는 부분수열을 구해야하기에이전 값의 위치를 기록할 필요가 있다. 예제를 보면 10 20 10 30 20 50 이 입력되는데여기서 실제 LIS는 10 20 10 30 20 50이렇게 된다. 그럼 어떻게 추적을 해야하나 LIS 내에서 이분탐색을 하면서 새로운 값 추가가 아니면 기존 LIS 원소 내에 덮어씌운다. 때문에 LIS에 기록될 때 LIS에 기록된 위치에서 이전 위치의 값을 기록하는 것이다.단순히 -1~순차적으로 올릴 수 있지만 여기서는 prev만으로 바로 위치를 ..

1. 디스크의 읽기 방식디스크 같은 기계식 장치의 성능은 상당히 제한적로 발전데이터베이스의 성능 튜닝 == 디스크 I/O를 어떻게 줄일지 관건 HDD vs SSDCPU, 메모리 같은 주요 장치는 대부분 전자식 장치HDD는 기계식 장치이기에 데이터베이스 서버에서 항상 디스크 장치가 병목 발생 전자식 저장 매체인 SSD가 많이 출시되고 있으며 HDD와 같은 인터페이스 지원, 내장 디스크나 DAS, SAN에 그대로 사용 가능한마디로 DB서버로 사용하기 최적이며 HDD보다 훨씬 빠르다. (랜덤 I/O, 순차I/O) 둘다 1.2 랜덤 I/O 와 순차 I/O랜덤 I/O : HDD의 플래터(원판)를 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동 시킨 다음 데이터를 읽는 것순차 I/O : 디스크의..

🧫 문제 분석 ✔️ 출처행성 터널 플래티넘 5 📖 문제 최소 비용 MST 문제크루스칼로 풀면된다. 문제에서 x길이, y길이, z길이중 가장 작은 값을 비용으로 사용하고터널 N-1개를 생성한다. 이때 연결에 필요한 최소 비용 구하기 어떤 수열에서 오름차순 정렬시 자신의 인접 수가 가장 자신과 가까운 값이 된다. x, y, z 각각 기준으로 정렬하고인접 노드와의 거리를 구한후 우선순위 큐에 저장한다. 우선순위 큐에서 가장 작은 비용의 터널 건설 정보를 꺼내서 union-find set 을 사용하여 터널의 건설 여부를 체크하고 union으로 터널을 건설한 두 행성을 합치고 최종 비용을 더한다. 🔅 문제 풀이import java.io.*;import java.util.*;import java.u..

✔️ OIDC(OpenID Connect) 란 ? OpenID Connect 1.0은 OAuth 2.0 [RFC6749] 프로토콜 기반의 간단한 신원 계층입니다 . 클라이언트는 권한 부여 서버에서 수행한 인증을 기반으로 최종 사용자의 신원을 확인하고, 상호 운용 가능하고 REST 방식과 유사한 방식으로 최종 사용자의 기본 프로필 정보를 얻을 수 있습니다. - openid.net - OIDC(OpenID Connect)에서 로그인 제공자(예: 소셜 서버)는 공개 키를 JWKS(JSON Web Key Set) 형식으로 제공하며, 클라이언트는 로그인..

🧫 문제 분석✔️ 출처2048 (Easy) 골드 1 📖 문제 보드 크기가 N이며, 매 이동마다 변화하기때문에완전탐색 말고는 답이없는 것 같아서 완전탐색으로 풀이방향을 정했다. 문제에서 알고리즘 분류는 백트래킹 쪽이지만 나는 BFS로 풀었다.BFS + 완전탐색 이 문제에서 어려웠던 건 단순히 어떻게 한 방향으로 보내면서 합치고, 다를땐 이동시키는가 이다. 합쳐지지않은 위치를 추적한다. notUnionIdxnotUnionIdx ~ 현재 위치 전까지를 이동 가능한 곳을 탐색한다. 이때 같은 값을 가지고 있다면 합친다. 값을 2배로 하고 현재 위치의 값은 0으로 저장한다. 그리고 notUinonIdx 를 합친 위치의 다음 위치로 갱신한다. 각 방향은 4개의 함수로 각각 작성하였다. 🔅 문제 풀이impo..

🧫 문제 분석✔️ 출처Four Squares 실버 3 📖 문제DP문제 1~n-1까지의 four squares를 구하고 n의 four squares 를 구한다. 단순히 현재 자신의 최대 제곱근의 제곱을 자신의 수에서 뺀 나머지의 four squares를 이용하면 틀린다. 12의 경우최대 제곱근은 3이며 12 - 9 = 3 이므로 dp[3] 의 값을 더해주면 dp[3] (3) + 3^3(1) = 4개 로 최소가 된다 싶겠지만 2^2 + 2^2 + 2^2, 단 3개만으로 12를 완성할 수 있다. 때문에 해당 수의 1~최대 제곱근까지를 탐색해야한다. 점화식dp[i] = Math.min(dp[i - (j*j)] + 1, dp[i]) [i = 2~N , j = 1 ~ sqrt(i)] 🔅 문제 풀이imp..