Algorithm/back_tracking

[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)..

백준 16987 계란으로 계란치기 c++ // 백트래킹, 원상복구, 다음깊이로 넘어가는 방법

https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 1. 다음깊이로 넘어가는 방법 if(조건){ go(k+1); return; } 하면된다. 2. 의사코드 3. 내 전체코드 #include using namespace std; int n, v[10], ret; vector eggs; //현재 k번째 계란을 들고 깨려고함 void go(int k) { if (k >= n) { int died_count = 0; for (auto p :..

백준 1941 소문난 칠공주 c++ // 1차원배열을 2차원좌표로 매핑하는법 , 백트래킹, dfs

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 1. 1차원배열을 2차원좌표로 매핑하는법 1차원 idx : 0 1 2 3 4 5 6 7 8 9 ...... 24 2차원 : (0,0) (0,1) .... (4,4) y좌표 == 1차원idx /5 x좌표 == 1차원 idx %5 하면 된다! 2. 풀이과정 1. 25C7로 인덱스를 조합한다. (방문할 대상들의 좌표를 조합) 2. idx로 배열에 접근 후 , s_cnt>=4인지 검사 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ..

백준 6603 로또 c++ // kC6 구현하기

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 조합 - isused사용 => 중복조합아님 2. 전체코드 #include using namespace std; int n,k; int a[15], isused[15], arr[15]; //현재 q개뽑았음 void go(int q) { if (q == 6) { for (int ..