development korean paul development korean paul

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 DP[1] = 1 1 DP[2] = 2 00, 11 DP[3] = 3 001, 100, 111 DP[4] = 5 0011, 1001, 1100, 1111 DP[5] = 8 00000, 00001, 00100, 10000, 00111, 10011, 11001, 11100 5까지의 경우의 수를 구하고 규칙성을 찾았다. 피보나치 수열을 따른다는 것을 알았다. #include using namespace..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 이 문제는 이항정리 문제이다. 이항정리란 ? n개 중 r개를 순서와 상관없이 뽑는 조합을 말한다. 이항정리 특징을 사용해 문제를 풀면 아래와 같은 코드로 풀 수있다. #include #include using namespace std; vector dp; int func(int r, int c) { if(dp[r][c]) return dp[r][c]; dp[r][c] = func(r - 1, c)..

조합이란 ? N개의 숫자 중에서 순서에 상관없이 M개를 뽑는 것이라 이해했다. 예를들면 공동대표의 자리를 뽑는데, 대표의 자리는 공동 대표이므로 순서에 상관없는 경우이고 이를 조합으로 표현하면 nCm으로 표현가능하다. 백준에서는 메모제이션으로 이 문제를 풀었다. #include #include using namespace std; array memo; int combination(int n, int r) { if(memo[n][r]) return memo[n][r]; else { memo[n][r] = combination(n -1, r - 1) + combination(n - 1, r); return memo[n][r]; } } int main() { for(auto& x : memo) fill(x.b..

지문해석 첫번째 풍선을 터뜨리고 종이에 써져있는 수만큼 이동해서 다음 풍선을 터뜨린다. 이 때 써져있는 종이의 수가 양수이면 오른쪽 이동, 음수이면 왼쪽으로 이동한다. 단 ! 0 일 때 왼쪽으로 이동하면 N으로 이동해서 왼쪽으로 이동한다. N 일 때 오른쪽으로 이동하면 0으로 이동해서 오른쪽으로 이동한다. 풀이 예제 1번을 보자 첫번째 풍선을 터뜨린다. 종이에 써져있는 3만큼 오른쪽으로 이동한다. 구현 방법은 deque 가장 앞에 있는 원소를 가장 뒤로 붙이면 된다. 가장 앞에 있는 4번째 풍선을 제거한다. 종이에 써져있는 -3만큼 왼쪽으로 이동한다. 구현 방법은 deque 가장 뒤에 있는 원소를 가장 앞으로 붙이면 된다. 가장 뒤에 있는 5번째 풍선을 제거한다. 위와 같은 순서를 반복하면 아래와 같이 ..

지문 파악 0번 자료구조이면 원소를 큐에 push() 후 pop()한다. 1번 자료구조이면 원소를 스택에 push() 후 pop()한다. 큐인지 스택인지 말하는 배열이 N개만큼 주어진다. 즉 큐 또는 스택을 원소로하는 배열이 N개 만큼 있다고 생각하면 된다. N- 1번째 원소를 N -1번 자료구조(큐 또는 스택)에 push() 후 pop() 한다. 이 때 스택의 특성에 대해 살펴보자, push를() 후 pop()을 하면 넣은 원소를 다시 뺴내게 된다. 예제 입력 2를 보자. 아래와 같이 넣은 원소는 그대로 나오게 되어있다. 즉 스택은 연산에서 제외해도 된다는 것이다! 1번 예제를 살펴보자. 2를 넣었으면 자료구조가 Queue일 때는 먼저있던 원소가 스택으로 전달 되고 스택은 연산을 하지 않는다 생각하면 ..

접근법 최단 거리를 구하는 문제이므로 다익스트라를 사용하면 된다. 풀이 1. 시간 복잡도 : 정점의 개수가 최대 1000개, 간선의 개수가 최대 10000개 이므로 O([V][E]) = 10'000'000이 되어 시간 내에 풀 수있다. 2. 모든 정점이 X로가는 최소시간을 구한다. 3. X에서 모든 정점으로 가는 최소시간을 구한다. #include #include #include #include using namespace std; const int INF = 1e9+7; #define PP pair vector road[1001]; vector dist; int sum[1001]; int N, M, X; void dijkstra(int s) { dist.clear(); dist.resize(1001, ..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 접근법 1. 가장 작은 용량의 가방에 들어 갈 수 있는 보석을 찾기 위해 오름차순 정리를 한다. (보석과 가방 모두)2. 그 중 가장 비싼 보석을 찾기 위해 우선순위 큐를 사용한다.3. 가장 작은 용량의 가방에 들어간 보석은 더 큰 가방에도 들어 갈 수 있으므로 그리디 탐색을 사용한다. 풀이 1. 가방과 보석을 오름차순으로 정리한다.2...

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 큐를 사용한다. pop()과 push()를 반복함으로써 k - 1 만큼 회전시키고 k번째 정수를 pop() 한다. #include "pch.h" int main() { queue queue; int n = 0, k = 0; cin >> n >> k; for (int i = 0; i < n; ++i) { queue.push(i + 1); } int value = 0; cout 1) { for (int i = 1; i < k; ++i) { value = queue.front(); queue...