본문 바로가기

백준198

[백준] 2579번 - 계단 오르기(C++/파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 계단 오르기 -> www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net Python 코드는 바텀업(Bottom-Up), C++코드는 탑다운(Top-Down)으로 구현했다. C++ 소스 코드) Python 소스 코드) 2021. 4. 9.
[백준] 1629번 - 곱셈 (C++) 문제 및 풀이 문제) 백준 - 분항정복을 이용한 거듭제곱 - 곱셈 -> www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 중간에 c로 나누어서 수를 작게 만드는게 핵심인 문제. 계산해야할 지수가 홀수,짝수로 나누어 지수법칙 적용. C++ 소스 코드) 2021. 4. 9.
[백준] 2217번 - 로프 (파이썬/C++) 문제 및 풀이 문제) 백준 - 그리디 알고리즘 (Greedy) - 로프 -> www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 그리디(Greedy) 같으면서도 완전 탐색(Brute Force) 같던 문제. 어렵지 않게 풀 수 있다! C++ 소스코드) 파이썬 소스코드) 2021. 4. 5.
[백준] 11726번 - 2xn 타일링 (파이썬/C++) 문제 및 풀이 문제) 백준 - 동적 계획법(Dynamic Programming) - 2xn 타일링 -> www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 점화식을 다음과 같이 작성할 수 있다. f(n) = f(n - 1) + f(n - 2) 파이썬 소스 코드는 위 점화식을 이용해서 작성했고, C++에서는 기저 사례(n = 1, n =2)의 설정과 재귀를 통해 답을 계산한다. 파이썬 소스코드) C++ 소스코드) 2021. 3. 30.
[백준] 1005번 - ACM Craft (파이썬) 문제 및 풀이 문제) 백준 - 위상 정렬 (Topology Sort) - ACM Craft -> www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 건물 간의 건설 순서 규칙이 주어졌을 때, 건물 W를 건설 완료를 위해 드는 최소 시간을 출력한다. 규칙(선후관계)이 존재하므로 위상정렬을 이용하여 문제를 해결한다. 진입 차수가 0인 것을 제거해가며 건물 W가 나오면 즉시 시간을 출력한다. Topology Sort ->2021.03.10 - [Algorithm_note/Al.. 2021. 3. 30.
[백준] 9251번 - LCS (파이썬) 문제) 백준 - 동적 계획법 (Dynamic Programming) - LCS -> www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net dp를 해당 문자 이전까지 만들 수 있는 LCS라 하자. dp를 업데이트 해가며 만약 문자열이 같을 경우(string1[i] == strring2[j]), 이전 LCS의 길이(dp[i - 1][j - 1])에 1을 더해준다. 문자가 같지 않을 경우, 이전에 만든 LCS중 최대값을 그대.. 2021. 3. 29.
[백준] 15917번 - 노솔브 방지문제야!! (C++) 문제 및 풀이 문제) 백준 - 수학(Mathematics) - 노솔브 방지문제야!! www.acmicpc.net/problem/15917 15917번: 노솔브 방지문제야!! 어떤 수 a가 2의 거듭제곱꼴로 나타내어진다고 해 봅시다. 그렇다면, a = 2n (단 n ≥ 0인 정수) 를 만족할 겁니다. 보통, 각 비트별로 검사를 하면서, 켜져 있는 비트의 개수를 알아내는 것도 좋은 www.acmicpc.net 완전 탐색을 이용한 풀이) #include #include using namespace std; int q; bool isTwo(int n) { for (int i = 0; i < 31; ++i) { if (pow(2, i) == n) return true; } return false; } int main() { i.. 2021. 3. 25.
[백준] 2798번 - 블랙잭 (C++/파이썬) 문제 및 풀이 문제) 백준 - 브루트 포스(Brute Force) - 블랙잭 -> www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 카드를 세 장 뽑으므로, 삼중 반복문을 이용하여 카드 세 장을 선택하며 그 카드들의 합을 계산하여 확인한다. c++ 소스코드) #include #include #include using namespace std; int n, m, sum = 0; vector card; int main() { //빠른 입출력 io.. 2021. 3. 18.
[백준] 2231번 - 분해합 (C++/파이썬) 문제 및 풀이 문제) 백준 - 브루트 포스(Brute Force) - 분해합 -> www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 1부터 n까지 완전 탐색을 수행한다. 만약 생성자를 찾을 경우, 그 즉시 반복문을 탈출한다. C++ 소스 코드) #include using namespace std; int n, ans = 0; //생성자 함수 int constructor(int a) { int res = a; while (a > 0) { res +.. 2021. 3. 18.
반응형

티스토리툴바