목록분할정복 (6)

1일1알

백준 17829번 222-풀링 C++

https://www.acmicpc.net/problem/17829 17829번: 222-풀링 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 22 www.acmicpc.net 재귀 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n; ve..
알고리즘 2023. 5. 5. 12:46
백준 10830번 행렬 제곱 C++

a^b에서 b가 홀수라면 b를 1 빼주고 결과(처음에는 단위행렬)에 a를 곱해주고 b가 짝수라면 a^b = (a^2)^(b/2) 이기 때문에 a를 제곱해주고 b를 2로 나눠주었다. 2^7를 예로 들자면 우선 처음에 결과는 1로 시작한다. (res = 1) 2^7 에서 7이 홀수이기 때문에 2^6 으로 바꾸고 res에 2를 곱한다 (res = 2) 2^6 에서 6이 짝수이기 때문에 4^3으로 바꿔준다. 4^3에서 3이 홀수이기 때문에 4^2로 바꿔주고 res에 4를 곱한다(res = 8) 4^2에서 2가 짝수이기 때문에 16^1로 바꿔준다. 16^1에서 1이 홀수이기 때문에 16^0으로 바꿔주고 res에 16을 곱한다(res = 128) b가 0이 됐기 때문에 그만 계산한다. 2^7 = res = 128이..
알고리즘 2022. 6. 29. 11:08
백준 2263번 트리의 순회 C++

포스트오더는 루트를 마지막에 순회하는것을 이용해서 인오더에서 루트값을 찾아서 작은 트리로 분할해가면서 루트를 출력하는 방식으로 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n; vector inOrderIndex; vector postOrder; void PrintRoot(int inOrderStart, int inOrderEnd, int postOrderStart, int postOrderEnd)..
알고리즘 2022. 6. 22. 12:08
백준 1629번 곱셈 C++

분할 정복을 이용하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int64 solve(int64 a, int64 b, int64 c) { if (b == 1) return a % c; int64 tmp = solve(a, b / 2, c); if (b % 2 == 0) return tmp * tmp % c; return ((tmp * tmp) % c * a) % c; } int main() { ios_base..
알고리즘 2022. 6. 11. 13:28
백준 2374번 같은 수로 만들기 C++

가장 작은 수부터 인접한 수와 같게 만들어가면서 문제를 해결하였다. 답을 int로 하면 오버플로우가 나기 때문에 long long을 사용하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int n; vector v(1001); ll ans = 0; void Add(int index) { int val = v[index]; int start = index; int end = index; int MIN = 1000000001; while (true) ..
알고리즘 2022. 2. 9. 13:05
백준 5904번 Moo 게임 C++

moo 문자열을 간단하게 숫자로 나타내 보겠다. moo는 3, mooo는 4, mooooo는 5 이런 식으로 사용할 것이다. moo 수열은 3 -> 3 4 3 -> 3 4 3 5 3 4 3 이런 식으로 증가하게 된다. n을 입력받아서 n이 수열의 길이보다 크다면 수열의 길이를 규칙에 맞춰서 늘리고, n이 수열의 길이보다 작다면 n의 값을 재조정하고 수열의 길이를 축소해가면서 문제를 해결하였다. 처음에는 직접 수열을 구현해보았는데, 그런 식으로 문제를 풀면 메모리 초과가 난다. 따라서 규칙에 맞춰서 특정 위치의 문자를 구하는 식으로 문제를 해결해야 한다. #include #include #include #include #include #include #include #include #include #inc..
알고리즘 2021. 12. 7. 12:31
이전 Prev 1 Next 다음