일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 이분탐색
- 스택
- priority_queue
- backtracking
- 유니온파인드
- 그리디
- 알고리즘문제해결전략
- 분할정복
- stack
- 알고스팟
- 재귀
- 완전탐색
- BFS
- acm
- 종만북
- 동적계획법
- 세그먼트트리
- 분리집합
- 너비우선탐색
- Greedy
- Algospot
- 문자열
- DP
- DFS
- 백준
- union-find
- 백트래킹
- BOJ
- 누적합
- 다이나믹프로그래밍
- Today
- Total
목록Problem Solving (85)
DAMPER's 낙서장
알고리즘 문제해결전략 183p에 소개된 카라추바 곰셈 알고리즘입니다. 2N자리수인 a와 b를 다음과 같이 정의한다고 하자. $$a = a_{1} \times 10^{N}+a_{0}$$ $$ b = b_{1} \times 10^{N}+b_{0}$$ a x b 는 다음과 같이 표현할 수 있다. $$a \times b \\ = ( a_{1}\times 10^{N} +a_{0}) \times (b_{1} \times 10^{N} + b_{0}) \\ = a_{1} \times b_{1} \times 10^{2N} + (a_{1} \times b_{0} + a_{0} \times b_{1})\times10^{N}+a_{0}\times b_{0}$$ 그렇다면 계산을 위해 다음과 같이 곱셈을 기준으로 4가지 조각으로..
www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 가장 처음과 마지막은 숫자이고, 두 개 이상의 연산자는 나타나지 않는다. 그럼 숫자가 N개라면 연산자는 N-1개이다. 숫자는 vector에, 연산자는 queue에 저장하고 숫자를 한칸씩 가면서 계산한다. 최솟값을 만들기 위해 '-'연산자 뒤에 나오는 '+'연산자에 해당하는 숫자들을 모두 더하여 한번에 뺀다. 경우의 수는 다음과 같다. - queue에서 '-'가 나온 경우, 빼기 위해 저장되어있는 값을 결과..
www.acmicpc.net/problem/11687 11687번: 팩토리얼 0의 개수 첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다. www.acmicpc.net N!에서 가장 끝 0의 개수를 세려면 2 * 5의 수를 세면 된다. N!을 소인수분해 했을 때, 2의 개수와 5의 개수를 생각한다면 min(2의 개수, 5의 개수) 가 M인 N! 중 N의 최소값을 찾으면 된다. 2의 개수는 N이 짝수일 때마다 1개 이상 생기고, 5의 개수는 N이 5의 배수일 때마다 1개 이상 생기므로 2의 개수는 항상 5의 개수보다 크거나 같다. 그러므로 5의 개수만 신경쓰자. 그러면 N!에서 5의 개수는 몇개일까? 5의 배수의 개수 + 25의 배수의 개수 + 125의 배수의 개수 + 625의 배수의 개수...
www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net N/2 명씩 두팀을 만들기 위해 check vector로 true면 A팀, false면 B팀으로 정합니다. 팀을 이룰 때는 순서에 상관없이 선택합니다. 재귀적으로 팀을 선택한 뒤, 정지조건(N/2명을 골랐을 때)을 만족하면, 팀의 점수를 계산합니다. 점수 계산은 이중 for문으로 완전탐색합니다. 점수차의 최솟값을 계산하여 출력합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..
algospot.com/judge/problem/read/TRIPATHCNT algospot.com :: TRIPATHCNT 삼각형 위의 최대 경로 수 세기 문제 정보 문제 9 5 7 1 3 2 3 5 5 6 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 algospot.com 9 5 7 1 3 2 3 5 5 6 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 숫자의 합이 가장 큰 경로는 하나가 아니라 ..
algospot.com/judge/problem/read/TILING2 algospot.com :: TILING2 타일링 문제 정보 문제 2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있 algospot.com 2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다. 경우의 수는 n이 커지면 아주 커질 수 있으므로, 1000000007으로 나눈 값을 대신 출력하세요. 입력의 첫 줄에는 테스트 케이스의 수(C >n; vector v(n+1, 0); v[1] =..