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일 때는 먼저있던 원소가 스택으로 전달 되고 스택은 연산을 하지 않는다 생각하면 ..

접근법 최적이 행렬 곱셈 알고리즘을 사용하여 푼다. https://ggjjdiary.tistory.com/132 [알고리즘] 연쇄 행렬 곱셈 알고리즘(Chained Matrix Multiplication) 연쇄 행렬 곱셈 알고리즘(Chained Matrix Multiplication) 연쇄 행렬(ex, 2 by 4 행렬 x 4 by 7 행렬 x 7 by 9 행렬 x ...)의 곱셈을 할 때 곱셈 연산을 최소로 하는 곱셈 순서를 찾는 알고리즘이다. 행렬 곱셈은 결 ggjjdiary.tistory.com 풀이 시간 복잡도 : 200 * 200 .. 200 의 형식으로 결합순서까지 생각하며 풀면 시간초과가 발생한다. 일단 다음과 같이 5개의 행렬이 있다고 생각해보자. 1) 그림에서 제시하고 있는 순서 외에도 ..

접근법 예제 1번을 보면 (1, 9) 보단 (2, 8)이 크다. 쭉 진행하다 보면 (3, 6) 보단 (4, 4)가 크다. 야근 지수 문제처럼 균등하게 분포 될 때 곱의 최대가 된다는 것을 알 수 있다! 풀이 s / n을 한 값을 정답에 담고, s % n 즉 나머지를 마지막 인덱스부터 추가한다. sort를 사용하는 것보단 위의 방식이 시간 복잡도를 줄여준다. 코드 #include #include using namespace std; vector solution(int n, int s) { if(n > s == 1) return vector(1, -1); int div = s / n; int ex = s % n; vector answer = vector(n, div); int i = answer.size()..

접근법 최단 거리를 구하는 문제이므로 다익스트라를 사용하면 된다. 풀이 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, ..