백트래킹
백트래킹이란?
- 완전 탐색 방법 중 하나
- 재귀의 형태
- 깊이 우선 탐색(DFS)를 진행하며 조건 확인, 조건 만족 X 일 시 더 이상 탐색하지 않음 (가지치기)
-> DFS는 stack 이 적용된 개념이기 때문에, 마지막에 넣은 것부터 나오게 됨!
백트래킹 주요 코드 작성 방법
Point 1 -> 재귀를 진행하는 동안 사용될 깊이(depth)를 매개변수로 넣기
Point 2 -> 재귀가 종료되는 시점에서 수행해야 할 내용
Point 3 -> 재귀가 진행중이면 가지치기할 내용
Point 4 -> 문제의 조건에 맞게 조건 작성
완전탐색 & 백트래킹 관련 문제 및 풀이
차이를 최대로
문제 : https://www.acmicpc.net/problem/10819
풀이
파이썬 - https://velog.io/@mong7399/python-10819번-차이를-최대로
자바 - https://velog.io/@mong7399/Java-10819-차이를-최대로
블랙잭
문제 : https://www.acmicpc.net/problem/2798
풀이
파이썬 - https://velog.io/@mong7399/python-2798번-블랙잭
자바 - https://velog.io/@mong7399/java-2798번-블랙잭
스타트와 링크
문제 : https://www.acmicpc.net/problem/14889
풀이
파이썬 - https://velog.io/@mong7399/python-14889번-스타트와-링크
자바 -
좋은 수열
문제 : https://www.acmicpc.net/problem/2661
자바풀이 : https://velog.io/@mong7399/Java-2661-좋은-수열
연산자 끼워넣기
문제 : https://www.acmicpc.net/problem/14888
풀이 :
파이썬 - https://velog.io/@mong7399/python-14888번-연산자-끼워넣기
자바 - https://velog.io/@mong7399/java-14888-연산자-끼워넣기
사다리조작
문제 : https://www.acmicpc.net/problem/15684
풀이
파이썬 - https://velog.io/@mong7399/python-15684번-사다리-조작
자바 - https://velog.io/@mong7399/Java-15684번-사다리-조작
