Meluu_의 코딩 공부 일지

모두 0으로 만들기 [자바]

🧫 문제 분석✔️ 출처모두 0으로 만들기 level 3📖 문제 dfs로 푸니 메모리 제한사항이 빡빡해서 6,7번에서 런타임 예외 (stackoverflow)가 터졌다.변수를 static으로 선언, iterator를 사용하지 않는 일반for문 사용 우선 트리에서 가중치가 가장 작은 노드를 기준으로DFS 탐색해서 리프노드부터 값을 넘기면서 연산 횟수를 카운팅하면된다. 그리고 특정 상황 즉, 모두 0이거나, 불가능한 경우는 미리 처리한다. a의 모든 합이 0이 아니면 절대로 모든 정점의 가중치를 0으로 만들 수 없으므로 바로 -1 반환 a의 모든 요소가 0이면 0 반환 재귀를 통한 dfs 말고 stack으로 dfs를 구현하면 더 안정적일 것 같다. 🔅 문제 풀이import java.util.*;cla..

봉인된 주문 [자바]

🧫 문제 분석✔️ 출처봉인된 주문 level 3📖 문제 설계는 잘했는데 구현이 조금 어려웠다. 1. 일단 bans을 무시하고 전체 주문서를 규칙순서대로 뒀을때 n번째 주문서를 찾는다.2. n번째 주문서보다 사전 순서가 앞서는 bans 주문서가 있다면 개수를 카운트한다.3. 2번에서 카운트한 개수만큼 n = n + cnt로 갱신하고 다시 2번을 진행한다.4. 카운트가 0이라면 ban을 모두 적용한 n번째 주문서이므로 반환한다. 예시에서 30번째 주문서를 찾는데ban을 적용하지 않고 주문서를 규칙에 따라 정렬했을 때 30번째는 "ad" 이다.그런데 그 중에 ban 문자 d, e, aa, ae 가 있으므로 이 문자들은 건너뛰고 순서를 할당했을 것이다.ban을 적용하면 해당 4개의 문자만 넘어가면되니 n +..

🧫 문제 분석✔️ 출처최적의 행렬 곱셈 level 3📖 문제 DP로 풀은 문제행렬의 곱을 복습하자면 A(3X5) 와 B(5X7)의 크기의 행렬이 있을때 구 행렬을 곱하면AB = 3X5X7 이된다. 행렬 A, B, C... 이렇게 있을 때ABCD를 만드는 조합은ABC DAB CDA BCD 이렇게 3가지 가 있고ABCDE는 A BCDEAB CDEABC DEABCD E4가지가 있다 여기서 규칙성을 찾을 수 있고 이를 점화식으로 나타낼 수 있다.시작과 끝을 지정하고, 중간을 지정해서 분할한 후 최소값을 찾는 것이다.// A: s,mid까지 곱한 행렬의 행 크기, B: mid+1,e 까지 곱한 행렬의 열 크기DP[s][e] = min(DP[s][mid] + DP[mid+1][e] + multiply(A..

