Algorithm/DFS (45) 썸네일형 리스트형 (C++) - 프로그래머스(2021 KAKAO BLIND RECRUITMENT) : 메뉴 리뉴얼 programmers.co.kr/learn/courses/30/lessons/72411?language=cpp 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr backtracking으로 푼 문제였습니다. 풀이방법 1. orders의 문자열 하나씩을 확인하여 정렬합니다. 이런식으로 정렬한다면 세번째 예제에서 'XWY'는 'WXY'로 정렬됩니다. 2. map으로 모든 orders문자열들을 보면서 각 알파벳이 몇 개씩 나왔는지 세줍니다. 2개 이상나온 알파벳들을 합쳐 새로운 문자열 candidates를 만들어 줍니다.. (C++) - 백준(BOJ) 17609번 : 회문 www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 재쉬를 이용해 푼 문제였습니다. 풀이방법 1. 분류기 함수를 만듭니다. 펠린드롬이면 0, 유사 펠린드롬이면 1, 이외의 경우엔 2를 반환하는 함수입니다. 2. 유사 펠린드롬인지 확인합니다 : left, right번째 문자를 확인하며 펠린드롬 여부를 결정합니다. left번째 right번째 문자열이 같다면 left +1, right -1 문자를 확인합니다. 아닌 경우 : 지울 문자열을 선택합니다. left번째 문자를 지우거나 right번째 문자.. (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.. 이전 1 2 3 4 5 6 다음