알고리즘 문제풀이/백준134 [백준 1629] 곱셈 www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 모듈러 연산과 제곱 빠르게 하기 응용버전이다. 제곱빠르게 하기는 재귀로도 풀 수 있기 때문에 이전에 풀었던 관련 문제를 참고한다. 이전 포스팅 참고 eazymean.tistory.com/192?category=883575 리트코드에서 동일한 문제를 푼 경험이 있다. 모듈러 연산에 대해서 짚고 넘어가자면 (a*b) mod n = ((a mod n) * (b mod n)) mod n이다. 문제에서 주어진 a,b,c의 범위가 상당히 크므로 long long으로 선언해도 오버플로우가.. 2020. 12. 13. [백준 1495] 기타리스트 www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net DP를 사용하는 문제이다. DP[I][J]를 가능한 최댓값으로 접근하면 문제를 풀 수 없다. 경우의 수가 많기 때문 따라서 DP[I][J]는 I번째 노래에서 J의 볼륨이 가능한지 여부여야 한다. DP[0][S] = 1로 초기화 된다. 그 다음에 입력을 받으면서 이전 노래에서 J 볼륨이 가능했다면 J +- IDX가 가능한지 확인하여 DP 배열에 체크한다. 마지막 노래에 볼륨 .. 2020. 12. 13. [백준 1074] Z www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 재귀함수를 사용하는 문제이다. 재귀함수는 아무리 풀어도 익숙해지지가 않는듯하다 사실 이 문제는 재귀함수를 따로 정의하기 보다 while문 돌리는게 편했다. 1. 재귀함수 사용 기저 조건은 한 변의 길이가 2인 정사각형일때이다. cnt의 초기값을 0으로 설정하여 기저 조건에 도달할 때마다 4씩 더해준다. 재귀함수 내 재귀함수 호출은 z모양으로 발생한다. #include using namespace std;.. 2020. 12. 13. [백준 1992] 쿼드트리 www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 재귀문제이다. 이전 문제와 약간의 차이가 있다면 (를 추가로 붙이는 거 정도 이전과 동일하게 압축할 정사각형의 길이, 정사각형 시작점을 인자로 받는다. 헷갈렸던 점은 (를 어디에 붙여야 하나...했던 점이다. (,)는 압축한 횟수 만큼 추가되므로 4개로 나눠서 압축을 시작하는 전후에 붙여주면 된다. #include using namespace std; char arr[65][65]; int n; b.. 2020. 12. 13. 이전 1 ··· 20 21 22 23 24 25 26 ··· 34 다음
