본문 바로가기

Algorithm197

[실전 알고리즘] 백트래킹 백트래킹 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 연습문제 1- N과 M [백준 15649] N과 M (1) - 백트래킹 (tistory.com) 연습문제 2- N-Queen [백준 9663] N-Queen (tistory.com) 연습문제 3- 부분수열의 합 [백준 1182] 부분수열의 합 (tistory.com) STL next_permutation next_permutation - C++ Reference (cplusplus.com) 왼쪽 그림이 순열(순서 상관 있음) , 오른쪽 {0,1} 넣어서 구현하는게 조합(순서 상관 없음) 조합에서 5개에서 3개를 뽑는 문제라면 배열 a를 {0, 0, 0, 1, 1}로 두면 됨 출처 BaaaaaaaarkingDog | [실전 알고리.. 2022. 9. 15.
[백준 1182] 부분수열의 합 1182번: 부분수열의 합 (acmicpc.net) 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 정답 풀이 #include using namespace std; int n, s; int arr[30]; int cnt = 0; void func(int cur, int tot){ if(cur == n){ if(tot == s) cnt++; return; } func(cur+1, tot); func(cur+1, tot+arr[cur]); } int main(void) { io.. 2022. 9. 15.
[백준 9663] N-Queen 9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 정답 풀이 #include using namespace std; bool isused1[40]; // column을 차지하고 있는지 bool isused2[40]; // / 방향 대각선을 차지하고 있는지 bool isused3[40]; // \ 방향 대각선을 차지하고 있는지 int cnt = 0; int n; void func(int cur) { // cur번째 row에 말을 배치할 예정임 if (cur == n) { // N.. 2022. 9. 15.
[백준 15649] N과 M (1) - 백트래킹 15649번: N과 M (1) (acmicpc.net) 배운것 백트래킹의 핵심은? 1. 현재 위치 어디인지 확인하기 2. 가지치기- isused 체크 해주고 체크 해제 해주기 정답 코드 #include using namespace std; int n,m; int arr[10]; bool isused[10]; void func(int k){ // 현재 k개까지 수를 택했음. if(k == m){ // m개를 모두 택했으면 for(int i = 0; i < m; i++) cout m; func(0); } 2022. 9. 15.
[백준 2447] 별 찍기 -10 2447번: 별 찍기 - 10 (acmicpc.net) 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 정답 풀이1 #include using namespace std; char board[2300][2300]; // solve(n, x, y) : board[x][y] to board[x+n-1][y+n-1]에 올바르게 '*'과 ' '을 넣는 함수 void solve(int n, int x, int y) { if (n == 1) { board[x][y] = '*'; return; }.. 2022. 9. 14.
[백준 2206] 벽 부수고 이동하기 2206번: 벽 부수고 이동하기 (acmicpc.net) 배운것 체크용 배열을 2개 만드는 방법도 있겠지만 3차원 배열을 만들고 변수를 하나 더 둬서 적용시킬 수도 있음 정답 코드 #include using namespace std; #define X first #define Y second int dx[4] = {0,1,0,-1}; int dy[4] = {1,0,-1,0}; char board[1000][1000]; int dist[1000][1000][2]; // dist[x][y][0] : 벽을 하나도 부수지 않고 (x,y)까지 오는데 걸리는 비용 // dist[x][y][1] : 벽을 하나만 부수고 (x,y)까지 오는데 걸리는 비용, (x,y)가 벽이라서 부수는 경우 포함 int n, m; int.. 2022. 9. 14.

티스토리툴바