본문 바로가기
반응형

알고리즘27

[cpp 알고리즘] 백준 1744 수 묶기 [백준] 1744 수 묶기 풀이 그리디 알고리즘, 정렬, 많은 조건 분기 문제 출처: https://www.acmicpc.net/problem/1744 문제 요약 - 길이가 N인 수열이 주어졌을 때, 두 수를 곱하거나 그대로 둘 수 있다. 이 수들을 모두 더한 값들 중 최댓값을 구하면 된다. 풀이 정리 1. 일단 오름차순으로 정렬한다. 2. 숫자 1을 기준으로 3가지 경우로 나뉘어진다. (1) 1보다 작은, 0이거나 음수인 경우 -> 앞쪽(작은 수)부터 두 수를 곱해서 최종 결과 값에 더하면 된다. (2) 1인 경우 -> 곱하는 데 사용하지 않고, 더하면 된다. (3) 1보다 큰 양수인 경우 -> 뒤쪽(큰 수)부터 두 수를 곱해서 최종 결과 값에 더하면 된다. 3. (1)의 경우 혹은 (3)의 경우가 홀.. 2023. 11. 11.
[cpp 알고리즘] 백준 1629 곱셈 [백준] 1629 곱셈 cpp 풀이 수학, 분할 정복을 이용한 거듭제곱 https://www.acmicpc.net/problem/1629 문제 요약 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어졌을 때, A를 B번 곱한 수를 C로 나눈 나머지를 출력하면 된다. 풀이 정리 - 분할 정복을 활용하여 지수를 나누어 주면 된다. (1) 지수가 0인 경우 -> X^0 = 1 이므로 1을 리턴해준다. (2) 지수가 짝수인 경우 -> X를 X/2로 나누어서, 계산한 두 값을 곱해준다. (3) 지수가 홀수인 경우 -> X를 X/2로 나누고, 계산한 두 값과 밑을 한 번 더 곱해준다. - 예제에 나왔던 A=10, B=11로 예를 들어 보면, 1. 가장 나이브하게 먼저 생각나는 방법은 for문을 이용하여 .. 2023. 11. 10.
[cpp 알고리즘] 백준 1780 종이의 개수 [백준] 1780 종이의 개수 cpp 풀이분할정복, 재귀https://www.acmicpc.net/problem/1780 문제 요약N(1 ≤ N ≤ 37, N은 3k 꼴) * N 크기의 행렬로 표현되는 종이에서, 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. - 만약 종이가 모두 같은 수라면, 그대로 사용한다. - 아니라면, 종이를 같은 크기의 종이 9개로 자르고, 각각의 종이에 대해서 위의 과정을 반복한다. 출력값으로, 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구하면 된다. 풀이 정리이전에 진행한 분할정복 문제와 같다. 즉 구간을 나눠가면서, (1) N=1인지 확인하기, (2) 그 부분이 모두 같은 값으로 이루어져있는지 확인하기.. 2023. 11. 9.
[cpp 알고리즘] 백준 1992 쿼드트리 [백준] 1992 쿼드트리 풀이 분할정복, 재귀 문제 출처: https://www.acmicpc.net/problem/1992 문제 요약 - 모두 0으로만 되어 있으면 압축 결과는 "0" - 모두 1로만 되어 있으면 압축 결과는 "1" - 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지 않고, "왼쪽 위/ 오른쪽 위/ 왼쪽 아래/ 오른쪽 아래" 4개로 나누어 압축하고, 이 4개의 영역을 압축한 결과를 괄호 안에 묶어서 표현 예시 문제의 경우: (0(0011)(0(0111)01)1) 로 표현된다. 풀이 정리 1. 모두 0인지 확인, 모두 1인지 확인, 그렇지 않다면 분할정복 2. 분할정복 할 때 n=1인 경우는 먼저 종료시키고 아니면 1의 과정을 반복한다. c++ 코드 #include #include.. 2023. 11. 8.
반응형

티스토리툴바