백트래킹

📖 문제   18428번: 감시 피하기NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복www.acmicpc.net   💡  풀이 방식• 조합(DFS) + BFS 1. 격자를 입력받으면서 학생 S의 위치, 선생님 T의 위치, 빈 칸 X의 위치를 각 리스트에 저장해둔다.이러면 나중에 완전탐색으로 학생, 선생님, 장애물 위치를 따로 안 찾아도 된다.for(int i = 0 ; i   2. 빈 칸 X의 위치들 중 3개를 뽑고, 해당 위치에 장애물을 심었을 때 모든 학생들이 감시를 피할 수 있는지 BFS로 탐색한다.private static void dfs(int..

📖 문제 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 💡 풀이 방식 • 백트래킹 + DFS (0,0)부터 dfs를 한다. 해당 점의 인접한 4방향 탐색을 통해 격자 범위 내에 있고, 지금까지 나온 적 없는 알파벳인 경우 마저 탐색을 진행하며 최대 경로를 찾는다. 🔺 코드 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 ..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 그리디 1. 연속된 5개의 광물을 한 그룹으로 묶어 각각 다이아/철/돌 곡괭이로 캤을 경우의 피로도의 합을 그룹별로 저장한다. 2. 돌로 캤을 때 가장 피로도가 높은 순으로 내림차순 정렬한다. 3. 정렬 후, 다이아 - 철 - 돌 곡괭이 순으로 캐야 피로도를 최소화할 수 있다. 🔺 코드 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 ..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS 먼저, 문자열 expression을 숫자와 연산자로 나눠 각각 배열에 저장한다. - 숫자인 경우, 숫자를 나타내는 임시 문자열에 하나씩 값을 붙여둔다. - 연산자인 경우, 여태까지 구한 임시 문자열을 숫자로 변환해 숫자 리스트에 저장하고, 임시 문자열을 초기화한다. 그리고 연산자 리스트에도 현재 연산자를 추가한다. + 반복문이 끝나면 마지막으로 만들어진 문자도 따로 삽입해주는 것을 잊지 말자,, static List numList = new LinkedList(); // 숫자..

📖 문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 💡 풀이 방식 • 부분 집합 (백트래킹, 재귀) + BFS 필요 자료구조 [전역변수] - 인구 수 저장용 1차원 int형 배열 - 그래프 정보를 저장하기 위한 그래프 리스트 배열 - 부분 집합용 사용 여부 표시용 1차원 boolean형 배열 - 최솟값 [BFS용] - 방문할 원소를 저장하는 Integer형 큐 - 방문 표시용 1차원 boolean형 배열 (연결되었는지 확인용) [두 그룹에 속한 원소들 저장하고, 차이 저장용] - 구역A 원소들 저장할 Integer형 리스트 -..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS (백트래킹) 필요 자료구조 - 1차원 int형 정답 배열 lion - 점수 차이가 최대일 때 라이언이 쏜 화살 수를 저장하는 1차원 int형 배열 arrows 백트래킹으로 n개를 뽑는 조합을 생성해 화살을 어디에 얼마나 맞추는지 구할 수 있다. 그런데 이 때 n = 10일 때 시간초과가 나므로, 백트래킹 메서드의 반복문에 가지치기(특정 조건 추가)해줘야 한다! 여기서 특정 조건은 과녁 i에 라이언이 임의의 점수에서 어피치에게 점수를 따내기 전까지 (arrows[i]

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 백트래킹 (중복 없는 순열) . 중복 없는 순열을 구하듯이 1에서부터 n개를 뽑는 백트래킹을 진행한다. (→ 방문 표시 배열 사용) . 1에서부터 백트래킹을 시도하기 전 방문 배열의 1은 방문 처리하고, 리스트에도 1은 미리 추가해둔다. - 시간 복잡도 : O(N! *N) 💥 유의사항 - 마지막 지점에서 뽑으려는 지점 간 이동 가능해야(= 비용이 0이 아니어야) 이동 가능하다. - 1번 지점으로 돌아오는 처리를 꼭 해야 한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11..

📖 문제 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 💡 풀이 방식 • 백트래킹 부분집합 (재귀) 을 활용해 팀을 나누고, 각 팀별로 능력치를 합하고 그 차이를 최솟값과 비교해 정답으로 출력한다. 💥 유의사항 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다. → 부분집합 🔺 코드 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 ..

📖 문제 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 💡 풀이 방식 • 브루트포스 + 백트래킹 1~N개의 재료(브루트포스) 조합을 만들면서(백트래킹), 원하는 갯수만큼 뽑힌 재료들의 (신맛 - 쓴맛)의 차이를 가장 작은 요리의 차이와 비교해 갱신한다. 1~N까지 N번 백트래킹을 실행한다. DFS의 인자는 아래와 같다. 재료를 뽑을 때마다 신맛과 쓴맛 인자를 갱신해 사용 가능하다. DFS(사용할 재료 idx, 지금껏 사용한 재료 수 cnt, 사용할 재료 수 target, 신맛 sour,..