Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처최적의 행렬 곱셈 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📖 문제생각보다 재밌는 문제였다. 입력으로 노드의 좌표값만 주어지고 해당 조건에 맞게 이진트리를 만들어야하는데 최상위 루트 부터 시작해서 자식노드를 추가하는 식으로 생각했다. 따라서 y값을 기준으로 내림차순 정렬하고, 같다면 x값을 기준으로 오름차순 정렬한다. 좀 복잡한데 코드를 보면 그나마 이해가 된다. 자식을 추가할때 주의할 점은다른 노드가 자식으로 가져야할 노드를 자식노드로 설정하게 될 때도 있다.이를 방지하기 위해서는 추가가능한 범위를 지정해줘야한다. 즉, 각 서브트리의 범위 x의 범위를 지정해서 해당 범위 안에 든 노드라면 자식으로 추가하는 것이다.범위는 트리 구성 조건 5,6번을 참고하면 된다. 예시) 위와 같은 케이스가 발생할 수 있다..

🧫 문제 분석✔️ 출처[1차] 셔틀버스 level 3📖 문제 시간 문제콘이 셔틀을 타되 최대한 늦게 탈 수 있도록 하면된다. 같은 시각대에 타면 해당 시각대의 맨 마지막에 타게되는 점을 조심하면 된다. 각 회차별 시간대에 따라 탈 수 있는 인원들을 태우고현재 셔틀에 탄 인원이 다 같은 시각이면 (해당 시각 - 1분) 에 타고시각이 다 다르면 (제일 늦은 시각의 -1분)에 타면 된다. 🔅 문제 풀이import java.util.*;class Solution { // 도착 시간중 제일 늦은 시각 //같은 시각에 도착한 크루 중 대기열에서 제일 뒤 // 23:59분 전까지 public String solution(int n, int t, int m, String[] t..

🧫 문제 분석✔️ 출처디스크 컨트롤러 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📖 문제 모든 경로를 탐색해서 사전순으로 앞서는지 확인하는 문제 간과한 것은 같은 경로가 여러개 있을 수 있다는 것이다. ICN -> SFO, ICN -> SFO 이렇게 같은 경로가 여러개로 입력될 경우가 있다. 문제에서 따로 중복에 대한 내용이 없으면 항상 중복 케이스가 있다고 생각하는게 좋다. 그렇다면 어떻게 문자열로 된 그래프에서 방문처리를 할까 나의 경우 (현재 공항 + 다음 공항의 idx )를 key값으로 사용하여Set에서 방문처리를 하였다. 이부분만 빼면 딱히 어려운 문제는 아니다. 🔅 문제 풀이import java.util.*;class Solution { static Map> graph; static int n; // 총 방..

🧫 문제 분석✔️ 출처보석 쇼핑 level 3📖 문제 투 포인터 문제로 모든 종류의 보석을 포함하는 가장 짧은 연속된구간을 찾는 문제다. 먼저 문제에서 보석의 종류의 개수를 알려주지 않으므로 따로 카운트한다.map 자료구조를 사용해서 현재 까지 구간에 어떤 보석이 몇개씩 있는지 저장하면서 체크한다. 현재 구간의 보석 종류 개수가 모든 보석의 종류 개수와 같다면구간 줄이기를 시도한다. 현재 앞쪽 포인터 (start)에 있는 보석이 map에서 개수가 1개면 오히려 구간을 늘려서 다음 탐색때 더 줄 일 가능성을 늘린다. 1개가 아니라면 s를 한칸 더 땡겨서 구간을 줄이는 식으로 풀어나간다. 테스트 케이스A B B C D As e처음에는 여기까지 탐색하고 map.size() == 모든 보석 종류 ..

🧫 문제 분석✔️ 출처다단계 칫솔 판매 level 3📖 문제seller가 판 이익의 10%을 계산자신이 90%을 먹고 자신의 추천인 즉, 부모에게 10%을 준다. 간단하게 자신의 부모를 가지는 배열을 생성하고판매금에 대한 이익 90%을 가지고 부모에게 10%을 줘서 처리하면된다. 여기서 간과한게 있는데 처음에는 그냥 판매자의 최종 판매액을 합산해서 한 번에 계산하는게 빠르지 않을까 싶었는데틀렸다. 생각해보니 문제에서 원단위 즉, 1원 미만은 절삭한다하였다. 홀수 금액의 경우 합산시 짝수가 될 수 있다. 즉 A, B 금액 둘다 홀수라서 1원 미만은 절삭될 수 있고 A+B를 합쳐서 계산시 짝수가 될 경우 위의 1원 미만 절삭이 사라져 오히려 더 큰 값이 분배될 가능성이 있다. 즉, 홀수 금액이 합..

🧫 문제 분석✔️ 출처K진수에서 소수 개수 구하기 level 2📖 문제 간단한 문제인데 소수 판별 문제를 오랜만에 만나서 리마인드 겸 포스팅한다. 조건이 뭔가 4가지 경우를 다 체크해야할 것 같지만 그렇지 않다111011101110을 기준으로 진수를 나누면1가지의 조건식만 적용된다첫번째와 마지막은 각각 P0, 0P가운데는 무조건 0P0이 적용된다.이들을 하나하나 다 소수검증해준다. 문제에서 k진법으로가 아닌 10진법으로봤을때 소수여야한다고 되어있는데 이는211 일 경우 10진수 그대로 211이 소수이냐는 것이다.. 4번 조건 P의 경우 0을 기준으로 진수를 나눴을떄각 자릿수에 0이 하나도 없어야하므로 그대로 나온다.따라서 똑같이 적용하면된다. 🔅 문제 풀이import java.util.*;cla..

🧫 문제 분석✔️ 출처양국대회 level 2📖 문제 최대 점수이면서 가장 낮은 점수를 가장 많이 맞춘 스코어 배열을 만들어야하는 문제 최대 점수를 만들되 어피치가 가진 점수를 빼앗기 위해서는어피치가 맞춘 화살 개수보다 더 많이 맞춰야 해당 점수를 획득할 수 있다. 라이언이 각 점수를 화살로 맞추는 경우와 맞추지 않는 경우 2가지를 dfs로 탐색하여 풀었다.(최대 점수가 10점이기에 시간복잡도는 길어야 O(2^11)이다) 그리고 최대 점수를 갱신하고, 해당 점수를 얻은 화살 맞춘 스코어 배열을 list에 저장하면서 진행한다. 같은 점수라도 다 저장한다. 탐색이 끝나면 정답 후보를 탐색한다. 같은 점수인 정답 후보 중 가장 낮은 점수를 더 많이 획득한 경우를 구한다. 구한 정답 후보에서 안쏜 화살 개..