백트래킹

[백준 14391] 종이 조각 (C++)

14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 백트래킹, 브루트 포스 [백준 1799] 비숍 C++ 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 hyeo-noo.tistory.com > N >> M; string str; for(int r = 0; r > str; for(int c = 0; c

[백준 1405] 미친 로봇 C++

1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 백트래킹 1. 문제 해결 아이디어 로봇이 최대 14번 움직이므로 14번 동안 자유롭게 움직일 수 있는 좌표 Map[32][32]를 설정해주었다. 초기 좌표를 적당한 중간 좌표로 잡아주고 백트래킹 dfs를 해준다. 움직일 때마다 확률을 곱해줘야 하므로 함수의 인자로 초기값 1을 가지는 확률 변수를 넘겨준다. 이동 중에 방문했던 곳을 다시 들리게 된다면 지금까지 곱해진 확률을 결과값에 더해준다. (단순하지 않을 때만 더해 줌) 결과는 단순한 경우를 찾으므로 1-..

[백준 2239] 스도쿠 C++

2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 백트래킹 1. 문제풀이 아이디어 브루트포스 + 백트래킹 문제이다 현재 칸이 '0' 이라면 1 ~ 9까지의 숫자를 모두 대입해 보고, 대입한 숫자가 현재 칸에 들어가도 되는지 확인한다. 현재 칸에 모든 숫자가 들어갈 수 없다면 현재 칸을 다시 0으로 만들고 이전 칸으로 돌아간다. 현재 칸이 '0'이 아니라면 다음 칸으로 넘어간다. 2. 코드 설명 ~ 숫자를 입력 받아 Map 배열에 넣는다. ~ Map 상태를 보여준다. ~ 현재 칸에 들어있는 숫자를 넣어도 룰..

[백준 1799] 비숍 C++

1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 백트래킹 연습하기 #4 1. 문제풀이 아이디어 비숍의 특징 : 체스판의 검은 칸에 있는 비숍과 흰색 칸에 있는 비숍은 서로 아무 영향을 끼칠 수 없다. 이 문제를 정석적인 백트래킹으로 푼다면 시간 복잡도는 O(2^(N*N))이 된다.. 체스판에 모든 곳에 비숍을 놓을 수 있고 N=10이면 각각의 칸마다 ( 비숍을 놓는다 or 놓지않는다 ) 2가지의 경우가 생기므로 2^100가지의 경우를 모두 탐색해야한다 2^100 = 1.2676506e+30 이므로 참신한 방법이 필요하..

[백준 12852] 1로 만들기 2 C++

12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net dfs + 백트래킹 기법을 사용해서 푼 문제 vector temp : dfs를 돌면서 거쳐온 숫자가 순서대로 저장되어 있는 벡터 (경로 저장) solve 함수의 cnt는 현재 사용된 연산의 횟수 solve함수가 실행 될 때마다 현재 숫자 n을 경로벡터(temp)에 저장해 주고 n == 1 이 되면 현재 결과 값과 비교해서 cnt값이 더 작다면 지금까지 지나온 경로를 ret 벡터에 넣어준다 모든 경로를 탐색하는게 기본 동작이지만 if(cnt > result) return; 코드가 있기 때문에 현재 구해진 결과값보다 지금 경로에서의 연산 사용횟수가 많아진다면 return을..

[백준 17136] 색종이 붙이기 C++

17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 백트래킹 연습하기 #3 삼성 A형 기출 문제 백트래킹을 효과적으로 적용하기 위해서 가장 큰 색종이 먼저 덮어줘야하는 그리디 기법이 사용되었다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 ..

[백준 2661] 좋은 수열 C++

2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 백트래킹 연습하기 #2 res : 지금까지 만들어진 수열 is_bad() 함수의 나쁜 수열 찾는 방법 ex1) res = 32121 start lo hi 0 32 121 1 21 21 -> start=1 일 때 lo == hi 이므로 나쁜 수열이 되어 return false ex2) res = 3212323 start lo hi 0 321 2323 1 212 323 2 12 323 3 23 23 -> start=3 일 때 lo==hi 이므로 나쁜 수열이 되어 return f..

백트래킹 너무 어려워

아 백트래킹 너무 어렵다... 실버 1문젠데 1시간 반이나 고민하고 진짜 절망스럽다 백트래킹 왜이렇게 어렵냐 나만그래? 전에 조고리즘 Music도 백트래킹에서 막혀서 80점으로 그냥 던져놨는데 요즘따라 백트래킹 알고리즘때문에 신경쓰여서 다른거 할 때도 자꾸 생각나서 집중이 안된다 그만큼 열심히 해야지... baaaarkingdog 님 유튜브에도 보니까 백트래킹은 구현력이 매우 많이 필요한 파트이고, 재귀를 기본적으로 사용하기 때문에 문제를 많이 풀고 익숙해지는게 진짜 중요하다고 한다... 쉬운 알고리즘이 아니란거에 그나마 위안을 좀 얻어야 겠다ㅠ 그런데 백준 티어는 플레티넘을 바라보고 있는데 실버 1 백트래킹 문제에 쩔쩔매면 진짜 티어가 무슨 의미인가 싶다 아직 기초공사가 많이 부족한 상태임을 다시한번 ..

[백준 1759] 암호만들기 C++

1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹 연습하기 #1 Stack Permutation C++ 순열을 구하기위해 dfs를 사용했는데 visit 배열 대신 stack을 사용해서 구현해보았음 n이 8이 넘어가면 하루종일 걸려요.. 모든 경우의 수를 출력해주기 때문에 어쩔 수 없다 if(node == N) 부분의 for hyeo-noo.tistory.com 이전에 스택을 이용해 permutation을 구현한 코드처럼 C개의 문자중에서 L개를 뽑는 경우를 모두 출력하는 문제이다 추가된 조건들 암호를 이루는..