HwangHub

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 위 문제는 완탐 시뮬레이션 문제로 이해할 수 있다. 사실 이 문제는 로직 구성은 간단한데 문제를 잘 읽어야 한다는 게 포인트인 것 같다. 숫자들이 두 줄의 컨베이어 벨트 위에 있는 것으로 정의되는데, 아래 줄 숫자들은 반전되어 보여진다는 게 일종의 장애물 포인트이다. 이를 고려하지 않고 ver1.0의 로직을 구성해서, 그 이후에 적용할 때에는 기존 입력이나 출력을 뒤집어서 수행하여 기존 로직을 사용할 수 있도록 하였다. 문제 풀이 import java.io.BufferedReader; impo..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 위 문제는 N x M 크기의 배열 안에서 구성될 수 있는 직사각형을 모두 탐색하여, 그 직사각형이 모두 양수로 이루어진 케이스 중 최대의 넓이를 출력하는 문제이다. n과 m이 20 이하의 자연수이므로, 그 내부 직사각형의 길이를 for loop으로 정의하고, 기준 좌표를 정의하고, 넓이 내의 좌표를 모두 for loop으로 순회하더라도 어림잡아봐야 O(n^3 * m^3)인데, 이렇게 해봐야 최악의 경우 64,000,000번의 연산을 하게 되고, 실제로는 이보다 더 작을 것이므로 완전탐색으로 수..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 분석 이 문제는 n이 100까지이므로 충분히 완전탐색이 가능하다. for loop을 이용하여 손쉽게 모든 경우의 수를 훑어서 정답을 찾아낼 수 있다. 문제 로직 대각선은 훑지 않아도 되고, 가로 또는 세로만 훑으면 되므로 원래 배열, 축 반전 배열 두 가지로 저장해두고 한번에 가로와 세로를 훑을 수 있도록 하였다. 또한 m이 1일 때에는 비교문 연산이 필요없이 모든 행/열이 '행복한 수열'이므로 해당 부분은 별도로 처리해주었다. 연속성이 중간에 끊기면 카운트를 다시 하되, 한번이라도 연속성을 가진 ..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 이 문제는 주어진 범위에서 조합의 경우의 수를 구하는 문제이므로 전형적인 백트래킹 문제라고 할 수 있다. 여기서 필요한 것은, 중복이 허용되지 않는다는 것이다. 따라서 파라미터를 통해 시작점을 진행시키는 테크닉이 필요했다. 문제 풀이 public class n개중에_m개뽑기 { private static int n, m; private static Set set = new TreeSet(); public static void main(String[] args) throws IOException..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이 문제 또한 최단 경로를 묻는 문제이므로 BFS로 접근하면 된다. 풀이 자바는 0으로 배열이 기본 초기화되니, 처음에는 0이면 이동이 불가한 것이라고 생각했다. public class 나이트 { private static int n; private static int[] dx = new int[]{-2, -1, 1, 2, 2, 1, -1, -2}; private static int[] dy = new int[]{-1, -2, -2, -1, 1, 2, 2, 1}; private static int x1,..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 2차원 배열 + 상하좌우 탈출 가능 경로 최단 거리 -> 가중치가 동일하니 BFS 뱀이 있는 칸 or 배열 크기를 벗어나는 방향으로 이동 불가 + visited[][] != 1 이동 발걸음 수를 저장할 ans[][] 선언하여 이동하며 업데이트 /* * 풀이 과정 pseudo code * 1. n, m 입력받는다. * 2. n번 loop : * 뱀이 없는 경우 1, 뱀이 있는 경우 0으로 2차원 배열 입력 * * 3. BFS() : * dx,dy 선언 ~ 상하좌우 * Queue q = new L..

https://www.codetree.ai/missions/2/problems/yutnori-1d?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 이 문제는 윳놀이 말의 선택 조합을 어떻게 가져가면 더 많은 점수를 낼 수 있는지에 대한 문제이다. 백트래킹으로 완탐을 돌렸을 때 시간복잡도는 O(k^n + n) 정도 될 것인데, k가 4 이하이고, n이 12 이하이므로 약 16백만 정도의 연산량이 최대이니 백트래킹을 활용해도 좋을 것이란 판단이 났다. 문제 풀이 package ..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 위 문제는 k

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 a,b,c,d,e,f가 여러개 등장할 경우에는 각 미지수에 적합한 숫자를 할당하는 것이 중요 완탐으로 조합을 탐색 -> 백트래킹으로 a,b,c,d,e,f 각각에 1~4를 배정한 뒤, 그 조합에 따른 결과값을 PQ에 넣구, 최대 결과를 출력(PQ.poll())하면 될듯. 문제 풀이 import java.io.*; import java.util.*; public class Main { private static List li = new ArrayList(); private static Queue ..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 이 문제는 선분들의 조합을 완전 탐색하여, 겹치지 않는 가장 많은 선분 선택 조합을 구하는 문제이다. 따라서 백트래킹을 이용하여 풀어낼 수 있다. 문제 풀이 [실패] 처음 떠올린 로직은 다음과 같다. 재귀 과정에서 앞뒤로 for loop을 활용하여 선분들을 수직선 상에 추가해주고 초기화하는 로직을 배치해 주었다. package 코드트리.완전탐색.백트래킹; import java.io.IOException; import java.util.HashMap; import java.util.Map; im..