백트래킹

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

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

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 백트래킹 필요 자료구조 - 1차원 int형 배열 (퀸의 위치 나타냄) ⭐ - 갯수 저장할 1차원 int형 변수 arr[i] = j : (i, j) 위치에 퀸을 둔다는 의미의 배열 - 퀸, 상하좌우 및 대각선으로 거리 제한 없이 한 방향으로 이동 가능하며, 이 이동가능한 동선과 겹치지 않는 곳에 또 다른 퀸을 배치해야 함 - 각 행 별로 놓을 수 있는 위치에 있을 때 재귀호출하고, 만약 모두 배치되었다면 count하면서 경우의 수 찾아냄 > 놓을 수 있는 위치인지 확인 → 1) 같은 ..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 백트래킹 + 가능한 모든 위치에서 한꺼번에 시작하는 BFS 필요 자료구조 - int[][] copy : 원본 배열 값 저장해둘 배열 (얘 대신 boolean[][] visited를 활용해도 된다,,) - List emptyPlaces : 벽 설치 가능한 위치 리스트 ⭐ - List realWalls : 벽 있는 위치 리스트 ⭐ - List fireList : 불 있는 위치 리스트 ⭐ - Queue q : 불 위치 저장 큐. BFS 탐색 위해 존재하는 불을 큐에 넣는다. 1. 입..

📖 문제 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 💡 풀이 방식 • 브루트포스 + 백트래킹 - 최소 색종이 갯수 사용 ⇒ 큰 종이부터 붙이기 ⇒ 그리디 - 완전탐색 ⇒ 브루트포스 + 백트래킹 - N X N 범위 내에 모두 1이 존재한다면, N X N 색종이를 붙였다 떼는 작업 반복 1. 종이 배열에 종이의 최대 갯수 저장 2. DFS 활용해 백트래킹 시도 - 기본 탐색 방향 : 가로 - 끝 칸 도착 시, 아랫줄 첫 칸으로 이동 3. 좌표가 맨 마지막 점 도달 시, 지금까지 붙인 종이 갯수 반환 ..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 백트래킹 시간 복잡도 : O(N! * N) 사용 자료구조 - 2차원 ing형 배열 - 1차원 boolean형 배열 → 열에 대한 방문 표시 배열 재귀 함수 인자 : (int row, int sum) = (현재 행, 적힌 수들의 합) - 종료 조건 : N개를 뽑았을 때, sum과 여태까지의 최댓값 max를 비교해 더 큰 값으로 갱신한다. - 반복문 : 현재 행에 대해 색칠할 열을 선택한다. ┕ 현재 열을 방문하지 않은 경우, 현재 열을 방문처리하고 그 다음 행에서 열을 확인하러 ..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 백트래킹 1. 말 K개 中 N개를 뽑는 재귀함수를 작성한다. 2. 말을 N개 뽑았을 때, 해당 순열에서 말을 이동시켜본다. 3. 말 위치가 윷놀이 판 상태보다 크거나 같은 값에 위치한다면, 정답 + 1한다. 4. 3에서 구한 정답과 최댓값을 비교해 더 큰 값으로 갱신한다. 💥 유의사항 N번 턴을 다 끝마치지 못하고 최대 점수를 얻을 수 있으므로, 모든 턴에 대해 점수를 계산해 그 중 최댓값을 계산해야 한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 백트래킹 (conditional) 1. [조건] 특정 숫자를 뽑을 때, 배열의 오른쪽에 위치한 원소 2개와 해당 숫자가 같은지 확인한다. - 이렇게 숫자 3개가 동일하다면, 같은 숫자가 3번 이상 연달아 나오는 것이므로 pass 한다. - 다르다면, 다음 백트래킹을 수행한다. 2. 같은 숫자 3개가 연달아오지 않는 리스트의 크기가 N과 같을 때, 해당 리스트를 출력한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..