문제 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 로봇 청소기와 점프를 합쳐 놓은 듯한 문제였다. 문제 유형은 다이나믹 프로그래밍이면서도, 구현 능력도 요구하는 문제였다. 문제에서 고려할 중요한 조건은 다음과 같다. 1) 가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 2) 파이프가 놓여진 방향에 따라 회전 방향이 결정된다. 3) 회전 방향에 따라 특정 칸이 무조건 비어있어야 한다. dir..
문제 www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 이항 계수라는 개념을 모르면 풀기가 어려운 문제였다. 비슷한 문제인 이항 계수 1 같은 경우 N이 최대 10으로 작기 때문에 재귀적으로 코드를 작성하거나 itertools모듈을 이용해도 풀이가 가능했다. 하지만, 이 문제는 N이 최대 1000으로 O(N^2)시간의 알고리즘을 구성해야 한다. 따라서 바텀업(Bottom-up) 방식으로 이항 계수를 구현했다. MOD계산을 해주는 것도 잊으면 안된다. 코드 import sys n, k = map(int, sys.stdin.re..
문제 www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 풀이 처음엔 단순한 그래프 문제로 생각했는데, 잘 풀리지 않았다. 곰곰히 생각해보니 이전에 프로그래머스에서 풀었던 등굣길 문제와 유사했다. 좌표 (0, 0)부터 (n-1, n-1)까지 순회하며 현재 좌표(x, y)에서 오른쪽과 아래쪽으로 갈 수 있는지 검사하고, 만약 갈 수 있다면 dp[nx][ny]에 dp[x][y]를 더해준다. 이때 dp[y][x] == 0이면 건너뛰는 방식으로 최적화를 해줄..
동적 계획법 푸는 방법 (DP 풀이) 알고리즘 중 하나인 동적 계획법, 사실 알고리즘 자체보다는 순발력을 요하는 경우가 잦아 많은 연습이 필요한 알고리즘이다. 이러한 동적 계획법에 대해 소개하고 어떻게 풀이해야 하는지에 대한 글이 있어 소개하고자 한다. 결론은 많은 연습과 직관이지만, 풀이 단계를 체계적으로 나누고 실제로 적용해봄에 의의가 있다고 생각된다. (원문: www.geeksforgeeks.org/solve-dynamic-programming-problem/) 동적 계획법(DP, Dynamic Programming)은 다항식 시간의 특정 유형의 문제를 해결하는 기술이다. 동적 계획법은 지수 시간의 브루트 포스 방식보다 빠르며 정확하다. 동적 계획법을 풀기 위해선 선행 학습되어야 할 내용들이 있다...
문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 유사한 문제들은 많이 풀어보았다. 1, 2, 3을 만들 수 있는 경우의 수를 dp테이블에 베이스로 저장해둔다. 점화식은 다음과 같다. dp[n] = dp[n-1] + dp[n-2] + dp[n-3] (3
