# Backtracking
[BOJ 15649] N과 M (1)
문제 15649자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열백트래킹 문제arr: 수열이 담긴 리스트1\. 1~N 사이의 자연수를 중복없이, 오름차순으로

백 트랙 킹 (미완)
Backtracking(백트래킹)개념여러가지 선택지들이 존재하는 상황에서 한가지를 선택선택이 이루어지면 새로운 선택지들의 집합이 생성선택을 반복하며 최종상태에 도달올바른 선택을 계속하면 목표상태에 도달백트래킹 vs 깊이 우선 탐색불필요한 경로를 조기에 차단 / 모든 경

i'm Not a QUEEN(feat. backtracking)
백준과 SWEA의 N-Queen 문제를 풀었당.backtracking의 개념을 이용한 풀이를 활용해야했다.당연히 이차원배열을 생각했지만 하나의 일차원배열로 활용할 수 있는 방안이 있어서 차용했다.https://st-lab.tistory.com/118
백준 1038. 감소하는 수 (Python)
문제 : https://www.acmicpc.net/problem/1038참고로 이문제는 1174번(줄어드는 수)와 99% 유사하다.백트래킹 혹은 조합을 통해 0부터 1000000까지의 줄어드는 수 조합을 찾는다.이때,최대 감소하는 수(9876543210)는
백트래킹(Backtracking) 개념

[Baekjoon/Python] 16198 에너지 모으기
백준 16198 에너지 모으기처음 문제를 봤을 때 그리디로 접근해도 될 것 같았다.각 단계에서 얻을 수 있는 최대 값을 구해서 구슬이 2개만 남았을 때 그 값들을 모두 합하려고 했다.하지만 시간초과도 아니고 바로 틀렸다고한다..ㅎ테스트케이스 다 맞았길래 이렇게 푸는거구
[백준 19942] 다이어트 (Backtracking, 파이썬3)
다이어트식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각각 합이 최소 100, 70, 90, 10가 되도록 하는 경우를 생각

[python] 깊이 우선 탐색(DFS), 백트래킹(Back Tracking)
그래프 탐색은 하나의 정점을 시작으로 모든 정점을 한 번씩 방문하는 것이다. 깊이 우선 탐색(Depth-First Search)이란 그래프 탐색법의 일종으로, 한 정점에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 전부 탐색하는 방법이다.주로 모든 노
리트코드 - 797. All Paths From Source to Target
주어진 DAG의 시작점에서 끝점으로 갈 수 있는 경로들을 반환하는 문제입니다. ( DAG - 위키피디아 바로가기 )시작점부터 carrier에 경로를 담으며 끝점에 도달하면 answer에 추가하고 return하는 방식으로 구현했습니다.return 후에는 carrier에서

SWEA 4613. 러시아 국기 같은 깃발 (Python)(D4)
흰색a줄, 파란색b줄, 빨간색c줄을 색칠하는데, a>=1, b>=1, c>=1, a+b+c=N 이어야 하며 색칠해야하는 값이 최소이어야 한다.먼저, N개의 줄에 대해 각 줄의 W,B,R의 갯수를 구한다.이후 백트래킹으로 2~N-1줄에 대해 B가 색칠될 줄의 경우의 수를

SWEA 1494. 사랑의 카운슬러(Python)(D4)
N마리의 지렁이가 있으면 이중 N/2마리를 출발지렁이, N/2를 도착지렁이로 구분짓는다.그리고 출발지렁이의 좌표값합과 도착지렁이의 좌표값합을 A, B라고 할 경우(Ax-Bx)^2+(Ay-By)^2가 최소가 되게하는 지렁이 조합의 경우의수를 찾으면 됨 한쌍, 한쌍 구해서

[Python] 백트래킹(Backtracking)
= 퇴각 검색해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법최적화 문제와 결정 문제를 푸는 방법DFS: 가능한 모든 경로(후보)를 탐색한다.: 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지

[BOJ] 15654: N과 M(5)
이제 이런 류는 껌이다 ㅋN과 M 시리즈 정복하기 !이제 이건 진짜 쪼끔 식은 죽 먹기다 ㅎㅂㅎ다른 사람 풀이도 비슷하거나 내가 좀 더 쉬운 코드여서 다른 풀이는 생략!실버3은 많이 쉽구나 ...
백준 2239번 스도쿠
링크텍스트스도쿠가 주어지면 정답을 출력하는 프로그램을 작성해야 한다.정답이 여러가지라면 사전식으로 가장 앞서는 것을 출력한다.풀이 방법Brute force, backtracking 방식으로 푼다. 우선 값이 0인, 즉 채워야 하는 칸들의 좌표를 vector인 zeroC