Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처사회망 서비스 (SNS) 골드 3 📖 문제 DP 문제트리를 이용한 DP 문제는 처음이라 좀 어려웠다 처음에는 엣지가 많은 노드 순으로 연결 해제 여부를 따지며 선정하면 되지않나 싶었는데불가능한 케이스가 있어서 바꿨다. 현재 노드를 얼리 아답터로 선정할지 안할지에 대해서 탐색하면된다.DFS+DP 식으로 풀어서 별로일 수 있다. 또한 입력을 받을 때 주의해야한다.방향성을 가지면 안되며 양방향으로 트리를 만들어야한다.그 이유는 단방향시 루트를 가지는 트리가 되는데 이러면 방향에 따라 값이 달라진다. 51 52 12 32 4이런 입력이 들어오면 1을 루트로 설정시2를 탐색할 수 없다. 때문에 양방향으로 설정해야한다. 루트를 1 기준으로 입력이 들어온다는 생각때문에이런 실수를 했다...

🧫 문제 분석 ✔️ 출처열쇠 골드 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만으로 바로 위치를 ..

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

🧫 문제 분석✔️ 출처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..

🧫 문제 분석✔️ 출처트리의 순회 골드 1 📖 문제이진 트리 (완전 이진 트리 X) 이기에 한쪽으로 기울어긴 트리가 가능하다. 때문에 직접 배열로 이진트리를 만들 생각을 하면 안된다. 순회 특징후위 순회는 마지막이 항상 중앙노드다. 중앙 순회는 중앙노드 기준으로 왼쪽, 오른쪽 서브트리를 갖는다. 중앙노드, 서브트리, 왼쪽 끝 오른쪽 끝 노드를 알 수 있는데 어떻게 해야 전위순회를 할 수 있을까 분할 정복을 이용하면 쉽게 알 수 있다.후위 순회의 마지막 노드는 항상 중앙노드이므로 중앙 노드를 얻고 이 노드의 중앙 순회에서 위치를 얻은다음 중앙 순회에서 중앙 노드를 기준으로 왼쪽을 서브트리, 오른쪽을 서브트리로 나눠서 분할한다. 나눠지면 또 그 서브트리에서의 후위 순회의 마지막 노드는 그 서브트리의 중..