본문 바로가기

Algorithm/DFS

 (43)
(C++) - 프로그래머스(2017 카카오 코드 본선) : 단체사진 찍기 programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 순열 구현문제였습니다. 풀이방법 8!의 모든 순열을 확인하면서 data의 조건에 부합하는지를 확인하면 됩니다. 8! * 100 < 1억번 연산이므로 1초 이내로 문제를 해결할 수 있습니다. 따라서 next_permutation함수를 사용하면 됩니다. Code #include using namespace std; bool isOk(string friends, char a, c..
(C++) - 프로그래머스(2019 카카오 개발자 겨울 인턴십) : 불량 사용자 programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr dfs 구현 문제였습니다. 풀이방법 1. 하나의 banned_id에 해당하는 user_id들을 index로 뽑아 저장합니다. 예제2의 경우 "*rodo" 에 해당하는 [0,2] index를 저장해줍니다. 마찬가지로 나머지 "*rodo", "******"에 대해 [0,2], [3,4]를 저장해줍니다. 2. 목록을 dfs로 뽑아준 후 map에 저장해줍니다. [0,2,3], [0,..
(Javascript) - 프로그래머스(고득점 kit : 동적계획법) : N으로 표현 programmers.co.kr/learn/courses/30/lessons/42895?language=javascript 코딩테스트 연습 - N으로 표현 programmers.co.kr backtracking으로 푼 문제였습니다. 풀이방법 모든 경우의 수를 dfs를 사칙연산에 대해 계속 호출하는 방식으로 해결했습니다. Code let ans = 0x3f3f3f3f; let n, num; function dfs(depth, sum) { if (depth > 8) return -1; if (sum == num) { ans = Math.min(ans, depth); return; } let tmp = 0; for (let i = 0; i < 8; i++) { tmp = tmp * 10 + n; dfs(dep..
(C++) - 프로그래머스(월간 코드 챌린지 시즌2) : 모두 0으로 만들기 programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr dfs로 푼 문제였습니다. 풀이방법 1. cost를 모두 더했을 때 0이 아니라면 -1을 반환합니다. 2. 그래프를 인접리스트로 재구성합니다. 3. dfs를 시행합니다. 어떤 정점에서 시작해도 모든 정점을 확인하기 때문에 정답을 구할 수 있습니다. 연결된 모든 정점을 확인하면서 다음 정점의 cost 절댓값을 ans변수에 더해줍니다. 현재 정점의 cost는 n..
(C++) - 백준(BOJ) 12101번 : 1, 2, 3 더하기 2 www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net backtracking문제였습니다. 풀이방법 1. 1,2,3중에 중복가능하게 i개를 골라 식을 만들었을 때 num과 같다면 vector 변수 ans에 넣어줍니다. 2. 매번 3개의 분기로 호출이 되므로 시간복잡도는 i * 3^i 가 됩니다. Code #include using namespace std; int n,k; vector ans; void backtracking(int idx,int m,int num,string op){ if(idx ..
(C++) - 백준(BOJ) 13023번 : ABCDE www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net dfs문제입니다. 풀이방법 1. 인접리스트로 친구관계를 만들어줍니다. 친구 사이니 양방향 그래프가 됩니다. 2. dfs를 수행합니다. 확인하지 않는 친구사이들 중에 dfs가 5번 호출이 되었다는 뜻은 조건에 부합하다는 말입니다. ABCDE순으로 dfs가 호출되었다면 해당 관계가 존재한다는 뜻으로 1을 return해줍니다. 3. 자신과 연결된 모든 친구관계를 확인했다면 자신을 통해 다른 친구관계를 확인할 수 있도록 자신을 체크했던것을 0으로 만들어줍니다. Code #include using namespace std; ..
(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번째 문자..

티스토리툴바