분류 전체보기

백준 13549 숨바꼭질3 c++ // pq를 이용한 bfs 구현방법

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 1. 문제 그냥 bfs : 메모리초과? 가 났다. bfs는 비용이 모두 동일할때만 사용 가능하다. 해결 : 비용이 적은것부터 탐색하도록 pq에 담는다. 2. 전체코드 #include using namespace std; int n, k; int vis[100000 + 4]; int main() { ios_base::sync_with_stdio(0); cin.t..

백준 1717 집합의표현 c++ // 유니온 파인드 구현방법

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 1. 의사코드 *파인드 : 자기자신이 부모임 == 루트노드 아님 : 부모의 조상을 찾아서 리턴 *유니언 : 조상이다를때, 작은쪽으로 합침 rootA의 부모 = rootB // parent[rootA]=rootB ※ A의 부모 = rootB 가 아님에 주의! // parent[A]=rootB (X) #include using namespace std; int n..

백준 1107 리모컨 c++ // 완탐, 초기값 잘 설정하는법

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 1. 초기값 잘 설정하는법 ret=abs(100-n) 초기값을 100번에서 노가다하는 경우로 설정 => 이것보다 작은게 있을때만 정답이 갱신됨 2. 전체코드 #include using namespace std; int n,m,dead[10],ret1,ret2; //번호n을 누를수 잇는지 체크 int check(int n) { string s = to_string(n); for (..

백준 5430 AC c++ // 파싱, 덱 사용법

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 0. 덱 뒤쪽에서도 삽입,삭제 가능한 업그레이드 벡터라고 생각하면 된다. 양쪽끝에서 삽입,삭제하는 문제일때 사용하면 된다. 1. 시행착오 끝에서 2번째줄이 없는경우 : 정답이 빈칸인경우 "["이 팝되서 "]" 만출력된다. 예외처리조건추가후 []이 출력됨. string ret = "["; while (d.size()) { if (!rev) { ret += to_string(d.front()); ret += ","; d.pop_front(); } else ..

백준 2293 동전1 c++ // dp, 경우의수는 덧셈이다!

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 의사코드 여기에서 2회차 dp[4]를 보면 1111 112 22 의 경우의 수가 있는데, 1111은 1회차의 dp[4]의 경우의수이고 (1) 11, 2 는 2회차 dp[2]의 경우의수이다. (2) 답은 1+2 = 3 따라서 dp[4]=dp[4](이전회차 경우의수) + dp[4-2(coin)] (현재회차까지 동전으 직전코인 경우의수) 이라는 식이 도출된다. 2. 경우의수는 덧셈이다. dp[4]를..

백준 1504 특정한최단경로 c++ // 다익스트라 필수경유정점 해결, INF설정방법

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1. INF설정방법 -문제 : INF(987654321) *3 > max_int(21억) -> 오버플로우 -> 오답 최악의경우 : 1 ,2, 3, 4, ... 800개의 정점 비용이모두 최대인경우(1000) == 800*1000 ? 그냥 맘편하게 max_int /3(함수호출 최대횟수)으로 설정하는게 편했다.. 2.의사코드 1~v1~v2~n 1~v2~v1..

백준 1238 파티 c++ // 다익스트라 여러정점 돌리기

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. 시간복잡도 다익스트라 : EleE * N(학생마다 다익스트라) * 2(끝~시작지점도 반복) 10000 lg10000 * 1000 *2 가능 2.전체코드 st와 en을 수정하면서 학생마다 다익을 돌린다. #include using namespace std; typedef long long ll; int n, m, x, st, en,ret; vector adj[10..

백준 11779 최소비용구하기2 c++ // 다익스트라 경로복원 방법

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 1. 다익스트라 경로복원 방법 1.1 pq에 push후 pre배열에 기록하면된다. ex) pre[5]=3 // 5이전에 3임 pre[next.second] = cur.second; //경로복원 : (이전정점을 기록만하면된다) //pre[next.정점]=cur.정점 1.2 출력시 경로를 v 에 push 1.3 reverse(begin,end) 후 출력 cout > m..