HwangHub

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 이 문제는 지난번에 풀었던 "사각형 채우기"와 같은 유형의 문제로써, 점화식을 세울 때 조금 더 생각을 해줘야 하는 문제이다. 기본적으로 n번째 자리까지 타일을 까는 경우의 수는 n-1, n-2 번째까지의 타일을 까는 경우의 수 들을 이용하여 도출해낼 수 있다는 아이디어가 DP의 기본 흐름이다.(큰 문제는 작은 문제로 쪼개어 생각한다.) 이렇게 볼 때, 1칸짜리 그리고 2칸짜리를 이용하여 f(n) = 2 * f(n-1) + 3 * f(n-2) 까지는 쉽게 구해질 것이다. 이게 만약 안보인다면 ..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 계단 오르기와 동일한 전형적인 DP 패턴 한 번에 1칸 오르냐 2칸 오르냐 하는 것 n번째의 경우의 수를 구하는 것이니까 f(n) = f(n-1) + f(n-2); 문제 풀이 public class 사각형_채우기 { public static void main(String[] args) throws IOException { int[] dp = new int[1001]; dp[0] = 0; dp[1] = 1; dp[2] = 2; for (int i = 3; i

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 1. n층 높이의 계단을 오르는 경우의 수를 구하는 문제이다. -> 여기까지만 보면 아직은 어떤 알고리즘을 쓸지 확신하기 어렵다. 2. 2개 또는 3개 계단 단위로만 오를 수 있다고 한다. -> 일정 패턴으로만 진행되는 것을 알 수 있다. 이렇게 정형화된 패턴을 배치하는 경우의 수를 구하는 문제는 다이나믹 프로그래밍의 가장 대표적인 유형이다. 문제에서 요구하는 답은 n개의 계단을 오르는 경우의 수 이므로 f(n) = n번째 계단을 오르는 경우의 수 일 것이다. n번째 계단은 n-2번째 계단 또..

문제는 비공개이기 때문에 첨부하지 않겠다. 문제 해석 이 문제는 체스 나이트의 이동 패턴을 이용하여 나이트가 어디어디 갈 수 있는지 파악하는 문제였다. 2차원 격자 위에서 움직이는 패턴이 일정하므로 인접한 좌표로 이동할 수 있는 그래프 탐색 알고리즘을 사용하면 될 것이라고 생각했고, 전체를 탐색해야 하는 것이지 최단거리를 알아낼 필요는 없으므로 상대적으로 구현이 더 단순한 DFS를 사용하는 것이 효율적일 것이라고 판단하였다. 문제에서 요구하는 출력 결과는 visited 배열값을 이용하면 파악할 수 있을 것이라고 판단하였다. 문제 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; imp..

https://www.codetree.ai/missions/2/problems/puyo-puyo?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 코드트리 Intermediate Low 단계의 BFS 유형을 모두 푼 김에, DFS의 테스트 문제를 다시 한번 풀어보았다. 오랜만에 푸니까 조금 헤맸지만 그래도 풀어냈음에 의의를 가지고 싶다. 문제 해석 이 문제는 BFS로도 풀 수 있을 것 같은데, 핵심은 그래프 알고리즘으로 푼다는 것이다. 인접한 칸을 하나의 블록으로 인지하는 것이고, 이어..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 가중치가 일정한 상황에서 각 귤에 도달되는 시간을 숫자로 표현하는 문제이므로 BFS 문제임을 알 수 있다. 상한 귤들은 시작점이 되고, 인접한 귤로만 이동하면서 time을 1초씩 추가하면 된다. 이를 기록하는 배열은 별도로 선언한다. 그 외에 -1, -2 와 같은 결과 출력 양식을 맞춰주기 위해서는 출력 단계에서 조건문으로 처리해주면 깔끔하다. 문제 풀이 public class 상한_귤 { private static class Pair { private int x, y; private Pair..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 위 문제는 가중치가 1로 동일한 경우에서의 최단 거리를 묻는 문제이므로 BFS를 돌리면 된다고 느낄 수 있다. 대표적인 유형의 문제인 걸로 느껴지는데, 지금 뇌가 정지한건지 도저히 내가 어디가 틀린지 모르겠다... 일단 내 풀이는 맞을 가망이 없었고, 아무리 봐도 모르겠어서 일단은 답안을 이해한 뒤에 내 방식대로 고쳐서 작성해 보았다. 내 풀이(틀린 풀이) 나는 인간이 있는 좌표로부터 최단거리에 있는 대피소를 BFS로 찾고, 그 최단 거리를 ans라는 정답 배열의 인간 좌표에 입력해주는 방식으..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 k개의 도시를 중복 없이 골라야 하므로, 백트래킹을 통해 k개의 도시를 선정한 뒤, 각 시작점으로부터 BFS를 통해 탐색을 해서 이동 수의 최대를 뽑아내면 된다. u 이상 d 이하인 것을 검사하는 로직은 canGo()에서 검사하면 된다. 문제 풀이 백트래킹으로 k개의 도시를 고른다. (중복이 없어야 하므로 selected[][] 활용) 모든 경우를 탐색해야 하므로 적절하게 isVisited[][]를 초기화해줘야 한다. import javax.swing.*; import java.io.Buffe..

문제 해석 이 문제는 돌을 골라내는 조합 로직 + 탐색 로직이 필요하므로 백트래킹 + BFS로 풀 수 있겠다 판단하였다. 결론적으로, 해석까지는 좋았는데, 로직의 구현 단계에서 디테일이 부족하여 틀리고 말았다. 문제 풀이 package 코드트리.그래프.BFS; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class 돌_잘_치우기 { private static int n, m, k; private static int[][] arr; private static int ans; private static List sPos = new Array..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 위 문제는 2차원 배열 위에서 상하좌우로 움직이며 최댓값을 찾는 것을 반복하되, 움직이는 과정에서 무한으로 돌지 않도록 방문한 곳은 두번 방문하지 않아야 하며, 처음 시작한 곳의 숫자보다 작은 곳만 탐색할 수 있다. 이러한 방식은 그래프 알고리즘으로 구현이 가능하다. 일단은 코드트리에서 의도한 방향이 BFS이므로 BFS로 구현해보고, 나중에 다시 풀때 DFS로 가능한지 한번 살펴볼 예정이다. 문제 풀이 package 코드트리.그래프.BFS; import java.io.BufferedReader..