Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처장작넣기 골드 5 📖 문제 완전탐색 문제 문제를 이해하는데 조금 어려웠다.처음 위치한 SKH의 위치에 대해서는 장작을 넣지 않는다.그 다음 부터 넣는다. 화력감소때 넣은 장작의 위치는 감소시키지 않는 형태로 진행한다. 장작은 왼쪽, 현재, 오른쪽으로 3가지를 탐색한다. 시간복잡도가 약 O(3^T * N) 정도 나오는 것 같다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { // 24884번 장작 넣기 // T시간동안 최소 K개 유지 static class Node { int SKH; int[] arr; int time; public Nod..

🧫 문제 분석 ✔️ 출처레이스 골드 2 📖 문제 이분탐색 + 그리디문제 이분탐색의 대상은 두 심판의 거리다.M명 배치할 수 있는 심판의 거리를 구해서 심판을 배치하고 그 중에서 가장 가까운 거리가 가장 긴 심판 배치를 출력한다. 그런데 가장 긴 심판 배치는 심판 거리계산하면서 자동으로 마지막에 계산된 것이 가장 긴 거리가 된다. (더 긴 거리를 탐색해보기 때문) 비슷한 문제로 예전에 풀었던 공유기 설치 문제랑 비슷하다. 나의 경우심판 배치 거리 탐색 - 이분탐색적절한 심판 배치 위치 탐색 - 이분탐색 3중 while문으로 풀어서 좀 보기 안좋을 수 있다.심판 위치 배치는 for문으로 해도 된다. 🔅 문제 풀이import java.io.*;import java.util.*;public class ..

🧫 문제 분석 ✔️ 출처사수빈탕 골드 5 📖 문제 DP문제로 주어진 사탕 바구니 위치로 이동하며 최대 개수를 구하는 문제 한 번 움질일때마다 사탕바구니의 사탕이 -1이 된다. 사탕 바구니를 x,y로 오름차순 정렬해서 DP + DFS 탐색한다. 다른 사람풀이를 보니 bottom-up 으로 푸는 방법도 있다.🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int n, m; static int[][] arr; static int[][] dp; public static void main(String[] args) throws IOException { BufferedReader br = new..

🧫 문제 분석 ✔️ 출처도미노 (Small) 골드 1 📖 문제 DP 풀이 문제였는데나는 우선순위 큐로 풀었다. 각 도미노가 넘어뜨릴 수 있는 최대개수를 구하고우선순위 큐에 넣은 다음 가장 많이 쓰러뜨린 도미노 먼저 꺼낸후해당 도미노를 넘어뜨렸을 때 넘어진 도미노들을 방문체크한다.이를 반복하면 된다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static class Domino { int x, h; long left, right; public Domino(int x, int h) { this.x = x; this.h = h; ..

🧫 문제 분석 ✔️ 출처화살표 미로 (Easy) 골드 3 📖 문제 BFS 탐색 문제나는 끝지점에서 상하좌우의 방을 탐색후 현재 방을 가리키는지 체크하고현재 방을 가리키지 않았다면 주문서를 써서 방향을 바꾸고 바꾼 방향으로 현재 방을 가리킬 수 있는지 확인후 이동하는 식으로 구현하였다. 🔅 문제 풀이import java.io.*;import java.sql.SQLOutput;import java.util.*;public class Main { static int R, C, K; static char[][] map; static boolean[][][] visited; static int[] dr = {-1, 0, 1, 0}; static int[] dc = {0, 1..

🧫 문제 분석 ✔️ 출처내일 할거 골드 5 📖 문제 문제를 제대로 안읽어서 한 번 틀렸다.내일 부터 연속으로 최대로 놀 수 있는 기간을 출력하는 건데최대 놀 수 있는 기간을 출력해버렸다... 과제 마감 시간을 기준으로 내림차순 정렬하여과제 시작일을 구하고이전 과제 시작일과 비교해서 현재 과제 시작일을 배치한다. 다 구한 후 마지막으로 구한 이전 과제 시작일 - 1 이 내일부터 놀 수 있는 기간이다. 🔅 문제 풀이// 코드 내용import java.io.*;import java.util.*;public class Main { // 계산은 long static class Assigment implements Comparable { int d, t; public Ass..

🧫 문제 분석 ✔️ 출처벼룩 시장 골드 3 📖 문제 두사람의 거리 * 배달하는 벼룩의 수 의 합을 구하고, 그 중 최소가 되는 합을 구하는 그리디 문제제일 좋은 것은 가장 가까운 곳에 배달하는게 이득이다.따라서 판매자 즉, 가게와 고객을 따로 순서대로 받고 하나하나씩 거래하면된다. 투포인터로 풀었다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { // 계산은 long public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

🧫 문제 분석 ✔️ 출처N포커 골드 2 📖 문제 포함 배제 원리에 대해 배우게 되었다. 말그대로 여러 집합을 합칠때 중복을 빼는 것이다. 짝수 집합일 경우 빼주고홀수 집합일 경우 더한다.세 집합 A,B,CA, B, CA,B,C 면:→ 더하고 빼고 반복. 벤다이어그램으로 봤을때2번째 짝수번째 빼기를 보면3번 빼서 AnBnC가 없어진다따라서 세 집합의 교집합을 더한다. 최종적으로 중복ㅇ벗는 하나의 영역만 계산된다.|B| + |C| + |D| 이경우 BnC가 2개AnB 2개AnC 2개 때문에 1개씩 빼줌 하지만 이러면 AnBnC가 사라짐AnBnC 더함 최종적으로 중복없는 합 집합 생성 🔅 문제 풀이import java.io.*;import java.sql.SQLOutput;import java.uti..

🧫 문제 분석 ✔️ 출처개미 골드 3 📖 문제 트리로 풀어야하는데 Set이랑 문자열로 풀었다. 레벨 별 Set을 만들고 Set에 현재 레벨의 문자열을 체크하면서 추가한다. Tree 를 이용한 풀이를 꺼렸던게 정렬때문이였는데 생각해보니 TreeMap이 있었다.노드 만들어서 자식을 TreeMap에 넣고 진행하면 될 것 같다. 🔅 문제 풀이 [Set 풀이]import java.io.*;import java.util.*;public class Main { static final int MAX_LEVEL = 15; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe..

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