본문 바로가기

Algorithm/DFS

 (45)
(C++) - 백준(BOJ) 2580번 : 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net backtracking문제였습니다. 풀이방법 1. 해당 행의 1 ~ 9사이의 수를 확인했다는 것을 나타내기 위해 2차원 배열들을 사용합니다. rowCk[i][num]은 i행의 num은 이미 확인되었다는 뜻입니다. 같은 방식으로 colCk[j][num]은 j열의 num을 확인했다는 뜻이고 squareCk[(i / 3) * 3 + (j / 3)][num]은 정사각형을 떼어 생각했을 때 몇 번째 칸의 ..
(C++) - 프로그래머스(2021 Dev-Matching: 웹 백엔드 개발자) : 다단계 칫솔 판매 https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr backtracking 으로 푼 문제였습니다. 풀이방법 1. 각 판매원들의 추천인들이 곧 graph로 따지면 parent node가 됩니다. 이 정보를 적절한 자료구조로 저장한다면 graph형태로 나타낼 수 있습니다. "-"는 root라고 생각하고 서순을 지키기 위해 unordered_map을 사용해 저장합니다. 2. 모든 seller정보에 대해 이익을 갱..
(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; ..

티스토리툴바