Algorithm/DFS (43) 썸네일형 리스트형 (C++) - 백준(BOJ) 17070 : 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 모든 경우를 backtracking으로 탐색해 해결한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. 집 한변의 길이 n, 집의 구조를 입력받을 2차원 배열 house, n행 n열에 도착하는 경우의 수를 출력할 cnt를 선언합니다. 2. 길이 n행 또는 n열을 초과하는 모두 벽으로 생각해 house의 값들을 모두 1로 초기화해줍니다. 3. 1행 1열 ~ n행 n열까지 .. (C++) - 백준(BOJ) 1595번 : 북쪽나라의 도로 https://www.acmicpc.net/problem/1595 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net dfs로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 인접 도시로 가는 경로가 1개인 연결그래프는 트리입니다. 이 트리구조를 저장하기 위해 struct Edge를 만들어 양방향그래프를 저장합니다. 📔 풀이과정 단순히 건너간 간선이 최대라고 거리까지 최대가 되지는 않습니다. 또한 어떤 도시에서 다른 도시로 갈때는 말단 노드(도시)를 경유지로 가면 안됩니다. 출발도시에서 말단 노드(도시)로 가는 .. (C++) - 프로그래머스(위클리 챌린지) : 5주차 https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 5주차 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 조합 + 정렬문제였습니다. 📕 풀이방법 📔 입력 및 초기화 나올 수 있는 모든 형태의 문자열을 저장하기 위한 vector변수 dictionary를 선언합니다. 📔 풀이과정 1. 나올 수 있는 모든 문자열을 dictionary에 push해줍니다. 2. 자리마다 확인하며 사전상 앞에 오는 문자 순으로, 자리수에 대한 오름.. (C++) - 백준(BOJ) 17478번 : 재귀함수가 뭔가요? https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 재귀함수를 이해하기 좋은 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n을 입력받습니다. 📔 풀이과정 1. 기저 조건 세우기 : depth == n이면 출력 후 종료합니다. 2. 재귀 수행 : dfs함수 호출 전 본문 출력하고, dfs함수 호출 합니다. dfs함수가 종료되면 "라고 답변하였지."를 출력합니다. 📕 Code //재귀함수가 뭔가요? #include using namespace st.. (C++) - 백준(BOJ) 20166번 : 문자열 지옥에 빠진 호석 https://www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net dfs문제였습니다. 📕 풀이방법 k를 입력받을 때마다 dfs를 수행한다면 tle입니다. 따라서 전처리로 dfs 후 k를 입력받아야 합니다. 📔 입력 및 초기화 n,m,k 입력 후 문자열 배열 board에 적절히 입력받습니다. 📔 풀이과정 1. n행 m열을 모두 돌며 board[i][j]를 시작점으로 dfs를 수행해 줍니다. 2. dfs 수행 시 만든 문자열을 모두 map에 넣어줍니다. 해당 문자열의 value를 1씩 증가시킴으로써 경우의 수를 구할 수 있습니다. 📔 정답출력 k만큼.. (C++) - 백준(BOJ) 5568번 : 카드놓기 https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 순열문제였습니다. 풀이방법 1. 자기자신을 뽑지 않으면서 순서 상관있도록 뽑으면됩니다. 2. 카드를 뽑았으면 카드들을 나열한 뒤 set에 넣어줍니다. 3. set의 size를 출력합니다. Code #include using namespace std; int n,k; vector card; set cardSet; vector tmp; int ck[11]; void dfs(int depth){ if(depth == k){ string c; for(auto t : tmp) c += t; cardS.. (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정보에 대해 이익을 갱.. 이전 1 2 3 4 5 6 다음
