Algorithm

백준 2470 두용액 c++ // 투포인터는 st,en중 누구를 움직일지 결정하라

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. 의사코드 1.1 st,en중 누구를 움직일지 결정하라 if (sum1 커져야함->음수를 줄임 -> st++ else e--; //합이양수 -> 작아져야함 -> 양수를 줄임 -> e++ 1.2 변수 테이블을 정의하라 //ret : 현재까지 값중 0에 가장가까운 합 2. 전체코드 #include using namespace st..

백준 2748 피보나치수2 c++ // 탑다운 dp 형식

https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net #include using namespace std; long long dp[91], n; long long fibo(long long idx) { //기저사례 if (idx == 0 || idx == 1) return idx; //메모 long long& ret = dp[idx]; if (ret) return ret; //값이 있으면 바로리턴 //로직 retu..

백준 2225 합분해 c++ // dp 규칙찾는 방법

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. dp 규칙찾는 방법 1.1 표를그린다 1.2 규칙을세우고(뒤에만 숫자추가하기) 경우의수를 센다. 1.3. 그 숫자가 어디서 왔는지 규칙을 찾고 화살표로 표시한다 1.4. 규칙을 찾았으면 dp 테이블로 옮기고 숫자의 이동을 표시한다. 1.5. 점화식을 세운다(dp[j]=dp[j]+dp[j-1]) 2. 전체코드 #include using namespace std; int n, k; int dp[204]; int divd = 1000000000; int main() { ios_base::sync_with_stdio(0); ..

백준 2294 동전2 c++ // dp 동전논리 정리, 규칙성발견 dp테이블 형식

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 0. 규칙성발견 dp 테이블 형식 dp : target 후보들.. ex) dp : 0 1 2 3 4 5 ... 15 (target) 1 5 7(동전들) dp[i][j] : i원 추가시 j원을 만드는 최소 동전갯수 i원들을 추가해나가면서 table을 완성시킨다 => 규칙성발견 1. 동전논리 정리 (j-coin)의 이유 5원일때) dp[12]=d[7]+1 dp[7]의 ..

백준 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 ..