HwangHub

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 n의 길이가 10이므로 기본적으로 완전탐색이 가능한지 파악하는게 좋다. 이 문제는 글자 하나씩 shift를 수행한 뒤 문자열을 인코딩했을 때 가장 짧은 길이를 물어보는 문제이므로, 이를 단순 완전탐색으로 알아내어도 최대 2차원 for loop만으로도 전체 경우 탐색이 가능할 것으로 예상되어 완탐을 수행하는 것에 무리가 없다고 보았다. 문제 풀이 package 코드트리.완전탐색.시뮬레이션; import java.io.BufferedReader; import java.io.IOException; ..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 위 문제는 일정 규칙에 따라 이동한다고 가정할 때, 가장 많은 이동 수를 얻는 경우를 찾는 문제이다. 특정 위치에서 항상 최선인 경우가 명확하다면 그리디 알고리즘으로 풀 수 있겠지만, 이번 경우에서는 위치와 grid상의 숫자에 따라 최선인 상황이 매우 다이나믹하게 변동된다. 따라서 동적 계획법이 적합한 알고리즘일 것으로 예상할 수 있다. 문제 풀이 첫 번째 풀이는 틀린 풀이이다. public class 이차원_최대_증가_수열 { private static int n, m; private sta..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 내가 얻고자 하는 값은, 문제에서 주어진 규칙을 따를 때 "첫 번째 위치에서부터 최대 몇 번의 연속된 점프를 할 수 있는가?" 이다. 수열 위의 임의의 점 arr[i]이 갖는 값은 그 위치에서 얼마만큼 멀리 점프를 할 수 있는지를 의미하며, 무조건 적게 뛰거나 많이 뛴다고 해서 최선이 아니므로 그리디는 부적절한 것으로 보인다. 그렇다면 전체 경우의 수를 탐색해야 하는가? n의 크기가 1,000이하이므로 백트래킹이나 루프를 이용한 완전탐색을 돌리려고 시도하면 어림짐작 하더라도 상당히 많은 경우의..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 ans[i]가 i번째 숫자까지를 기준으로 최대 길이라고 할 때, ans[i-1]에서 ans[i]를 무조건 알 수 있다 할 수 없다고 판단하여 그리디는 아니라고 판단했다. 그러면 완전탐색이냐 할 때에 n이 1,000 이하의 수인데, 총 1000개의 숫자 중 최장 길이의 부분 수열을 구하기 위해서는 길이 1부터 n까지의 루프 속에서 해당 길이의 숫자를 선택하는 모든 경우를 탐색하기 위해 백트래킹을 걸면 2^n정도로 걸리는 게 일반적이라 이번 문제에서는 부적절하다 보았다. 동적계획법으로 풀게 되면 ..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 분석 인접한 항으로 이동하는게 아니라 모든 항을 대상으로 움직이는 패턴이 정해져 있고 , n 번째 위치의 숫자가 무엇일지 알아보는 문제이므로 전형적인 DP 문제이다. 하지만 이 문제에 대한 점화식을 세우는 것이 개인적으로는 어려웠는데, 최댓값을 최소로 하는 프로그램이므로, "각 패턴의 최대값끼리의 최솟값을 구하면 된다"라는 것을 감안하여 세우니 되었다. 감 잡기 전에는 와닿지 않는 말이었는데, 식을 세우고 나니 사실 문제가 매우 명확하게 제시되어있는 것 같다는 생각도 했다. 문제 풀이 package..

문제 분석 이 문제는 일정 규칙을 갖고 숫자를 채워나갈 때, 최종적으로 어떤 결과를 얻는가를 파악하는 문제이므로 전형적인 동적계획법 문제이다. 문제 풀이 동적계획법 알고리즘을 적용하기 위해, 기본적으로 당연한 경우를 initialize 한 뒤에, 가정한 점화식을 바탕으로 코드를 전개해주었다. package 코드트리.DP; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 정수_사각형_최소_합 { private static int n; private static int[][] arr; private stati..

유형 파악 이 문제는 2차원 배열 상의 출발지에서 목적지까지 이동시간의 최소를 구하는 문제이면서, 이동간 시간 가중치가 동일하기 때문에 전형적인 BFS 문제라고 이해할 수 있다. 아울러, 몇 개의 점을 선택하여 제거하는 경우를 세야 하므로 이 부분은 백트래킹 로직을 활용하여 풀어내 주었다. 제출 코드 구성했던 로직의 특징은, 여러 경우에서 도착지에 도달하는 시간이 도출될텐데, 그 경우 중 가장 빠른 경우에서의 시간을 구하는 것을 우선순위 큐를 활용하여 도출해줬다는 것과, 제거하려는 벽을 중복으로 선택하지 않기 위해 selected[][] 라는 배열을 운영한 것이다. 개인적으로 헤맨 부분은, 백트래킹을 통해 제거할 벽을 모두 선택했을 때 bfs를 수행하기 위해 관련 변수들을 초기화해줘야 한다는 것이다. 이..

지난 실력진단 문제에서 구성되는 마을의 최대 크기라던지, 마을의 개수를 어떻게 구할 수 있을지 쉽게 떠오르지 않았어서 해당 부분을 연습하기 위해 이 문제를 다시 풀어봤다. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 접근 이 문제는 단순 반복문을 통해서는 나의 한계로 로직이 떠오르지도 않거니와, 있더라도 분명히 매우 복잡할 것이므로 패스하였다. 그 외에 순열, 조합과 같은 경우의 수를 탐색하는 경우도 아니고, 최대최소를 얻는 그리디한 바이브의 문제도 아니였다. 탐색 알고리즘 중에 이웃한 항과의 관계를 통해 답을 도출해 내는 그래프 알고리즘이 이 문..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 이 문제는 N x N 행렬 위에서 이동을 할 때, 지나온 숫자들의 합이 최대가 되는 경우의 그 총합을 구하는 문제이다. 1. 완전탐색으로 접근했을 때 가능한가? -> 일단 인접한 항으로 이동하면서 탐색하는 방법이므로 그래프 알고리즘을 적용해볼 수 있을 것 같다는 느낌은 들지만, 이 문제의 경우 오른쪽 또는 아래로 선택하여 이동 + 이 과정을 최악의 경우 2n-1번 반복하여 얻는 결과를 보여줘야 한다. 이 때, 시간복잡도를 보면 2^(2n-1)이 될 것이므로 n이 최대 100이니 2^199 만큼..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 이 문제도 전형적인 타일 깔기 문제라서 DP로 풀 수 있으며, 이는 매우매우 간단한 점화식으로 표현할 수 있다. 문제 조건에 등장하는 타일을 가지고 n의 길이를 가진 사각형을 채우는 경우의 수는 아래와 같이 점화식을 세울 수 있다. f(n) = f(n-1) + 2 * f(n-2) 이를 참고하여 타뷸레이션 방식으로 DP 로직을 구성하면 아래와 같다. 문제 풀이 package 코드트리.DP; import java.io.BufferedReader; import java.io.IOException; ..