전체 글105 [DP] 2578번 계단 오르기 https://www.acmicpc.net/problem/2578 알고리즘 Dynamic Programming 풀이 포인트 bottom-up 구현 세 계단을 연속적으로 오르지 못하는 제한 조건을 활용하여 점화식 변형 Dynamic Programming 전형적인 dp 문제로, i번째 계단을 방문했을 때, 그 상태를 기반으로 i+1번째 계단, i+2번재 계단을 방문할 때의 점수 상태를 업데이트하면 된다. 이때, 연속적으로 3개의 계단을 방문하면 안되므로, i번째 계단 방문 상태가 이미 연속 두 계단을 방문한 상태라면 i+1번째 계단은 방문 못하고 i+2번째 계단만 방문할 수 있다. 만약, 연속 두 계단이 아닌, 연속 하나의 계단만 방문한 상태라면 i+1,i+2 계단 모두 방문할 수 있다. 우선 2차원 dp .. 2022. 1. 29. [BFS] 15558번 점프 게임 https://www.acmicpc.net/problem/15558 알고리즘 BFS 풀이 포인트 하나의 상태를 나타내는 조건을 그대로 옮기면 메모리 초과가 난다는 점 BFS 처음에 이 문제를 접했을 때 하나의 상태를 나타내는 조건이 여러개인, 전형적인 조금 어려운 BFS문제라고 생각했다. 그 조건은 아래와 같다. x,y 좌표 몇초가 지났는지 따라서 처음에 3차원 visited 배열을 아래와 같이 정의했다. visited = [[[-1]*n for _ in range(n)] for _ in range(2)] 이렇게 하니 메모리 초과가 발생했다. 문제의 제한 조건을 잘보면, $1 2022. 1. 13. [BFS] 1175번 배달 https://www.acmicpc.net/problem/1175 알고리즘 BFS 풀이 포인트 하나의 state을 나타내는 조건들이 여러개라는 점 BFS 문제에서 주어진 조건들이 여러개라 이를 state로 연관하고 그에 맞게 프로그래밍을 하는게 약간 어려운 문제이다. 먼저 주의해야하는 조건을 정리해보자. 선물이 2개이고 이를 모두 배달하기 전까지 배달은 끝나지 않는다. 두 개의 선물을 각각 A,B라고 할 때, 아래 네 개의 상태가 존재한다. A만 배달한 상태 B만 배달한 상태 두 개 모두 배달하지 않은 상태 둘 모두 배달한 상태 같은 방향으로 두 번 연속 이동할 수 없다. 따라서 (i,j)를 방문했을 때, 어느 방향을 보고 있는지에 따라서 동,서,남,북 네 개의 상태가 존재한다. 이런 문제 의식을 가지고.. 2022. 1. 13. [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. 이전 1 ··· 14 15 16 17 18 다음
