목록백트래킹 (9)

Doby's Lab

[알고리즘] 백준 2580번: 스도쿠 (C++), exit(0); 백트래킹 보완

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 이번 문제는 공부할 포인트가 많았다. 글과 코드가 꽤 길기 때문에 앞서 공부할 내용을 정리하면 배열의 역할, 발상의 전환 exit(0); -> 프로그램 자체 종료 DFS에서 다음 좌표값도 넘겨주기 (시간 소요 줄임) 처음엔 백트래킹을 생각하지 않고 풀려했다. 스도쿠 표를 1행 1열부터 탐색하면서 0이면 check함수를 콜 하여 그 자리에 들어올 수를 넣어주었다. 허나, 아래 코드를 보면 이 방법이..
PS/BOJ 2021. 12. 18. 03:53
[알고리즘] 백준 15658번: 연산자 끼워넣기 (2) (C++)

https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net 연산자 배열을 선언 후 각 연산자를 고른 경우 총 4가지를 가지고서 백트래킹 하면 된다. #include #include #include #include #include using namespace std; int n; vector num; int oper[4] = { 0, }; int maxValue = INT_MIN; int minValue = INT..
PS/BOJ 2021. 11. 28. 13:56
[알고리즘] 백준 10819번: 차이를 최대로 (C++)

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 범위가 8밖에 되지 않아서 백트래킹으로 나올 수 있는 수열들을 temp 배열에 담아 직관적으로 풀 수 있는 문제였다. abs() == 절댓값 함수 #include #include #include #define MAX 8 + 1 using namespace std; vector v; vector temp; int n; bool visited[MAX]; int maxValue = 0; void sol(vector&..
PS/BOJ 2021. 11. 28. 13:46
[알고리즘] 백준 6443번: 애너그램 (C++), 백트래킹 중복 처리 유형 2번째!

https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 단순한 백트래킹 문제인 줄 알았으나 꽤 조건이 까다로운 문제다. 허나, 이 조건은 예전에 N과 M 시리즈를 풀 때도 한 번 크게 겪었던 똑같은 유형이었다. (N과 M (9) 문제: https://www.acmicpc.net/problem/15663) (N과 M (9) 포스팅: https://draw-code-boy.tistory.com/29) 이 문제에서 필요한 건 정렬과 이전 노드(같은 d..
PS/BOJ 2021. 11. 15. 04:53
[알고리즘] 백준 9663번: N-Queen, Backtracking의 대표 문제

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N-Queen 문제는 백트래킹 알고리즘의 대표 문제라고 할 만큼 백트래킹하면 N-Queen 문제를 사람들이 많이 떠올린다. 하지만, 백트래킹을 이제 막 배우고, 겨우 구현할 수 있는 시점이라면 백트래킹을 공부하는 데에 있어서 당장 이 문제를 추천하고 싶진 않다. 백트래킹을 대표하는 문제이기는 하되 접근성이 쉬운 문제는 아니기 때문이다. 처음에 접근할 때는 2차원 배열로 접근을 했다. goQueen이라는 함수를 선..
PS/BOJ 2021. 11. 8. 05:58
[알고리즘] 백준 2023번: 신기한 소수 (C++), 음..? 신기한 문제네

논리 입력으로 4가 주어지면 4자리 수 중에 예를 들어 7331이면 맨 앞자리부터 7, 73, 733, 7331처럼 모두 소수가 되어 만족하는 수들을 구하는 문제였다. 논리를 이렇게 짜두고 코드는 반대로 7331, 733, 73, 7 순서로 소수인지 판별했다. 하지만, 이는 시간 초과를 유발한다. 그래서 반대로 맨 앞자리부터 소수 판정을 하는 코드를 짰다. 왜냐하면 극단적으로 8자리 수가 주어졌을 때, 8자리 수가 소수인지 판정을 하고 7자리 수가 소수인지 판정하는 것보다는 1자리 수가 소수인지 판정하고 그다음으로 넘어가는 형식이 더 빠르기 때문이다. 그래서 다음과 같이 코드를 짰다. (맨 처음의 수를 기억하고 있어야 하기 때문에 solution 함수에서 answer에 초기값을 넣어줬다.) #includ..
PS/BOJ 2021. 10. 1. 08:56
[알고리즘] 백준 14889번: 스타트와 링크 (C++), 복합형 문제, 백트래킹의 pruning

이번 문제는 처음으로 겪어보는 복합형(?) 문제였다. 여러 고난이 있었는데 고난을 겪었던 코드들을 읽어보면서 어떻게 정답에 도달했는지 알아보자. 논리를 어떻게 접근할까 (첫 번째 고난) 스타트팀 링크팀을 각각 나눠서 능력치를 더하고 비교해서 최솟값을 어떻게 구할지 논리에서 막혔었다. 1시간 정도 고민하다가 문제들을 분할시켜보았다. 1. 스타트 팀, 링크 팀 나누기 2. 각 팀 능력치 더하기 3. 각 팀 능력치의 차 값 구하기 4. 차 값의 최솟값 구하기 4개 정도로 분할시켜 하나씩 진행할 수 있었다. #include #include #include using namespace std; int n; bool visited[2001] = { 0, }; bool visited2[1001] = { 0, }; v..
PS/BOJ 2021. 9. 29. 20:37
[알고리즘] 백준 15663번: N과 M (9) (C++), 도식화의 중요성

(추가 내용 2021.11.15) https://draw-code-boy.tistory.com/96 [알고리즘] 백준 6443번: 애너그램 (C++), 백트래킹 중복 처리 유형 2번째! https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램 draw-code-boy.tistory.com 비슷한 문제가 나와서 정리해두었다. 백트래킹의 코드 구조를 익히면서 [N과 M 시리즈]를 풀고 있었다. 이번 문제에서 막히게 되었는데 해당 문제에서 이런 걸 요구했기 때문이다. 'N이 4이고, M이 2일 때, 9 7 9 1의 수들로 부분 수..
PS/BOJ 2021. 9. 19. 00:28
이전 Prev 1 2 Next 다음