Algorithm/boj

백준 13913 // bfs 경로추적은 prev[next]=here

13913번: 숨바꼭질 4 (acmicpc.net) 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net * bfs 경로추적 핵심코드 prev[10]=5 // prev[5]=3 .. 이런식으로 연결함. ex) 노드 : 5-10-11(목표k) 벡터 : 11(k)-10(prev[11]). 문제 : 첫노드는 안들어감 ,역순으로 넣어짐 해결 : push(start), 리버스 for (int next : {now - 1, now + 1, now * 2}) { //1. 범위체크 if (next..

백준 12869 //visit[체력][체력][체력]=최단거리(공격횟수) /visit idx를 체력으로 사용하라.

12869번: 뮤탈리스크 (acmicpc.net) 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net /* * bfs algorithm * 1.초기화 * 2.종료조건 * 3.next * 4.next 방문체크 * 5.visit[next] 갱신 */ *핵심로직 1. visit[체력][체력][체력] = 최단거리(공격횟수) 1.1 idx에 각각 체력저장. 2.v[0][0][0] 에 방문했다? -> bfs이므로 -> 최초 체력 0,0,0으로 만든애가 최단거리임. -> 출력. 끝. #include using namespace std;..

백준 16234 인구이동 // ny,nx만처리하는 bfs / main에서 v[y][x]처리 / vector &v로 함수내 전역변수 사용

16234번: 인구 이동 (acmicpc.net) 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net * dfs 조건처리는 contine만으로 가능, 빡구현필요X if (abs(a[y][x] - a[ny][nx]) r) continue; * for(v) 조건문실행되면 연결할게 있었다는 뜻 -> ret++, else break 조건문안에 flag=1 => 연결할게잇는지없는지 검사 !flag 이면, 종료. for (pair p : v) { a[..

백준 4179 // 갈수있는지조사는 bfs visit 비교

4179번: 불! (acmicpc.net) 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net *팁 bfs는 main안에서 짜는게 낫다. ret는 전역변수로? * 아이디어 1. 불bfs => 불 도착시간들 모두 저장 2. 사람bfs : 종료조건 -> 그때v값이 답임. ---------------------------------- 불보다 visit이 작다 -> 더빨리도착가능 -> 이동가능. == visit(불) >= 사람 -> continue; *예외처리 불이없는경우? visit(불) : 0 0 0..

백준 15686 // 조합함수암기!

15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net *로직 1. 완탐? 13C6 * 50 * 13 ok 2.for(13Cm) for (home) for(치킨) min갱신,ret갱신 * 조합핵심코드 /* * * 조합함수 암기 * * 결과 : idx 조합결과 * chichenList[0] -> [0,1] * chichenList[1] -> [0,2] * chichenList[2] -> [1,2] */ void combi(int start, vect..

백준 1325 // 자식수찾기는 int dfs(ret=1, ret+=dfs)

https://www.acmicpc.net/problem/1325 > n>>m ; for (int i = 0; i > a>>b; adj[b].push_back(a); } //디버깅 /*for (int i = 1; i

백준 17298 // 짝짓기는 stack(push[idx]) / 막대그림을그려라

17298번: 오큰수 (acmicpc.net) 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net * 행동영역 : 짝짓기는 stack stack에 인덱스를 저장하라. a[i] => 입력저장 while(top> n ; for (int i = 0; i > a[i]; while (s.size() && a[s.top()] < a[i]) //if가 아니라 while써야함 { ret[s.top()] = a[i]; s.pop(); } s.push(i); //idx를 스택에 push하라. } for (int ..

백준 1068 // 2차원벡터선언법 / 트리문제는 root 1개만 남는상황 예외처리하라 / 리프노드 카운팅은 int dfs

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net * 2차원벡터선언법 vector adj[54]; * 극단적예외처리 0-1 트리에서, 1이 삭제되는경우 //정답 : 1이 나와야함(root가 리프노드) 모든인접노드에대해, 인접노드가 삭제예정이 아닐때만 자식으로인정. if(i!=del) child++; #include using namespace std; typedef long long int ll; int root, n, t, del, v[5..