# Backtracking

308개의 포스트

[BOJ 15649] N과 M (1)

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

2일 전
·
0개의 댓글
·
post-thumbnail

백 트랙 킹 (미완)

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

6일 전
·
0개의 댓글
·
post-thumbnail

i'm Not a QUEEN(feat. backtracking)

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

2023년 3월 23일
·
0개의 댓글
·

백준 1038. 감소하는 수 (Python)

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

2023년 3월 20일
·
0개의 댓글
·
post-thumbnail

Q. 15649 N과 M (1)

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

2023년 3월 14일
·
0개의 댓글
·
post-thumbnail

[Baekjoon/Python] 16198 에너지 모으기

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

2023년 3월 12일
·
0개의 댓글
·

[C++] 15652: N과 M(4)

backtracking

2023년 3월 10일
·
0개의 댓글
·

[백준 19942] 다이어트 (Backtracking, 파이썬3)

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

2023년 3월 7일
·
0개의 댓글
·
post-thumbnail

[python] 깊이 우선 탐색(DFS), 백트래킹(Back Tracking)

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

2023년 3월 2일
·
0개의 댓글
·

리트코드 - 797. All Paths From Source to Target

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

2023년 2월 28일
·
0개의 댓글
·
post-thumbnail

BOJ 2800 괄호제거

문제 해석구현피드백

2023년 2월 17일
·
0개의 댓글
·
post-thumbnail

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가 색칠될 줄의 경우의 수를

2023년 2월 8일
·
0개의 댓글
·
post-thumbnail

SWEA 1494. 사랑의 카운슬러(Python)(D4)

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

2023년 2월 6일
·
0개의 댓글
·
post-thumbnail

[Python] 백트래킹(Backtracking)

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

2023년 1월 31일
·
0개의 댓글
·
post-thumbnail

[BOJ] 15654: N과 M(5)

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

2023년 1월 20일
·
0개의 댓글
·
post-thumbnail

[BOJ] 1759: 암호 만들기

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

2023년 1월 20일
·
0개의 댓글
·
post-thumbnail

[BOJ] 14888: 연산자 끼워넣기

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

2023년 1월 20일
·
0개의 댓글
·

백준 2239번 스도쿠

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

2023년 1월 20일
·
0개의 댓글
·