목록Algorithm (418)
Mini
[맞음] 프로그래머스 서버증설횟수 // 배열, 구현
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; ..
[세모] 프로그래머스 완전범죄 // dp, void dfs dp
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..
[틀림] 백준 20181 꿈틀꿈틀 호석 애벌레 // 투포인터 dp
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 += ..
[틀림] 백준 문자열 지옥에 빠진 호석 // 문자열, 먼저계산 dp, dfs
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}; ..
[틀림] 백준 20165 도미노장인 // dfs, 구현
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 새값 비교로..
[틀림] [자바] 프로그래머스 수식최대화 // 문자열, 구현, 링크드리스트
https://school.programmers.co.kr/learn/courses/30/lessons/67257 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 시도1배열에 숫자, 연산자를 넣고갱신을 어떻게 할건지 문제발생, 해당 연산자가 있으면, i, i+1 배열의 값을 바꿔주는 방식?값전파문제 발생 , 완료된 연산자의경우 , i+1을 i 값으로 채워주기?끝나면 마지막 남은숫자가 정답?맨 처음에는 삭제가 쉬운 링크드 리스트로 해볼까 생각은 했음.but, 복잡할것 같아서 배열의 값을 바꾸는 방법으로 시도해봄실패 * 풀이그냥 ArrayList를 쓰던지, LinkedList를 쓰던지 실제 삭제를 해주면 ..
[세모] 프로그래머스 가장많이 받은 선물 // 구현, 해시맵, 문자열을 인덱스로
* 풀이1일단 문제를 읽으며 도식화를 진행.문제의 예시에서 힌트를 얻어, 그래프형태로 만들기graph[i][j] : i가 j에게 준 선물 수문제1 : string을 배열의 인덱스로 쓰려면?map을 이용해 매핑문제2 : 둘다 주고받지않는것을 어떻게 판단?graph[i][j], [j][i]가 둘다 0인경우처음 제출 코드 (답이 2배가 되는 문제)import java.util.*;class Solution { public int solution(String[] friends, String[] gifts) { int answer = 0; int n = friends.length; HashMap m1 = new HashMap(); //str to index..
[틀림] 프로그래머스 미로탈출 // 상태기반 다익스트라, 비트마스킹을 이용한 다익스트라
https://school.programmers.co.kr/learn/courses/30/lessons/81304 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr * 시도1trap을 만날때마다, 실제로 그래프를 수정해주는 방법실패import java.util.*;public class A{ int node; int weight; int state; //trap이 발동되었는지 A(int node, int weight, int state){ this.node=node; this.weight=weight; this.state=state; } ..