# Backtracking

gracemjy

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

leverest96

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

leverest96

백준과 SWEA의 N-Queen 문제를 풀었당.backtracking의 개념을 이용한 풀이를 활용해야했다.당연히 이차원배열을 생각했지만 하나의 일차원배열로 활용할 수 있는 방안이 있어서 차용했다.https://st-lab.tistory.com/118

www-jong

문제 : https://www.acmicpc.net/problem/1038참고로 이문제는 1174번(줄어드는 수)와 99% 유사하다.백트래킹 혹은 조합을 통해 0부터 1000000까지의 줄어드는 수 조합을 찾는다.이때,최대 감소하는 수(9876543210)는

ashbrother

BOJ 문제 15649 N과 M (1) 풀이

ezenjun

백준 16198 에너지 모으기처음 문제를 봤을 때 그리디로 접근해도 될 것 같았다.각 단계에서 얻을 수 있는 최대 값을 구해서 구슬이 2개만 남았을 때 그 값들을 모두 합하려고 했다.하지만 시간초과도 아니고 바로 틀렸다고한다..ㅎ테스트케이스 다 맞았길래 이렇게 푸는거구

j30ngwoo

backtracking

jypapapaa

다이어트식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각각 합이 최소 100, 70, 90, 10가 되도록 하는 경우를 생각

lhj99apr

그래프 탐색은 하나의 정점을 시작으로 모든 정점을 한 번씩 방문하는 것이다. 깊이 우선 탐색(Depth-First Search)이란 그래프 탐색법의 일종으로, 한 정점에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 전부 탐색하는 방법이다.주로 모든 노

bnbnac

주어진 DAG의 시작점에서 끝점으로 갈 수 있는 경로들을 반환하는 문제입니다. ( DAG - 위키피디아 바로가기 )시작점부터 carrier에 경로를 담으며 끝점에 도달하면 answer에 추가하고 return하는 방식으로 구현했습니다.return 후에는 carrier에서

return-to-oz

문제 해석구현피드백

www-jong

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

www-jong

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

petcu1004

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

drizzle0171

이제 이런 류는 껌이다 ㅋN과 M 시리즈 정복하기 !이제 이건 진짜 쪼끔 식은 죽 먹기다 ㅎㅂㅎ다른 사람 풀이도 비슷하거나 내가 좀 더 쉬운 코드여서 다른 풀이는 생략!실버3은 많이 쉽구나 ...

drizzle0171

보이는가 ... 나의 광기가 ... 풀이도 광기다 ...ㅎㅂㅎ

ilov1112

백트래킹

drizzle0171

1시간은 고민한 것 같다 ...나 왜 골드 5...? 실버 1 문제도 이렇게나 어려운데 ...

asmka2

링크텍스트스도쿠가 주어지면 정답을 출력하는 프로그램을 작성해야 한다.정답이 여러가지라면 사전식으로 가장 앞서는 것을 출력한다.풀이 방법Brute force, backtracking 방식으로 푼다. 우선 값이 0인, 즉 채워야 하는 칸들의 좌표를 vector인 zeroC