Algorithm/DFS (43) 썸네일형 리스트형 (C++) - 백준(BOJ) 2303번 : 숫자 게임 www.acmicpc.net/problem/2303 2303번: 숫자 게임 N명이 모여 숫자 게임을 하고자 한다. 각 사람에게는 1부터 10사이의 수가 적혀진 다섯 장의 카드가 주어진다. 그 중 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람이 게임을 이 www.acmicpc.net dfs 혹은 backtracking하며 brute force하는 문제였습니다. 풀이방법 1. 한 사람마다 5개의 카드를 입력 받은 후 3개의 숫자카드를 dfs로 뽑습니다. 뽑은 후에는 가장 일의자리가 큰 값을 return합니다. 2. 가장 큰 카드의 값, 사람번호 를 pair로 하여 vector에 push 합니다. 3. 가장 큰 카드의 값이 vector의 처음으로 오도록 내림차순, 그리고 만약 카드의 값이 .. (C++) - 프로그래머스(고득점 kit - (DFS/BFS)) : 타겟 넘버(DFS) 답 programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr dfs로 푼 문제였습니다. 풀이방법 1. 빼거나 더해서 depth == size까지 target과 같다면 1을 반환, 아니라면 0을 반환 2. dfs함수 호출 후 cnt를 반환 Code #include using namespace std; int dfs(int depth, int num, vector &numbers, in.. (C++) - 백준(BOJ) 1526번 : 가장 큰 금민수 답 www.acmicpc.net/problem/1526 1526번: 가장 큰 금민수 첫째 줄에 N이 주어진다. N은 4보다 크거나 같고 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net dfs로 모든 경우의 수를 탐색하는 문제였습니다. 풀이방법 2의 7승(100만의 자릿수 + 1) 정도로 dfs를 수행하면 됩니다. Code #include using namespace std; int n,ans; void dfs(int sum){ if (sum > n) return; dfs(sum * 10 + 7); dfs(sum * 10 + 4); ans = max(ans, sum); } int main(){ cin >> n; dfs(0); cout (C++) - 백준(BOJ) 1068번 : 트리 답 www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 트리를 만들고 dfs를 시행하는 문제였습니다. 풀이방법 1. tree를 생성합니다. 자식이 여러개일 경우를 대비해 자식이 추가될 때마다 vector push_back()을 이용합니다. 2. root node부터 dfs를 시행합니다. 지울 노드를 방문처리하게 되면 그 이하 자식들도 dfs를 하지않게 가능합니다. 2-1. 자식노드가 존재한다면 그 자식노드를 다음 dfs 호출의 인자로 넘겨줍니다. 2-2. 자식.. (C++) - 백준(BOJ) 1189번 : 컴백홈 답 www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K < R*C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R x C 맵의 정보를 나타내는 .과 T로 구성된 길이가 C인 문자열이 주어진다. www.acmicpc.net dfs를 이용해 구현 할 수 있는 문제였습니다. 풀이방법 1. T인경우 이거나 이미 방문한 경우에는 갈 수 없는 길입니다. 2. 방문을 한 후 dfs를 또 호출해 다음 길로 가며 호출 후에는 해당 길 방문했던 기록을 없앰으로써 다른 경로에서 온 경우를 제하는 것을 방지합니다. Code #include using namespace std; int dx[4] = {0,0,1,-.. (C++) - 백준(BOJ) 14503번 : 로봇청소기 답 www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net dfs를 이용한 구현문제였습니다. 풀이방법 나와 있는 조건을 검사하며 구현하시면 됩니다 Code #include using namespace std; int n,m; int board[11][11]; int ck[11][11]; //북 동 남 서 int dx[] = {-1, 0, 1,0}; int dy[] = {0, 1, 0,-1}; int area[51][51]; int visited[51][51]; int.. (C++) - 백준(BOJ) 11725번 : 트리의 부모 찾기 답 www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이방법 1. 입력을 받습니다. 받을 때 정점 사이의 간선들이 주어지므로 정점 n개를 가진 tree자료구조에서 간선들의 개수는 n-1개입니다. 따라서 그만큼 입력을 받고 vector에는 인접행렬 형식으로 양방향 간선을 추가해줍니다. 2. parent[x] 는 x정점의 부모에 해당하는 정점 번호가 값으로 들어갑니다. root node로부터 시작, 각 정점에 연결된 간선을 정보를 따라 만약 갱신되지 않은 부모배열 방이 있다면 갱신해줍니다. 즉, vector[1]이라는 정점에 연.. (C++) - 백준(BOJ) 1107번 : 리모컨 답 www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net backtracking으로 푸는 문제였습니다. 풀이방법 1. 고장나지 않은 channel 번호를 vector 배열에 저장합니다. 2. 모든 자리 수에 대해(1자리~7자리) 고장나지 않은 channel번호를 backtracking으로 대입하여 목표 channel에서 가장 가까운 channel을 구합니다. 3. 100번으로 시작해서 목표 channel로 가는 것과 backtracking하여 구해.. 이전 1 2 3 4 5 6 다음