Algorithm/dfs

[틀림] 백준 17822 원판돌리기 // 구현, 배열회전, 원형 dfs

https://www.acmicpc.net/problem/17822* 틀린풀이인접한것들 지우는 idea (좌우, 상하 1개씩만 비교)반례 : 3단 인접인경우, 처리가 안됨dfs를 해야하나? * 정답풀이원형 dfs에서 next 계산방법else if 주의수정후 else if 안하면 바로 조회하기때문에 오답이됨. else if 써야함. #includeusing namespace std; int n,m,t,ret, vis[54][54];int x,d,k, found;vector v[54];const int dy[] = {-1, 0, 1, 0}; // 상, 우, 하, 좌 (y 방향)const int dx[] = {0, 1, 0, -1};void calc() { for(int i=0;i rotate(..

[알고리즘] 리트코드 417. Pacific Atlantic Water Flow c++ // dp

https://leetcode.com/problems/pacific-atlantic-water-flow/ * 완탐모든좌표에대해 모든곳을 가보면서 갈수있는지 검사함O(N * M * N * M )int dy[]={1,0,-1,0};int dx[]={0,1,0,-1};vector> heights;vector> ret;int vis[204][204],dp[204][204]; //해당좌표에서 바다로 갈수있는지int n,m;int a,b;class Solution {public: //해당좌표가 pacific바다로 갈수있는지, 좌-우 탐색 void dfs(int y, int x){ // if(x =m || y>=n){ // can go atlantic // b=1; ..

리트코드 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.net1.의사코드 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,int G,int NA)..

[맞음] 백준 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.net1.의사코드dfs(n) : n번째사람이 1팀으로가거나 2팀으로 가거나... 이진트리탐색dfs(a, b) : 1팀들의 리스트, 2팀들의 리스트계산부분 : 2중반복문으로 해결v : 0 1 2 ij(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팀으로감or2팀으로감voi..

백준 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..