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

문제는 전형적인 bfs 문제이지만 세부 조건을 잘 처리하지 않으면시간이 오래 소모될 수 있다 ㅜㅜ나는 다음과 같은 조건을 간과해서 삽질 엄청 했다..;; 1. n과 m의 순서 주의x좌표: 0~my좌표: 0~n 이다..그리고 맨아래 x좌표=0이고 위로 갈수록 x값이 커지는 구조2. 두번 점프를 할 수도 있고 안 할수도 있음나는 다익스트라를 이용해서 최소 비용을 갱신하는 식으로 로직을 짰다이 때에 최소거리(비용)을 나타내는 배열을 삼차원으로 처리해줘야 함dist[x][y][0] : 두번 점프 안한 경우dist[x][y][1] : 두번 점프 한 경우 import java.util.*;class Solution {static int[] dx = {0,1,0,-1,0,2,0,-2};static int[] dy ..

맨 처음 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){ ..

일단 처음에 문제가 잘 이해가 가지 않아서 오래 걸렸다..도시의 개수 N이 연결되어 있는지의 대한 정보가 N*N개 입력,여행 계획에 대한 정보를 M개 입력하는 것이다..또한 순간 착각해서 A->B, B->A를 같은 경우로 생각해서 ArrayList에 양방향으로 추가해줬는데..다른 경우이므로 따로 List에 추가해주지 않아도 된다 !! 이 문제는 bfs로 풀이해도 되지만union-find 알고리즘으로 푸는 게 더 수월하다 ! https://www.acmicpc.net/problem/1976   import java.io.*;import java.util.*;public class Main { static int N, M; static int[] parent; static void union..

리스트를 처음에 정렬해야 함lost와 reserve 모두에 해당하는 학생 먼저 판단한 후에나머지 학생들을 판단해야 한다.나 같은 경우에는 빌려준 학생 처리를 -1로 하고 싶지 않아서int[]에 있던 데이터를 ArrayList에 넣고빌린 경우에 리스트에서 값을 remove로 제거하도록 코드를 구현했다.but.. remove로 값을 제거하는 경우에 index도 함께 -1 update 해줘야 함..(이 부분 놓쳐서 계속 부분점수 나왔다 ㅜㅜ) https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=java# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이..