🧫 문제 분석✔️ 출처2차원 동전 뒤집기 level 3📖 문제 DFS 로 풀었지만 정석은 bitmask인듯하다. 행 기준으로 현재 행을 뒤집는 경우와 뒤집지 않는 경우를 탐색하여 뒤집는 행을 갖는 조합을 만들고 열 기준으로도 조합을 만들어서 최종적으로 조합을 적용해 동전들을 뒤집고, target과 비교해서 맞다면 뒤집기 카운트와 비교해서 최솟값을 찾는다. 이문제를 풀면서행과 열을 왔다갔다하면서 뒤집어야 나올 수 있는 target이 있을 줄 알았는데 그게 아니였다. 궁금해서 gpt 에게 물어봤다.begin[i][j] ^ R[i] ^ C[j] == target[i][j] 🔅 문제 풀이import java.util.*;class Solution { static int[][] otarg..

🧫 문제 분석✔️ 출처디스크 컨트롤러 level 3📖 문제 우선순위 큐를 이용한 시간 관련 문제 입력이 요청 시간 순으로 들어오는게 아니라서 요청 시간별로 정렬해주고우선순위 큐는 문제에서 말한대로 정렬해준다. 현재 시간에 요청된 작업이 있다면 우선순위 큐에 넣고 작업을 꺼내서 처리한다. 만약 작업이 없다면, 즉, 현재 시간까지 요청된 작업이 없다면 현재 작업 인덱스의 작업 요청 시간으로 현재시간을 변경한다. 🔅 문제 풀이import java.util.*;class Solution { class Job { int num, req, cost; public Job(int num, int req, int cost) { this.num..

🧫 문제 분석✔️ 출처연속 펄스 부분 수열의 합  level 3📖 문제 문제를 잘못 이해해서 삽질했다. 펄스 수열을 연속 수열에 패턴대로 곱했을때 최댓값이 나오는 연속 펄수 부분수열을 구하는 것이였다. 나는 잘못 이해해서 펄스 수열 처럼 수열의 연속 부분수열이 3,-6,1,-4 이런식으로 1,-1 이런 패턴이 유지되는 연속 부분 수열에만 펄스 부분 수열 1,-1을 곱해서 양수가 되는 것만 합쳐서 최댓값을 구했다. 당연히 틀렸고 이 문제는 사실 펄스 수열은 페이크고 누적합 문제이다.   주어진 수열에 펄스 수열 패턴을 곱해서 2개의 수열로 만든다.1,-1 패턴을 곱한 수열-1, 1 패턴을 곱한 수열 이제 누적합으로 풀면 된다.  나는 누적합 하면서 최댓값과 최솟값을 구하고  최댓값 - 최솟값을 하되 최..

🧫 문제 분석✔️ 출처섬 연결하기 level 3📖 문제 다익스트라로 했다가 생각해보니 이건 최단경로가 아닌 최소비용으로 연결하는 거였다.알고리즘 시간때 배웠던 걸로 기억하는데 최소신장트리 였던걸로 기억한다.  서로소 집합, 유니온, find 등 같은 걸 배웠었는데 기억이 안나서 결국 찾아봤다. https://sskl660.tistory.com/72 자세한 이론은 위 블로그 참조 핵심은 최소 비용으로 정렬하고 연결하는 두 노드(섬)의 부모가 서로 달라야한다. (사이클 방지, 최소 신장 '트리' 이기에 사이클은 없어야한다. )이때 find 메서드를 사용해서 각각 부모를 찾는다. 두 노드의 부모가 서로 다르다면 union 메서드를 사용해서 두 노드 중 부모가 더 작은 곳으로 편입된다. 이때 실제 원소가 편..

🧫 문제 분석✔️ 출처기지국 설치 level 3📖 문제 간단하면서도 생각할게 좀 있는 문제였다.N은 2억이므로 배열을 만들 생각은 하면 안된다.  stations가 최대 10만이므로 stations을 이용해서 푸는 문제이다.  나는 우선 처음 기지국의 전파범위와 처음 아파트 사이의 거리를 구하고 그 거리가 0이하가 아니라면 그 거리를 새로운 기지국을 설치했을때 전파범위로 나눈 값을 더했다.  그리고 기지국 사이에도 위와같이 연산을 해주고 마지막아파트와 마지막 기지국 사이의 거리도 동일하게 계산해주었다.   이번에 하면서 Math.ceil 과 직접 나누기와 나머지연산을 더하는 식으로 2가지로 해봤는데좋은 경험을 한 것 같다. - 664 / 667 을 연산했을 때 -0.9955 정도의 값이 된다.  Ma..

🧫 문제 분석✔️ 출처단속카메라 level 3📖 문제 탐욕법 문제로예전에 포스팅했던 요격시스템과 비슷한 문제다.  시작지점을 기준으로 정렬하고 (다음 차량의 시작지점 이때 다음 차량의 끝지점이 기준 차량의 끝지점보다 작다면 기준 차량의 끝지점을 갱신한다.  왜냐하면 최소한의 카메라를 설치해야하기에 최대한 겹치는 부분에 카메라를 놓아야한다. 이때 끝지점이 제일 작은 것을 기준으로 그 안에 겹치는 부분이 최대 중복 차량의 위치이며카메라 설치 위치이다. 잘 모르겠다면 요격시스템 포스팅을 보길 바란다.  🔅 문제 풀이import java.util.Arrays;class Solution { // 고속도로 진입 지점을 기준으로 정렬 // 끝 범위 안에 시작지점이 있으면 하나로 취급 pu..

🧫 문제 분석✔️ 출처숫자 게임 level 3📖 문제 B팀은 A를 이길 수 있게 순서를 바꾼다. 원소가 같다면 승점을 얻지 못한다. A팀에 원소에 맞게 B팀 원소를 바꾸면 된다.  오랜만에 투 포인터 문제가 나왔다. A팀과 B팀을 오름차순 정렬한다. (어짜피 A팀은 순서가 있다 하더라도 B팀은 A팀에 이기도록 순서를 바꿀 것이기에 정렬해도 상관없음) 그리고 각각 원소를 비교해서 B가 더 크면 승점을 얻어주면 되는 간단한 문제이다. 🔅 문제 풀이import java.util.Arrays;class Solution { // 승점만으로 답 판단, B팀은 순서를 바꿀 수 있음 public int solution(int[] A, int[] B) { int answer = 0; ..