Mini

https://leetcode.com/problems/majority-element/description/ * 풀이1절반이상인 원소가 반드시 존재함을이용정렬 -> 중간지점의 원소가 다수원소임class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; }}O(nlgn) * 풀이2투표 알고리즘 이용 O(n)class Solution { public int majorityElement(int[] nums) { int king=nums[0]; int cnt=1; for(var num : nums){ ..

https://www.acmicpc.net/problem/10653* 시도1완탐) 500 C 250 -> 건너뛸 체크포인트 고르기 -> 불가 * 풀이dp(idx, cnt) : idx, 점프횟수 그때 최소비용이때, OX 퀴즈로 하면 안된다.nxt 후보들에대해 한번에 점프하는 식으로 완탐해야 구현이 쉬워진다.정답코드import java.util.*;class Pair { int y; int x; Pair(int y, int x) { this.y = y; this.x = x; }}public class Main { // 인덱스 i, j개 를 스킵 했을때, 그때 최소거리 static int dp[][] = new int[504][504]; stat..

https://leetcode.com/problems/linked-list-cycle/description/풀이1/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public boolean hasCycle(ListNode head) { HashMap m = new HashMap(); while(head!=null){ if(m.containsKey(hea..

https://school.programmers.co.kr/learn/courses/30/lessons/389479 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 풀이필요할때마다 증설하는게 최적인가? 그런듯.귀류법 증명) ... class Solution { static int[] need = new int[25]; static int[] server = new int[25]; public int solution(int[] players, int m, int k) { int answer = 0; int n = players.length; ..

https://school.programmers.co.kr/learn/courses/30/lessons/389480?language=java 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 내풀이A가훔치기, B가훔치기 OX퀴즈 -> 2^40 -> 시간초과 -> dp 필요int dfs로 변경 && 메모참고로 dp 초기화부분을 상수시간 최적화해야 통과함..? 맞게푼건지? (재귀dp 억까?)import java.util.*;class Solution { static int n,m,ret=Integer.MAX_VALUE; // static int dp[][][] = new int[44][124][1..

https://www.acmicpc.net/problem/20181* 시도1완전탐색방법상태 : index, 축적된에너지, 얻은탈피에너지, 이전에얻었는지(한번먹으면 계속먹어야함)O X로 완전탐색import java.io.*;import java.util.*;public class Main { static long ret, n, k; static long[] dp = new long[100000+4]; static ArrayList arr = new ArrayList(); // 축척된에너지, 얻은탈피에너지 static void dfs(int idx, long acc, long tal, boolean flag) { if(acc >=k){ tal += ..

https://www.acmicpc.net/problem/20166* 시도110*10 이니까 그냥 dfs로 완탐하면 될듯? -> 시간초과100칸마다 각각 8방향 && depth 5제한 * 풀이미리 계산후, 쿼리하는 방식으로 개선시간복잡도 : 3,276,800(3백만) + 1000(조회)정답코드dfs가 과거풀이,dfs2가 캐시 미리계산 코드.string을 인자로 넘기는게 범인이 아니었음.import java.io.*;import java.util.*;public class Main { static int ret, n, m, k; static char[][] arr = new char[14][14]; static int[] dx = {0, 1, 0, -1, -1, 1, -1, 1}; ..

https://www.acmicpc.net/problem/20165* 시도1table을 2개 놓고 dfs?k칸을 어떻게 처리?배열에 k만큼 넘어졌다고 표시하면?if(dir=='E'){ for(int i=0;i 0){ cnt++; arr[y][x+i]=0; }}문제 : 다음에 언제 멈출지 계산하기가 매우 복잡해짐, dfs는 한칸씩 보는건데 이러면 다음상태에 영향을 끼쳐버림.실제로 멈춰야되는데 진행이 되는 문제 발생* 풀이일단 배열을 원본, 백업으로구분삭제된것 : 원본에 높이를 0으로 둠remain이라는 상태 추가remain이 0이되면, 정답갱신, 리턴remain은 계속 MAX로 갱신필요. (내가더 큰경우 vs 엄청큰게 나오는경우)remian을 직전값 vs 새값 비교로..