코테/코드트리

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 가중치가 동일한 그래프에서의 BFS 각 사람마다 BFS를 수행해 가장 가까운 쉘터를 구하도록 했다. ⇨ 시간 복잡도 : O(hN^2) 1. 격자를 입력받으면서, 사람(2)의 위치도 리스트에 저장해둔다. 2. 사람 위치가 저장된 리스트를 돌면서, 각 사람이 비를 피할 수 있는 공간 3까지 가는 최단 거리를 bfs를 통해 구한다. 방문 배열을 매번 초기화해줘야 한다. 사람 위치(2)에서 bfs를 진행하며 3까지 bfs를 수행한다. (=최단 거리) 큐에는 (방문할 행, 열, 거리 값..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 백트래킹 + BFS 사용 자료구조 [백트래킹용] - 도시 위치와 인덱스 저장할 int형 2차원 배열 ⇨ int[][] cities = new int[n*n + 1][2]; - 뽑은 도시 저장할 int형 리스트 [BFS용] - dx/dy 배열 - 방문 표시 배열 - 최댓값 도시 정보를 입력받을 때 해당 도시의 행,열 값과 인덱스를 도시 정보 배열 cities에 저장한다. 백트래킹을 통해 도시 정보 배열을 돌며 이 중 도시 k개를 뽑는다. 만약 k개를 뽑지 않았다면, 해당 인덱스의..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • BFS 1. 빙하에 둘러쌓여 있지 않은 물들을 구해야 한다. ▷ 매번 (0,0)에서 BFS를 수행한다. 2. 완전탐색을 통해 주변에 빙하에 둘러쌓여 있지 않은 물이 있는 빙하들을 찾아 녹인다. 3. 과정 1,2를 격자 내에 빙하가 존재하지 않을 때까지 실행하며 걸리는 시간과 마지막으로 녹은 빙하의 크기를 갱신한다. ▷ 완전탐색 통해 확인 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 백트래킹 + BFS 필요 자료구조 - 돌 위치 저장용 리스트 rockList ⭐ - 고른 돌 목록 1차원 int형 배열 (dfs용) - 방문 표시 배열 (bfs용) - 시작점 위치 1차원 int형 배열 startPos ⭐ 1. 격자를 입력받으면서, 돌이 있는 위치를 rockList 리스트에 저장한다. 2. startPos 배열에 K번 시작점 위치를 저장한다. 3. M개를 뽑는 dfs를 수행한다. - 종료 조건 : m개 뽑았을 때 3-1) 돌을 제거한다. 3-2) 시작점에서부터 ..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • BFS 1) 현재 위치에서 이동 가능한 칸 전부 찾기 2) 도달 가능한 칸 中 우선순위가 가장 높은 칸 위치 구하기 - 도달 가능한 칸 있다면, 현재 칸 위치를 해당 위치로 옮기기 - 도달 가능한 칸 없다면, 움직이기 종료 시작 위치에서 상하좌우에 본인보다 작은 값이 없다면, 이동할 수 없으므로 종료한다. 하지만 본인보다 작은 값이 존재한다면, 아래와 같이 진행한다. 1) bfs를 통해 배열을 탐색하며 방문 가능한(=격자 범위 내에 있고, 방문한 적 없고, 기준 점의 값보다 작..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 시뮬레이션 입력받은 시작점 (r,c)에서부터 우선순위가 상하좌우일 때 현재 칸보다 큰 값을 가진 칸으로 바로 이동할 수 있는지 확인한다. (boolean으로 확인) 그 칸에서 이동할 수 있다면, 해당 칸을 경로 리스트에 넣어 출력한다. 상하좌우로 이동할 수 없다면, 종료한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 4..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 백트래킹 1~4까지의 숫자 중 하나를 선택해 총 N번 선택하는 재귀를 작성해 모든 숫자들을 만든다. 그 중 정확히 숫자만큼 연달아 같은 수가 나오는 숫자 수를 구한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 import java.util.*; import java.io.*; public..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • DP dp[ i ] : 점프해 도착한 마지막 위치 i까지 가능한 최대 점프 횟수 i보다 앞에 있는 위치(j)들 中 해당 위치에서 점프해 i번째 위치로 올 수 있는 경우 중 최대 점프 가능 횟수 계산 for(int i = 1 ; i = i) { dp[i] = Math..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • DP (LDS) dp[ i ] : 마지막으로 고른 원소 위치가 i인 부분 수열 中 최장 감소 부분 수열의 길이 현재 위치의 값 arr[i]와 현재 위치보다 앞쪽 j에 있는 값들과 값을 비교해 현재 위치에 있는 값 arr[j]가 앞쪽에 있는 값 arr[i]보다 작다면 감소하는 부분 수열이므로 dp 배열을 갱신한다. for(int i = 0 ; i arr[i]) { dp[i] = M..