일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 누적합
- 문자열
- 분할정복
- acm
- 이분탐색
- 알고스팟
- 세그먼트트리
- 그리디
- union-find
- Algospot
- 동적계획법
- BFS
- DFS
- stack
- 백준
- priority_queue
- 종만북
- backtracking
- 백트래킹
- 너비우선탐색
- 완전탐색
- 유니온파인드
- 다이나믹프로그래밍
- 스택
- DP
- Greedy
- 알고리즘문제해결전략
- BOJ
- 재귀
- 분리집합
- Today
- Total
목록전체 글 (105)
DAMPER's blog
www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 처음에 이 문제를 접했을 때에는 문제이름이 이중 우선순위 큐여서 우선순위가 다른 priority_queue를 2개 선언해서 두개로 돌렸는데 다시 생각해보니 말도 안되는 방법이었다... 그래서 map을 사용해서 value 값을 counting 용도로 쓰면서 naive하게 진행. 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..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/wLIeH/btqSxC8l7W1/39qos3cbDjKEPrK3OKHL4K/img.png)
algospot.com/judge/problem/read/FENCE algospot.com :: FENCE 울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체 algospot.com 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, ..
알고리즘 문제해결전략 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..