정들었던 Boj가 서비스 종료한다고 해서 마지막 날 기록 대학 생활 그래도 유일하게 공부(?) 비슷하게 꾸준히 했었던 게 백준 알고리즘 문제 풀기인데 너무 아쉽다. 아직 코테를 완전히 뚫을 정도로 실력이 좋지는 못하지만, 그래도 어느정도 기본기는 백준 덕분에 갖췄다고 해도 무방한듯 하다. 고마웠어!
[ 문제 ]https://www.acmicpc.net/problem/15684 간단하게 설명하면 일반적인 사다리게임에서 추가적으로 최대 3개의 선을 추가하여 모든 i번 세로선들의 결과가 i로 나오게 만드는 최소 가로선 추가 개수를 출력하는 문제이다. [ 구현 ] 적용시킨 알고리즘은 백트래킹(Backtracking) 기반 DFS로 조합을 탐색하는 완전탐색(Brute Force) 우선 주어진 가로선들의 입력을 받았을 때map[a][b] = 1; // 오map[a][b + 1] = -1; // 왼와 같은 방식으로 사다리를 구현해주었다. map[a][b] = 1만 해두고, 조건 검사시에 map[a][b - 1] ==1 인지 함께 검사해주는 방식으로 구현해도 무방할 듯 하였지만, 뭔가 이 방식이 더 깔끔해보여서 ..
[ 문제 ] [ 구현 ] 다익스트라를 적용해서 풀되, 경로 추적을 위한 parent 배열을 하나 따로 관리해주면 되는 문제이다.경로 복원을 할 때는 목표 지점에서부터 반대로 탐색하게 되므로 Stack(Deque)을 통해 뒤집어서 출력해주면 된다. [ 코드 ] import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static final int INF = Integer.MAX_VALUE; static int n, m; static int goalS, goalE; static List> graph = new Arr..
[ 문제 ][ 구현 ] 최근 트리 dp 문제들을 풀어보기 시작했다.기본적으로 트리가 모든 노드들이 연결된 사이클 없는 그래프이므로루트에서부터 dfs를 통해 탐색하되, 해당 서브트리를 기준으로 해당 시점에 최적이라고 생각되는 부분을 기록해서 전체를 이룬다.이 문제의 경우 전체 노드들을 선택적으로 방문하여더해서 최대를 만들어야 했으므로해당 서브트리에 속한 노드들의 최대 합이 음수인 경우는 최적의 해 구성에서 제외하도록 신경써주는 것이 포인트였다. dp[idx] = Math.max(dp[idx], dp[idx] + dp[adjIdx]);이 부분에서 현재 노드를 루트로하는 서브트리의 노드들의 합을 구성할 때, 자식을 루트로 하는 서브트리의 노드들의 합이 어떻게 해도 음수인 경우 최적의 해 구성에서 제외하는 것을..
[ 문제 ] [ 구현 ] 주사위의 형태를 어떻게 관리하고동서남북 이동에 따라 어떤 식으로 위치가 변화하는지만 관리해주면 되는 문제지만 좀 번거로웠다. 0(윗면), 1(바닥면), 2(북쪽면), 3(남쪽면), 4(동쪽면), 5(서쪽면)으로 주사위 배열의 인덱스를 잡아두고 입력에 따라 동서남북으로 이동했을 시 어떻게 해당 주사위의 면이 옮겨가는지를 일일이 생각해주었다.ex) 동쪽으로 이동할 경우 : 윗면 -> 동쪽면, 동쪽면 -> 바닥면, 바닥면 -> 서쪽면, 서쪽면 -> 윗면 정리한 이동 로직에 따라 범위가 벗어나지 않는지 체크하고 괜찮다면 해당 위치로 이동 +이동한 후의 주사위 윗면을 출력해주면 된다. [ 코드 ]import java.io.BufferedReader;import java.io.IOExcep..
[ 문제 ] [ 구현 ] 잘 모르겠어서 gpt한테 힌트달라고 했는데도 점화식 이해하는데 좀 애먹었다..힌트보고 이해한 다음에 코드는 손수 짰는데, 배열 크기 관련해서 신경써줘야하는 부분이 좀 있어서 디버깅하면서 고쳤다. dp[i] = 시각 i부터 N까지 시작할 때 얻을 수 있는 최대 거리 (이때 지침 지수는 0)로 잡고누적합을 통해 필요한 구간의 합을 계산하였다.이때 필요한 구간의 합이란 연속으로 달릴 구간을 의미한다(i ~ i + L - 1)dp자체가 bottom-up 방식이 아니라 top-down 방식으로 내려가는 형식이며L이 가지는 제한 조건 -> L 최종적으로 핵심이 되는 점화식은dp[i] = Math.max(dp[i+1], sum(i ~ i + L - 1) + dp[i+2L])이다. 우선 d..
[ 문제 ] [ 구현 ]벽을 3군데 세우는 부분은 dfs + backtracking으로 처리하고,벽이 세워진 이후에 bfs로 넘어가서 바이러스가 퍼트려지도록 시뮬레이션을 돌리고 안전한 구역의 최대를 저장해두는 식으로 풀었다. [ 코드 ] import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { static int n, m; static int[][] map; static BufferedReader br..
[ 문제 ][ 구현 ]가능한 색종이의 최소 크기를 구해야하는 것이므로 이분탐색 + 그리디 느낌으로 푸는 문제 색종이를 반드시 도화지의 밑변에 맞추어 붙이는 것이므로,앞에서부터 색종이를 붙여나가면서 주어진 색종이의 개수로 전체 잘못된 영역을 커버할 수 있는지 확인하고이분탐색을 통해 색종이의 개수를 늘리거나 줄인다. 색종이를 밑바닥부터 댔을 때, 높이가 부족한 경우 불가능하므로 바로 false를 리턴 최소 색종이 크기를 물어봤으므로 lower_bound에 해당하고따라서 min(left)의 값이 최종적으로 정답이 된다. [ 코드 ] import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import jav..
