Programming18 [BF] 16937번 두 스티커 https://www.acmicpc.net/problem/16937 알고리즘 Brute Force Greedy (?) 풀이 포인트 주어진 n개의 스티커 중 두 개의 스티커만 사용하여 최대 넓이를 구한다는 점 스티커를 회전할 수 있고 스티커끼리 접할 수 있다는 점 Brute Force 전형적인 brute force 문제이다. n개의 스티커 중 2개를 골라서 스티커를 붙여보면서 최대 넓이를 가지는 스티커 조합을 찾으면 된다. 여기서 고민되는 부분이 스티커를 붙이는 것을 어떻게 구현하는지였다. 가장 먼저 생각난 점은, $h \times w$ 넓이에 한칸 한칸 for문을 돌면서 스티커를 붙여보는 것이었다. 그런데 이렇게 하면, 스티커를 붙일 수 있는 격자판과 스티커 최대 넓이가 100이므로 시간 복잡도가 꽤 커.. 2022. 1. 9. [BF] 16936번 나3곱2 https://www.acmicpc.net/problem/16936 알고리즘 Brute Force Back Tracking 풀이 포인트 가능한 모든 경우의 수를 탐색하되, 나3곱2의 조건이 충족되는 경우만 살펴본다 (백트래킹) Back Tracking 문제에서는 순서가 뒤죽박죽으로 된 수열 B가 주어진다. 우선 여기 있는 애들을 기반으로 수열 A가 만들어지므로, B에 있는 숫자들을 defaultdict 자료 구조를 가지는 exist에 기록한다. 이는 추후에 나3곱2에 해당하는 숫자가 있는지 탐색하는 시간을 줄여주기 위함이다. 이후에는 평소처럼 재귀를 이용해 Brtue Force을 해준다. 다만, 나3곱2에 해당하는 조건만 탐색하므로, 정확하게는 백트래킹이라 함이 맞을 것이다. 백트래킹 조건은 for문 안.. 2022. 1. 9. [DP] 1970번 건배 https://www.acmicpc.net/problem/1970 알고리즘 Dynamic Programming Top - Down (시간초과) Bottom - Up (통과) 풀이 포인트 건배를 크로스해서 할 수 없음 $i$번째 사람과 $j$번째 사람이 건배를 했다면 그 두사람 기준으로 양 옆 사람들이 건배를 하는 가짓수로 문제를 나눌 수 있음 이를 이용해 DP 점화식을 세울 수 있음 Dynamic Programming DP 테이블을 아래와 같이 정의한다. $dp[i][j]$: $i$번째에서 $j$번째까지의 사람이 건배를 할 수 있는 최대 쌍의 개수 건배를 크로스해서 할 수 없으므로 아래와 같이 문제를 sub-problem으로 쪼갤 수 있다. 문제를 일반화하기 위해 $i$사람과 $j$번째 사람이 건배를 한.. 2022. 1. 9. [DP] 10844번 쉬운 계단 수 https://www.acmicpc.net/problem/10844 알고리즘 Dynamic Programming 풀이 포인트 계단 수는 각 자리 수와 바로 옆의 수가 1만큼만 차이가 나는 수를 의미한다. Dynamic Programming DP로 해결할 수 있는 문제의 특징은 $n$까지의 상황이 $n+1$의 상황에 영향을 미친다는 것이다. 이러한 점화식이 성립이 되면 $n+1$의 상황을 생각할 때 그 이전의 상황, 즉 $n,n-1$번째의 상황을 심각하게 고려할 필요가 없다. 이 문제도 비슷하게 풀 수 있다. $n$자리의 계단 수의 개수를 구했다고 생각해보자. $n+1$자리의 계단수의 개수를 구하기 위해서는 $n$번째 자리만 고려하면 된다. 계단수가 되기 위한 조건이, 바로 옆 자리수와 1만큼만 차이가 나.. 2022. 1. 9. [DP] 15990번 1,2,3 더하기 5 https://www.acmicpc.net/problem/15990 알고리즘 Dynamic Programming 풀이 포인트 같은 숫자를 여러번 사용할 수 있지만 연속적으로 사용할 수 없다는 점 Dynamic Programming 같은 숫자를 연속적으로 사용할 수 없다는 점에 착안하여, DP 테이블을 2차원으로 정의한다. $dp[i][j]$: 맨 마지막 수가 $j$면서 정수 $i$를 만들 수 있는 경우의 수 $1+2+2$: $dp[5][2]$에 포함되는 경우의 수임 점화식 $j == 1$이면, $dp[i][j] = dp[i-j][2] + dp[i-j][3]$ $j == 2$이면, $dp[i][j] = dp[i-j][1] + dp[i-j][3]$ $j == 3$이면, $dp[i][j] = dp[i-j][1.. 2022. 1. 9. [DP] 9095, 15988번 1,2,3 더하기 https://www.acmicpc.net/problem/9095 https://www.acmicpc.net/problem/15988 알고리즘 Brute Force Dynamic Programming 풀이 포인트 같은 숫자를 여러번, 연속적으로 사용해도 된다는 점 정수 n을 구성하는 숫자의 순서는 상관 없다는 점 1+1+2, 1+2+1, 2+1+1은 모두 다른 경우의 수 정수 n을 구성하는 숫자의 개수의 제한이 없다는 점 Brute Force 문제에서 n은 11보다 작다. 따라서 n은 최대 10개의 수로 구성될 수 있다. 그러면 각 자리마다 가능한 정수 (1,2,3)를 모두 놓아봄으로써 가능한 경우 (그 정수들의 합이 n)만 체크해주면 된다. Brute Force로 프로그래밍할 때, 재귀를 이용하는 것을.. 2022. 1. 9. 이전 1 2 3 다음
