Algorithm/dfs

리트코드 1325 리프노드지우기 c++

https://leetcode.com/problems/delete-leaves-with-a-given-value/description/?envType=daily-question&envId=2024-05-171. 의사코드dfs 기반으로, dfs(현재노드)내좌측, 우측을 탐색하는데1. 기저사례 : 내가 null이면 null을 반환2. 양쪽자식이 null 이고 내가 타겟이면 nullptr 반환리프노드의 자식을 null로 명시적으로 대입해주는 코드가 인상깊었다.  2. 전체코드 #include class Solution {public: TreeNode* removeLeafNodes(TreeNode* root, int target) { if(root==nullptr) return nullptr;..

백준 14888 연산자끼워넣기 c++ // dfs

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 1.의사코드 2. 전체코드 v: 5 6(i+1) a: +(i) #include using namespace std; int N,p,m,g,na,ret1=-1000000000 -1; int ret2 = 1000000000+1; vector v; //n번째자리, 들어갈연산 void dfs(int n, vector a,int P,int M,in..

백준 14889 스타트와링크 c++ // dfs, 사람기준으로 생각하라. 일단 모든경우의수를 벌려놓고 생각하라

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 1.의사코드 dfs(n) : n번째사람이 1팀으로가거나 2팀으로 가거나... 이진트리탐색 dfs(a, b) : 1팀들의 리스트, 2팀들의 리스트 계산부분 : 2중반복문으로 해결 v : 0 1 2 i j (i,j) : 0,0/ 0,1 /0,2 /1,0 ... 2. 전체코드 #include using namespace std; int N,M,arr[24][24]; int ret = 987654321; //n번째사람이 1팀..

백준 2573 빙산 c++ // dfs, 구현, year에 대해 반복문 만들기

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. 의사코드 일단 분할정복으로 문제를 나눈다 1. 뺄셈할 값을 계산하기 2. 원본배열에 더하기 3. 구역세기 위 1,2,3을 year에 대해 반복하기! 2. 시행착오 1. 매year(tc)마다 vis, b배열을 초기화 해주어야 한다! 2. 구역세는 코드는 외울것. 3. 전체코드 #include using namespace std; int n,m,cy,cx; int dy[] = { 1,0,-..

프로그래머스 소수찾기 c++ // 순열 3P1+3P2+3P3 하는방법, 소수판별함수, dfs

https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 순열 3P1+3P2+3P3 하는방법 do{ string s=""; for(int i=0;i

프로그래머스 미로탈출명령어 c++ // dfs 가지치기 방법, dfs중복방문 방법, dfs 시간복잡도 계산방법

https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. dfs중복방문 방법 그냥 visit처리안하고 depth==k일때 리턴하면 된다. 2. dfs 시간복잡도 계산방법 dfs(0) :dfs(상) dfs(하) 좌 우 dfs1번당 자식4개 생김 깊이:k ex)k==2일때, 자식==16(4^2) 복잡도 : 4*4*4*4*4(깊이만큼) == 4^k승 3. dfs 가지치기 방법 1. 사전순으로 dy,dx정함 -> 첫답이 최적해임 -> 첫답을 찾았으면 f..

백준 1759 암호만들기 c++ // 포함불포함 완탐 dfs, 순열시간초과 나는경우 해결

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1. 순열시간초과 나는경우 해결 15! == 시간초과 해결 -> 포함,불포함 완탐 (2^15 == 32768) 2. 전체코드 #include using namespace std; int l, c, visited[16]; vector v; int mo[128]; //현재까지 k번인덱스까지 포함,미포함 판단함 / 모음갯수/ tempStr void dfs(int k, int cnt, string s) { i..

프로그래머스 단어변환 c++ dfs ,백트래킹 // dfs 조건있는경우 해결방법

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. dfs 조건있는경우 해결방법 check함수를 만들고 if(check) continue 하면된다! 2. 삽질과정 단어길이가 3고정인줄알고 check-> if(count==2) return 1 ; 하드코딩했다가 맞왜틀? 하였다... 3. 전체코드 #include using namespace std; int visited[54]; int n,answer, is_possible,word_size; ..