본문 바로가기

Algorithm/DFS

 (43)
(C++) - 백준(BOJ) 6603번 : 로또 (DFS) 답 https://www.acmicpc.net/problem/6603 [ 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net ](https://www.acmicpc.net/problem/6603) 간단한 Back tracking 문제였습니다. 풀이방법 : 정적 배열이용 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 //DFS 문제입니다. 거꾸로 노드를 거슬러 올라가..
(C++) - 백준(BOJ) 2210번 : 숫자판 점프 답 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net DFS문제였습니다 문제풀이 : 5 X 5 숫자판에서 각 판을 시작점으로하여 동서남북 4방향에 대해 dfs를 실행하면 됩니다. 그리고 겹치는 탐색에 대해서는 자료구조 set을 이용해 중복을 제거했습니다. 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..
(C++) - 백준(BOJ) 1987번 : 알파벳 답 https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net DFS문제였습니다 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..
(C++) - 백준(BOJ) 9663번 : N-Queen 답 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 문제였습니다. 행을 기준으로 각 열에서 퀸이 놓일 수 있는 자리를 체크하고 dfs하였습니다. 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 #include #include using namespace std; int n; int board[16]; int ans; //행..
(C++) - 백준(BOJ) 1039번 : 교환 문제링크 : https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 메모이제이션을 사용한 DFS 백트래킹 브루트포스 문제였습니다. 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 #include #include #include #include using namespace std; int m,k; string n; int ck[1000001]; int cnt ..
(C++) - 백준(BOJ) 1182번 : 부분수열의 합 문제링크 : https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 조합으로 뽑았을 때 부분수열들이 중복될 경우도 고려했었는데 그런걸 고려하는 문제가 아닙니다 문제입력 : 4 16 1 7 9 9 output : 2 3번째 9와 2번째 7 뽑는것과 4번째 9와 2번째 7을 뽑는것은 다르다고 보는 것 같습니다. 요거 몰라서 고생했습니다..낄낄 마찬가지의 테스트 케이스입니다. 문제입력 : 2 0 0 0 output : 3..
(C++) - DFS 유형 DFS는 주로 재귀함수를 사용하며 백트래킹, 브루트 포스에 자주 이용하는 탐색 방법입니다. 고려할 점은 다음과 같은 3가지입니다. 1. 조합으로 뽑을 때 2. 같은 부분 집합을 출력하면 안될 때 3. 순열로 뽑을 때 순서 상관없이 막 뽑을 때
(C++) - 백준(BOJ) 15664번 : N과 M (10) 문제링크 : https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 출력은 무조건 오름차순, 중복 출력하지 않아야 합니다. 풀이방법 1. set으로 중복된 상태를 저장하지 않게 하는 방법 2. 해당 level의 수를 한 번 뽑았다면 뽑지 못하도록 만드는 2차원 배열을 사용하는 방법 Code 1. set으로 푼 코드 #include #include #include #include using namespace std; int n, m; int..

티스토리툴바