Algorithm/back_tracking

[틀림] 백준 13023 ABCDE // vis 초기화(백트래킹) 필요한 이유

https://www.acmicpc.net/problem/13023* 백트래킹 복습depth가 5이상인지 검사이때, vis=0으로 백트래킹 필요즉, 원복시키면서 완탐을 하려고 원상복귀를  하는것이다.완탐을하려면 원복이 필요!  * 풀이#includeusing namespace std; typedef long long ll;int n,m,ret;int vis[2004];vector adj[2004];int dfs(int cur, int depth) { if(depth==5) { cout>n>>m; for(int i=0;i>a>>b; adj[a].push_back(b); adj[b].push_back(a); //a와 b가 친구 -> 양방향맞음 } for(int ..

[틀림] 백준 17136 색종이 붙이기 // 구현, 원복

https://www.acmicpc.net/problem/17136* 풀이dfs로 한칸씩 보면된다.요령은없다.구현은 추상화, 분리가 핵심..5개제한 -> 카운팅스타? 맵또는 배열가지치기cnt가 ret보다 크다면, 해당 경로는 유망하지 않으므로 가지치기하면 더 최적화 가능#includeusing namespace std; typedef long long ll;int ret=987654321; //맵크기, 나무수, k년int a[14][14];int n=10;map m; ////좌표에 sz의 색종이를 놓을수 있는지int check(int y, int x, int sz) { //범위쳌 //n인경우는 dfs에서검사함 -> 제외 if(y+sz>n || x+sz>n) return 0; for(int ..

[틀림] [알고리즘] 백준 17825 주사위윷놀이 // 완탐 , 구현, 인접리스트, 백트래킹

https://www.acmicpc.net/problem/17825* 틀린풀이그리디 (틀린풀이)먼저 완탐이 되는지 봤어야함인접리스트 사용안하고 vector 여러개로 구현하다보니 너무 복잡... gg * 정답풀이adj로 2개 연결하는것도 표현값은 v에, index는 adj에 저장 // 값과 index를 분리해서 저장하라.adj.size로 특수이동인지 판별백트래킹으로 모든 경로 확인#includeusing namespace std; const int INF = 987654321;// 게임에 필요한 전역 변수들int a[14]; // 주사위 값을 저장하는 배열int mal[4]; // 4개의 말의 현재 위치를 저장하는 배열int n = 10; // 총 주사위 던지는 횟수int v[104]; /..

[Algo] 백준 소문난칠공주 c++ // 조합, 완탐, 갯수세기는 int dfs

일단 이문제는 2번째 푸는  문제이다.근데 못풀었다...모 기업 코테에서 비슷한 문제가 나와 다시 복습하였다. * 못푼이유설계도가 없으니 중간에 막히면 코드만 수정함 -> 점점 스파게티가 되어 망하였다. 아래정도 설계는 꼭하자!* 의사코드25C7 구현vector를 넥퍼돌리면서 1인부분의 idx를 selected에 넣으면된다.이때, 지도에도 표시해둔다. //나중에 선택된곳만 갈수있도록 제한해야하니까.i/5, i%5를 이용해, 값을 2차원으로 바꿔준다.이다솜 cnt > = 4 구현selected를 순회하면서 arr을 검사한다.이후 4이상인 경우만 dfs 검사로 보낸다.이때, selected 중 아무 좌표나 하나 보내면 된다.dfs 구현 - version 1dfs는 연결된 갯수가 7개이면, 정답을 +1 하면된..

[Algo] c++ next_permutation으로 조합 구현하기

//25C7 구현 // N개의 요소를 가진 벡터 생성, 뒤에서 K개만 1로 설정 n = 25; vector v(n); fill(v.end() - 7, v.end(), 1); int cnt = 0; do { cnt++; /*for (int i = 0; i

100C2 X 98 C 2 조합 구현

if(v==1) v1.push(index)else remain 백터에 넣는다.remain벡터에 대해서 다시 while_permutation을 반복한다. ex) 0 0 0 0 1 1 (v)idx : 0 1 2 3 4 5 -> v1=[4,5]-> remain : 0 0 0 0 -> 0 0 1 1-> 조합돌림v2 : [2. 3]

프로그래머스 상담원 인원 c++ // 우선순위큐, 중복조합(백트래킹)

https://school.programmers.co.kr/learn/courses/30/lessons/214288 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 의사코드i) 상담사 분배  경의의수 구현상담유형=5일때, 상담사=20명을 분배해야한다.이때, 최소 상담사는 1명씩 있어야한다. -> 15명을 5개칸에 분배해야한다[ 1 1 1 1 1] [ 0 0 0 0 0] 서로다른5자리에서 중복을포함해 15개를 고르면된다. ex) 첫째자리만 15번고르면 상담사가 [16 1 1 1 1]이 된다.중복조합의 구현은 st를두고, vis체크를 없애면 된다.모든 상담사..

프로그래머스 의상 c++ // 해쉬 , 경우의수 , 백트래킹

https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제해결 ex) 모자 : 3개 상의 : 2개인경우 모자 : 안입음, 1개입, 2개입, 3개입 상의 : 안입, 1개입, 2개입 모든경우의수 == 4*3==12 에서 안입는경우 -1을 하면된다. 2. 코드 #include using namespace std; int ret; map m1; map m2; int solution(vector clothes) { for(auto v : clothes)..