목록알고리즘 문제 풀이/BOJ (77)

영벨롭 개발 일지

[백준 BOJ][C++]11052번 카드 구매하기: DP

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. dp[n] 은 카드 n장을 만들기 위해 필요한 금액의 최댓값을 나타냅니다. 카드 i개가 포함된 팩의 가격 P[i]와 dp에 저장되어 있는 수들을 조합하여 해결할 수 있습니다. 그렇다면 dp[1]은 카드 1장을 만들기 위한 금액의 최댓값이므로 자동으로 P[1]이 되는 것이지요. 다음으로 dp[2]의 값은 어떻게 될까요? ..
알고리즘 문제 풀이/BOJ 2022. 2. 25. 14:00
[백준 BOJ][C++]11047번 동전 0 풀이: 그리디 알고리즘

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 입력으로 주어지는 동전의 가치 Ai가 오름차순으로 주어졌음으로 제일 가치가 큰 동전부터 비교해가며 풀이를 진행하면 됩니다. 가치 k를 만들기 위해 필요한 동전의 수가 최소가 되기 위해선, 먼저 k보단 작은 수들 중에서 가장 큰 수를 뽑아 k를 나눈 몫이 그 동전의 개수를 의미합니다. 그 나머지는 남은 가치의 합을 나타내고 위 과정을 ..
알고리즘 문제 풀이/BOJ 2022. 2. 24. 21:51
[백준 BOJ][C++]11399번 ATM 풀이: 그리디 알고리즘

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 각 사람이 돈을 인출하는데 필요한 시간의 합이 최소가 되려면 시간이 적게 걸리는 사람일수록 앞에 서야합니다. 입력으로 들어온 시간 Pi를 오름차순으로 정렬한 뒤, 각 시간을 점차 더해주면 됩니다. 시간 Pi의 자료구조로 배열을 사용해도 되지만, 정렬하기 귀찮으니 저는 우선순위큐를 사용했습니다. C++ 컨테이너인 priority_queue를 사용하여 push와 동시에 오름차순으로 정렬되게 하였습니다. #include #inclu..
알고리즘 문제 풀이/BOJ 2022. 2. 24. 21:28
[백준 BOJ][C++]9095번 1, 2, 3 더하기 풀이: DP

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이 문제는 Dynamic Programming 을 이용하여 해결할 수 있습니다. 숫자 N 모든 경우 경우의 수 dp[N] 1 =1 1 2 =1+1 =2 2 3 =1+1+1 =1+2 =2+1 =3 4 4 =1+3 (3=1+1+1 =1+2 =2+1 =3) =2+2 (2=1+1 =2) =3+1 (1=1) 7 =dp[1]+dp[2]+dp[3] 5 =1+4 (4=1+1+1+1 =1+1+2 =1+2+1 =2+1+1 =2+2 =1+3 =3+1) =2+3 (3=1+1+1 =1+2 =2+1 =3) =3+2 (2..
알고리즘 문제 풀이/BOJ 2022. 2. 24. 16:28
[백준 BOJ][C++]1463번 1로 만들기: DP

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 Dynamic Programming, DP로 해결할 수 있습니다. DP를 사용하지 않으면 중복 계산이 계속 발생하기 때문에 DP를 이용한 메모이제이션이 필요합니다. DP의 원리인 메모이제이션은 처음 실행되는 연산은 기록해두고 이미 진행된 연산이라면 그 값을 가져오는 방식입니다. 연산 과정 연산 횟수 (화살표 개수) 2->1 1 3->1 1 4->2->1 또는 4->3->1 2 5->4->2->1 또는 5->4->3->1 3 6->3->1 또는 6->2->1 2 7->6->3->1 또는 7->6->2-..
알고리즘 문제 풀이/BOJ 2022. 2. 24. 12:00
[백준 BOJ][C++]2004번: 조합 0의 개수 풀이

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 문제 풀이에 앞서 1676번 풀이 글을 보고 오시면 도움이 됩니다. n, m에 대한 조합 공식은 n!/(m!(n-m)!) 입니다. 1676번 팩토리얼 0의 개수를 구할 때에는 5의 개수를 알면 0의 개수를 알 수 있었습니다. 하지만 조합 0의 개수를 구할 때에는 5의 개수 뿐만 아니라 2의 개수도 고려해야 합니다. 만약 n이 6, m이 2일 때를 봅시다. 6!의 5의 개수는 1개이고 2!과 3!의 5의 개수는 0개입니다. 5의 개수만 고려한다면 조합 0의 ..
알고리즘 문제 풀이/BOJ 2022. 2. 22. 13:33
이전 Prev 1 ··· 9 10 11 12 13 Next 다음