혜유의 코딩신 만들기 프로젝트

맨 처음 bfs 기본 로직은 짰는데매번 이동할 때마다 그래프를 이동하는 게 아니라한 번의 턴 후에 그래프를 이동시켜야 하는데.. 이 부분 처리에서 헤맸다 ㅜㅜ또한 한 번의 턴에서는 중복 처리를 제거해야지 메모리 초과가 발생하지 않으므로한 번의 턴에서 visited로 중복 처리 해줘야 함!!! https://www.acmicpc.net/problem/169541. 그래프 이동 : 한 번의 턴 이후에 그래프 이동해줘야 하므로 q.size 구한 후에 반복문 이후에 그래프 이동!2. visited 중복 처리 import java.io.*;import java.util.*;public class Main { static char[][] graph; //인접한 한 칸 또는 대각성 이동+움직이지 않을..

N과 M의 범위 때문에 값을 일일이 구하면 시간초과가 발생한다따라서 dp를 이용해서 풀어야 한다는 것은 이해가 갔는데..일반적인 누적합을 이용하니 결과를 구할때에 N*M 시간복잡도가 나와아슬아슬하게 테케를 통과했다...출처: https://developerjisu.tistory.com/9위의 사진처럼 누적합을 구해야한다는 것을 깨달았다!1. 1행/1열은 단순 누적합ex. 1행이 1 2 3 4 -> 1 3 6 101열이 1 2 3 4 -> 1 3 6 102. 나머지 행/열부터는 위와 같은 방식으로 누적합을 구해야지표에 한번에 저장할 수 있다  [1차 풀이]import java.io.*;import java.util.*;public class Main { public static void main(St..

전형적인 백트래킹 문제이다.다만 각 순열의 결과를 자료구조에 저장하게 된다면 메모리 초과가 발생한다.맨 처음 정렬된 상태로 순열의 결과를 저장하려고 TreeSet 자료구조를 선택해서메모리 초과가 났다 ㅜㅜ 순열 결과를 저장하지 않고바로 sb에 담아서 출력하는 방식으로 수정해서 해결했다! https://www.acmicpc.net/problem/6443 첫번째 풀이import java.util.*;import java.io.*;public class Main { static String words; static boolean[] visited; static HashSet answer = new HashSet(); static void backtraking(String result, i..

https://www.acmicpc.net/problem/14890 문제를 이해하는 데에 시간을 꽤나 썼다..하지만 문제를 이해하면 조건만 잘 체크해주면 풀이가 수월하다 !2개의 경우로 나누어서 알고리즘을 짰다이 두 경우 인덱스 순서만 바꿔주면 되고 알고리즘은 동일하기 때문에 열을 이동하는 경우를 생각하면1열의 경우 1~N행 반복문을 돌면서 값이 달라지는 경우에 경사로를 만들 수 있는지 확인하면 된다값이 같은 경우는 생각할 필요 없으므로 continue예를 들어, 1행과 2행의 값이 2로 같다면 경사로를 만들 필요가 없으므로 건너 뜀! 따라서 값이 달라지는 경우 경사로를 만들 수 있는지를 체크해주는게 키포인트다!경사로 조건은 다음과 같다1) 경사로를 만드는 곳은 두 값의 차이 중 값이 작은 부분!2) 값..

dfs, bfs 개념만 알고 있으면 쉽게 풀 수 있는 문제다!다만 처음에 문제를 잘못 이해해서 마지막 테스트케이스가 이상하게 출력됐다..모든 정점을 다 방문했을 때에 dfs, bfs 종료되도록 코드를 구현했었는데마지막 케이스 같은 경우에는 정점은 1000까지 있지만연결된 정점 정보가 999,1000만 나오기 때문에 모든 정점이 다 주어진 것은 아니다. 따라서 종료 조건을 없애고, result를 배열에서 List로 자료구조를 변경했다 ! https://www.acmicpc.net/problem/1260  import java.io.*;import java.util.*;public class Main { static int N, M, V; static ArrayList[] graph; sta..

문제를 꼼꼼히 봐야한다!두가지를 간과해서 계속 틀림,,;;처음에 left, right 범위를 잘못 잡아줘서 계속 2N%..에서 틀림 ㅜㅜ'이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다.'라는 조건 때문에 최소와 최대를 left=1(0이면 x), right=L-1로 잡을 수 있다.또한 개수를 세는 것이므로 -1을 해줘야 한다처음에는 (arr[i+1]-arr[i])/mid로 해서 값이 잘 안나왔다 ..만약 mid=200이라고 하고 arr[1]=200, arr[0]=0이라고 하면cnt=1이 나오지만 최대값이 mid이므로 1개를 세울 수 없다..!따라서 (arr[i+1]-arr[i]-1)/mid 로 cnt를 세줘야 한다  https://www.acmicpc.net..

괄호가 없는 경우/있는 경우를 모두 고려해서 완전탐색으로 풀이하면 된다dfs를 생각하지 못해서 삽질하다가 다시 풀었다 ㅜㅜ두 가지 경우로 나뉘기 때문에 dfs를 이용해서 괄호가 없는 경우를 먼저 모두 구한 후있는 경우를 구하면 쉽게 풀 수 있다  https://www.acmicpc.net/problem/16637  import java.io.*;import java.util.*;public class Main { static int N; static int answer = Integer.MIN_VALUE; static ArrayList nums; static ArrayList operator; static void dfs(int depth, int result){ ..

https://www.acmicpc.net/problem/2003 left~right(이전 값까지) 합하며결과값이 M과 같은지 비교하도록 풀이했다.right 이전값까지 합해주므로 조건문을 잘 설정해야하는데처음에는 break문을 잘못 걸어줘서 계속 틀렸다 ㅜㅜ내가 찾은 반례는 다음과 같다! 10 8 3 1 1 1 1 1 1 2 2 2Answer: 4 (답)내 출력값: 3 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sys..

https://www.acmicpc.net/problem/13023 일단 문제가 잘 이해가 안가서 고생했다 ㅜㅜA,B,C,D,E는 임의의 기호이고친구 관계 5개를 찾아주면 된다..!  import java.io.*;import java.util.*;public class Main { static ArrayList [] relations; static boolean[] visited; static int flag = 0; static void dfs(int start, int cnt){ if(cnt==5 || flag==1){ flag = 1; return; } for(int i:relations[start]..

https://www.acmicpc.net/problem/15486 dp에 대한 연습이 많이 필요하겠다...일단 범위를 봐서는 완탐으로 풀면 시간초과가 날 것매일의 이익을 dp 배열로 두고 풀어야 한다 !! import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] T = new int[N+2]; ..