# 백트래킹

169개의 포스트
post-thumbnail

9663 N-Queen 파이썬 완전탐색?

백준 9663 N-queens 문제를 풀어보려고 하는데 생각보다 문제 설명이 넘 간단해서 당황하기도 했다. 왜그런가 했더니 꽤 유명한 문제였다. 어떻게 풀어야할까? 왜 완전탐색일까? 나는 완전탐색 문제 접근방식을 완전탐색을 할 수 있는 반복문짜기 요구하는 로직짜기

어제
·
0개의 댓글

[BOJ 19236] 청소년 상어(Python)

청소년 상어물고기를 먹는 모든 경우의 수를 체크하고 가장 번호가 많은 경우를 찾는 문제입니다. 아기 상어보다 제한사항이 더 까다롭고 물고기와 상어의 이동이 각각 다르기 때문에 따로 구현해야하는 것은 물론, 사소한 제한사항 하나하나 꼼꼼히 읽어야 합니다.물고기의 이동에

2일 전
·
0개의 댓글

[BOJ 17136] 색종이 붙이기(Python)

색종이 붙이기10X10 행렬이 주어지고 1x1, 2x2, ... 5x5 색종이를 각각 최대 5장씩 사용하여 행렬을 모두 0으로 만드는 문제입니다. 여기서 색종이를 붙이려면 해당 영역이 모두 1이어야 붙일 수 있습니다.저는 총 3개의 메소드를 활용했습니다.전체 탐색 메소

2일 전
·
0개의 댓글

2239. 스도쿠

2239\. 스도쿠스도쿠를 입력하면서 blank들을 찾아서 list에 보관 backtracking은 blank_list 순서대로 promising 한 값들을 넣어가면서 sudoku를 채움 숫자가 작은 순서대로 넣기때문에, 첫번째 나오는 스도쿠가 반드시 가장 작은 스도쿠

3일 전
·
0개의 댓글

1103. 게임

1103\. 게임기존의 그래프 문제와 다르게, visited와 cycle 두개의 확인 지표가 필요하다. 처음에는 기존의 maze 문제처럼 BFS로 풀려고했다. 왔던 타일을 다시 오는 경우가 발생할 수 있기 때문에 BFS로 풀 수 없다는 것을 알게되었다. DFS로 변경했

5일 전
·
0개의 댓글

[Baekjoon] 2239. 스도쿠

문제 링크백트래킹골드 49x9 스도쿠 문제에 빈칸들이 주어졌을 때, 빈칸을 모두 채워서 출력하기사전순으로 가장 빠른 답을 출력스도쿠 보드판을 입력받을 때 빈칸들의 좌표를 따로 저장해둠모든 빈칸들에 대해서 백트래킹 수행각 빈칸에서 넣을 수 있는 숫자들을 구해서 해당 숫자

2021년 6월 11일
·
0개의 댓글

15650. N과 M (2)

링크텍스트조합을 물어보는 문제여서 combination 씀itertool을 안쓸 경우 combination 구현 필요

2021년 6월 8일
·
0개의 댓글

2580. 스도쿠

2580\. 스도쿠스도쿠를 입력받을 때 blank도 같이 입력 받는다. back tracking 할때 blank list에서 하나씩 뽑아서 하도록 한다. \- blank list를 따로 안하고, row와 col을 돌아가는 방식으로 했더니 꼬임back tracking

2021년 6월 8일
·
0개의 댓글

백트래킹 ( Back tracking )

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

2021년 6월 4일
·
0개의 댓글

백준 10819번 차이를 최대로

문제링크: https://www.acmicpc.net/problem/10819permutation을 모두 구해서, 각 케이스마다 ai-ai+1의 합을 구하면 된다.쉬운 문제였다.

2021년 6월 3일
·
0개의 댓글

1062번_가르침.py

K개의 알파벳을 배워 최대의 단어를 읽을 수 있도록 하는 방법. 모든 단어는 anta 로 시작하며 tica로 끝남.1\. set과 백트래킹을 이용하는 방법2\. combination을 통해서 푸는 방법백트래킹을 통해서 모든 경우의 수를 check.이때 유망성 check

2021년 5월 31일
·
0개의 댓글

백준 1038번 - 감소하는 수

백트래킹 형식으로 푼 문제, 맨 앞쪽 자리수부터 채워나가면서 진행해준다.크게 최대 자리수가 한 자리 수이고 맨 앞자리 수를 채워야할 때, 최대 자리수가 한 자리 수가 아니고 맨 앞자리 수 를 채워야할 때, 그 외 맨 앞자리 수를 채울 때가 아닐 때로 나누어,최대 자리수

2021년 5월 30일
·
0개의 댓글
post-thumbnail

백준 9663번: N-Queen

N-Queen 시간 제한: 10 초 메모리 제한: 128 MB 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N

2021년 5월 30일
·
0개의 댓글
post-thumbnail

[백준] 9663번 N-Queen

https://www.acmicpc.net/problem/9663N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.첫째 줄에 N이 주어진다

2021년 5월 23일
·
0개의 댓글
post-thumbnail

[백준] 19621번 회의실 배정 2

https://www.acmicpc.net/problem/19621서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회

2021년 5월 23일
·
0개의 댓글
post-thumbnail

[Programmers] N-Queen

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.체스판의 가로 세로의 세로의 길이 n이

2021년 5월 18일
·
0개의 댓글

[알고리즘] 완전탐색

"모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘"

2021년 5월 17일
·
0개의 댓글
post-thumbnail

백준 16988

문제링크 https://www.acmicpc.net/problem/16988 문제 풀이 모든 경우의 수를 생각하여 bfs를 돌려주며 풀었다. 크게 해야하는 작업은 다음의 두가지 이다. 내 돌을 놓은 두 자리를 찾아서 돌을 놓아보기 백트래킹과 next_permutation 알고리즘을 이용하여 놓을 두 자리를 골라낼 수 있다. 아래 코드에서는 n...

2021년 5월 15일
·
0개의 댓글
post-thumbnail

[ BOJ 1182 ] 부분 수열의 합(Python)

https://www.acmicpc.net/problem/1182n개로 이루어진 수열에서 만들 수 있는 부분 수열의 합이 s가 될 때의 경우의 수를 구하는 문제다.1,3,5 로 만들 수 있는 부분 수열은 1, 3, 5, 1, 3, 1, 5, 3, 5, 1, 3

2021년 5월 14일
·
0개의 댓글