반응형 분류 전체보기584 [Python]백준 #2824 최대공약수(큰수자료구조) 사실 이 문제는 복잡하게 문제를 풀어야 하지만,큰수(big integer)가 지원된다면, 유클리드 알고리즘으로 간단하게 구할 수 있습니다.보통은 제가 C/C++을 이용해서 풀이를 해오고 있지만, 큰수 자료구조를 사용하기 위해서 파이썬을 이용해보았습니다. https://www.acmicpc.net/problem/2824 만약 큰수 자료구조를 지원하지 않는다면, 가장 큰 수의 제곱근을 기준으로 해서 그 이하의 소수들에 대하여 공약수를 구하는 방식을 사용해야 합니다. 큰수 자료구조끼리의 연산이 시간이 오래 걸리지만, 이 문제에 있어서는 큰수 자료구조를 사용한다고 해서 문제가 될만큼은 아닙니다. """ baekjoon #2824 - by Aubrey Choi - created .. 2024. 8. 18. [Python] 백준 #2812 크게 만들기(탐욕 알고리즘) 이번 문제는 n개의 자리를 가진 숫자에서 k개의 자리수를 제거하여 n-k개의 자리를 가진 수 중에 가장 큰 수를 만드는 것입니다. 문제의 링크는 다음과 같습니다.https://www.acmicpc.net/problem/2812 저는 스택(stack)을 이용한 탐욕 알고리즘을 이용해서 문제를 풀었습니다. 알고리즘은 간단합니다. 다음수가 맨 마지막수보다 크고 빼어야할 수가 있다면, 맨 마지막수를 빼고 다음수를 추가하는 방식입니다. 입력 받기n, k = map(int, input().split())- 이 부분은 `n`과 `k`를 입력받습니다. `n`은 문자열 `s`의 길이, `k`는 제거할 문자 개수를 의미합니다.스택 초기화stack = ["9"]- 가장 큰 수를 만들기 위해 사용할 스택을 초기화합니다... 2024. 8. 17. [C/C++] 백준 #2805 나무 자르기(이분 탐색) 이분 탐색은 단순증가하는 형태의 함수에서 원하는 값을 빠르게 찾는데 사용을 합니다. 시간 복잡도는 \(O( \log N )\)이 됩니다. 하지만, 어떤 지점을 기준으로 실패와 성공이 갈릴 때, 그 기준점을 찾을 때에도 유용합니다. 나무 자르기 문제 역시 이분 탐색을 이용하여 성공할 때 최적값을 찾을 수 있습니다. 문제의 링크는 다음과 같습니다.https://www.acmicpc.net/problem/2805 코드 설명1. `readint()` 함수int readint() { int s=0,c; for(;;){ c=getchar(); if(c'9') break; s=s*10+c-'0'; } return s;}- 이 함수는 표준 입력으로부터 정.. 2024. 8. 16. [C/C++] 백준 #2749 피보나치 수 3(분할정복) 피보나치 수에 대한 알고리즘은 점화식에서 출발해서 재귀함수(recursion)를 배울 때 자주 인용되는 것이죠. 재귀함수를 사용하는 방법이 매우 많은 중복이 발생한다는 문제를 거론하면서 동적계획법(Dynamic Programming)을 사용해야 하는 이유를 설명할 때에도 많이 쓰입니다. 재귀함수를 단순하게 이용하면, 시간 복잡도가 \(O(\phi^N)\)으로 기하급수로 늘어나지만, 이를 동적 계획법 또는 포워드 프로그래밍(Forward Programming)을 사용하면, 시간 복잡도가 \(O(N)\)으로 급격하게 줄어들 수 있습니다. 하지만 이번 문제는 N 자체가 \(O(N)\) 알고리즘으로 해결하기 어려운 문제입니다. 그래서 분할 정복을 사용해야 하고, 이를 이용하면 시간 복잡도를 \(O(\log.. 2024. 8. 12. [C/C++] 백준 #2718 타일 채우기(동적계획법) 경우의 수를 알아내라는 문제들 상당수는 동적계획법(Dynamic Programming)으로 해결할 수 있습니다.하지만 동적계획법을 사용하기 위해서는 문제를 올바르게 이해하는 것이 선행되어야 합니다. 2xn일 때에는 피보나치 수열과 비슷한 점화식을 얻을 수가 있습니다. 하지만 3xn, 4xn 과 같이 수가 늘어나면 조금 더 복잡한 점화식이 필요합니다. 일단 제가 모델링한 것은 조금 복잡합니다.이전값에 대해서 4개값까지 참고를 하니까요. 문제는 다음 링크와 같습니다.https://www.acmicpc.net/problem/2718 프로그램 설명: 1. 함수 solve(int n) • 이 함수는 주어진 n 크기의 바닥을 채우는 방법의 수를 계산하고 출력합니다. • 이 문제에서는 특이한 점이 있는데, 점화.. 2024. 8. 10. [C/C++] 백준 #2698 인접한 비트의 개수(동적 계획법) 동적 계획법(Dynamic Programming)으로 문제를 풀기 위해서는, 해당 문제에 대한 모델링을 해주어야 합니다. 모델링(modeling)을 할 때에는 N의 문제를 그보다 크기가 작은 N-1이나 N/2의 문제 등 보다 작은 형태로 나누어 주어야 하죠. 보통 N-1 문제로 표현할 수 있는 경우에는 시간 복잡도가 \(O(N)\)이 되며, N/2 문제로 표현할 수 있는 문제는 \(O(\log N)\) 또는 \(O(N \log N)\) 문제로 표현될 수 있습니다. 예를 들어서 피보나치 수열의 경우에는 N의 문제를 N-1 문제와 N-2 문제로 해결하며, 이 것을 그대로 적용하면 \(O(N)\)이 되며, 보다 적극적인 방법으로 이분 탐색을 진행한다면, \(O(\log N)\) 복잡도로 해결할 수 있습.. 2024. 8. 9. 이전 1 ··· 7 8 9 10 11 12 13 ··· 98 다음 728x90
