Mini

https://www.acmicpc.net/problem/5430  * 풀이1#include using namespace std; int t;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >>t; while(t--) { string s1,s2; int n; cin>>s1>>n>>s2; deque d; if(s2!="[]") { s2 = s2.substr(1,s2.size()-2); // [, ] 날리기 string buf=""; for(auto c : s2) { if(c==',') { d...

https://www.acmicpc.net/problem/13244* Tree의 조건노드수 == 간선수+1 이어야함모두 연결되어 있어야함 // connected component 는 int dfs 결과가 n과 같아야함 * 전체코드#include using namespace std; int t,n,m, vis[1004];vector adj[1004];int dfs(int here) { vis[here]=1; int ret=1; for(auto nxt : adj[here]) { if(vis[nxt]) continue; ret += dfs(nxt); } return ret; }int main(){ ios_base::sync_with_stdio(0); cin.t..

* 요약차원을 2차원으로 바꾸는힘i*m + j 암기!!!!i*m + j 공식이 어떻게 2차원 배열을 1차원으로 변환하는지 설명예를 들어 2x3 배열이 있다고 해보죠:1 2 34 5 6이 공식이 작동하는 방식을 단계별로 설명하겠습니다:각 행(i)마다 건너뛰어야 하는 개수:첫 번째 행(i=0): 0개 건너뜀 (0*m)두 번째 행(i=1): m개 건너뜀 (1*m)세 번째 행(i=2): 2m개 건너뜀 (2*m)열 위치(j)를 더하기:j=0: 첫 번째 열j=1: 두 번째 열j=2: 세 번째 열예시로 (1,2) 위치의 경우:i=1, j=2, m=3일 때1*3 + 2 = 5즉, 1차원 배열에서 5번 위치가 됨이렇게 변환하는 이유:비트마스크는 1차원으로만 동작2차원 위치를 1차원으로 고유하게 매핑해야 함각 위치가 겹치..

https://www.acmicpc.net/problem/2234 * 풀이1connted component, 구역수 세기는 잘 풀었다.int dfs, 전체에대해 dfs돌리면서 cnt를 세면됨방문조건에 bit가 들어간다.dy,dx에 따라 동서남북을 체크하고 해당비트가 꺼져있으면 next로 이동한다.문제는 벽을하나씩 부스는것이 문제다.첫풀이벽을하나씩 부스면서 (i번째 bit를 끄면서) 똑같이 dfs를 돌리고, 원복하면 될거라고 생각했다.문제점이웃한 벽도 같이 부서줘야함매번 dfs 돌기전에 vis를 초기화 해줘야함현재는 벽제거후 그곳에서만 dfs호출, 벽을제거한후 모든 지점에서 dfs를 호출해야 완탐이됨//n^2 C 1 * 4(동서남북) 벽제거 memset(vis,0,sizeof(vis)); f..

https://www.acmicpc.net/problem/1062* 내 풀이최초풀이 : 막구현 -> 26C13 (최악의경우) = 1천만 -> 시초a,n,t,i,c는 무조건 뽑아야함 -> 미리선택, 비트켜기입력: N, K 입력받기 N개의 단어 입력받아 arr에 저장필수 처리: if K #include using namespace std;typedef long long ll;int n,k,ret;int study[26];vector arr;void go(int subset) { memset(study,0,sizeof(study)); for(int i=0;i v) { if(v.size()==k) { memset(study,0,sizeof(study)); fo..

https://www.acmicpc.net/problem/14890* 문제 해결 방식문제 단순화하기처음에는 "한 줄"만 생각합니다.- 가로 한 줄에서 경사로를 어떻게 놓을 수 있을까?- 어떤 조건에서 경사로를 놓을 수 있고, 없을까?상태 추적하기현재 상황을 추적할 변수가 필요함을 깨닫습니다.- 같은 높이가 몇 칸 연속되는지- 경사로를 놓고 있는 중인지=> 이 두 가지를 하나의 변수(cnt)로 표현할 수 있다!패턴 발견하기높이 차이에 따른 패턴을 분석합니다:1. 같은 높이: 여유분 증가2. 오르막: 이전 여유분 필요3. 내리막: 앞으로의 공간 필요최적화하기가로/세로 방향 체크를 같은 로직으로 처리하려면?=> 전치행렬을 사용하면 동일한 함수로 처리 가능!엣지 케이스 생각하기- 연속된 경사로가 필요한 경우- ..

https://www.acmicpc.net/problem/1987* 고민했던 부분비트마스킹 발상하기N이 30미만 -> 비트마스킹 도전 -> vis를 숫자 1개로 나타내보자.알파벳을 숫자로 표현하기A - 'A' =0B-A = 1 C-A = 2...A를 1로 (1B를 2로 (1C롤 4로 표한하면 되겠다! (11을 알파벳-'A'만큼 밀면 현재 비트가 나온다! // (1i번째 비트가 켜진것을 확인하기(상태 & 현재비트) !=0 -> i번째 비트는 켜진것. -> already visited주의사항비트연산에는 항상 괄호를 사용할것!모든 탐색이 끝나고 return 될때 정답갱신하는 부분을 어디에 둘지* 의사코드알고리즘: 알파벳 보드에서 중복되지 않는 알파벳으로만 이동하는 최장 경로 찾기입력:- R: 보드의 행 개수-..

https://www.acmicpc.net/problem/19942* 개선할점비트마스킹 패턴 암기필요subset 은 정수 1 부터 2^n -1 (255)까지이를 비트연산 하면서 비트가 켜져있으면, 해당 원소를 선택한다.if문아래에 로직을 넣는다.이때, 선택된원소들은 1-idx이므로 i+1 해준값을 결과에 저장한다.정답이 여러개인 경우map>>에 가격별 정답후보들을 담는다. // m[300] : {1,2,3 / 4,5,6}이를 정렬후 m[ret][0]을 꺼내면 원하는 idx들이 출력된다. * 전체코드#include using namespace std;typedef long long ll;int n,mp,mf,ms,mv;int arr[16][6];int ret=987654321; //최소비용구하기, 초기화=..