백준

[백준] 1629 곱셈 (JAVA)

✉️문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 📝 접근 for문을 이용한 방법 가장 간단한 방법이 for문을 이용하여 a를 b번 곱해주는 것이다. for(int i = 0; i < b; i++) a *= b; 하지만, 이 방법은 b가 50,000,000이 넘어가면 시간초과가 되어 버린다. (시간 제한 : 0.5). 따라서, O(N)보다 빠른 알고리즘을 고려할 필요가 있다. 분할 정복(Binary Search) 분할 정복은 숫자의 1/2를 반복해서 구하는 것이다. 10^8을 분할 정복으로 구해보자. ..

[Baekjoon] 12865 평범한 배낭 문제

https://www.acmicpc.net/problem/12865 배낭 문제는 냅색 알고리즘의 대표 문제라고 할 수 있다. 냅색 알고리즘은 다이나믹 프로그래밍에 속하는 알고리즘이다. 문제의 입력 예제를 통해 냅색 알고리즘에 대해 알아보자. 1. 먼저 넣을 수 있는 무게 크기만큼 1차원 배열을 하나 준비하자. (dy라고 하겠다) 2. 첫 번째 경우(4kg, 8원) 4kg의 가방에 8원의 가치를 가진 물건을 하나 넣을 수 있다. 5 - 7까지 모두 동일하다. 3. 두 번째 경우(5kg, 6원) 5kg의 가방에 6원의 가치를 가진 물건을 넣을 수는 있지만 이전 값인 8이 더 크므로 4kg, 8원짜리 물건을 넣는다. 4. 세 번째 경우(3kg, 2원) -> 3kg의 가방에 2원짜리 물건을 넣을 수 있다. ->..