DP

[백준(BOJ)] #1520- 내리막 길 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 풀이 DFS + 동적 계획법 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming)이란? 동적 계획법(Dynamic Programming), 다이나믹 프로그래밍, DP라고 불리는 이 알고리..

[백준(BOJ)] #1562- 계단 수 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 해당 문제는 쉬운 계단 수 문제의 심화 버전이라고 볼 수 있습니다. 계단 수를 구하는 것은 같지만, 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개인지를 구해야 합니다. 쉬운 계단 수를 풀때와 마찬가지로 동적 계획법을 사용했고, 추가로 비트마스크를 사용했습니다. 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic..

[백준(BOJ)] #10844- 쉬운 계단 수 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 동적 계획법을 사용해 입력받은 자리 수의 계단수에 대한 경우의 수를 구할 수 있습니다. 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming)이란? 동적 계획법(Dynamic Programming), 다이나믹 프로그래밍, DP라고 불리는 이 알고리즘은 무엇일까요?? 동적 프로그래밍? 저는 이 ..

[백준(BOJ)] #1103- 게임 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 문제 풀이 처음에 DFS 알고리즘을 적용하여 풀었는데 시간 초과가 발생했습니다. 다른 풀이를 참고하여 DP를 함께 적용하여 풀 수 있다는 것을 알았습니다. 문제 풀이는 다음 이 블로그의 풀이를 참고하여 풀었습니다. 2022.07.12 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) DFS란? DFS(..

[백준(BOJ)] #11053- 가장 긴 증가하는 부분 수열 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 가장 긴 증가하는 부분 수열은 동적 계획법의 대표적인 문제 중 하나로 LIS(Longest Increasing Subsequence)로 잘 알려져 있습니다. 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우..

[백준(BOJ)] #14728- 벼락치기 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 문제 풀이 2022.08.12 - [PS/백준] - [백준(BOJ)] #12865- 평범한 배낭 (파이썬, PyPy3) [백준(BOJ)] #12865- 평범한 배낭 (파이썬, PyPy3) 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 ..

[백준(BOJ)] #12865- 평범한 배낭 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 풀이 이 문제는 대표적인 냅색 문제(Knapsack Problem)입니다. 냅색 문제는 배낭 문제라고도 불리며 동적 계획법을 사용해 푸는 문제 중 유명한 유형의 문제입니다. 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우는..

[백준(BOJ)] #1005- ACM Craft (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 풀이 이 문제는 위상 정렬과 동적 계획법 알고리즘을 사용하여 해결할 수 있습니다. 2022.08.08 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 위상 정렬(Topology Sort) [파이썬으로 배우는 알고리즘] 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)이란? 위상 정렬(Topology Sort)은 순서가 정해져 있는 작업을 수행해..

[백준(BOJ)] #1463- 1로 만들기 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 이 문제는 동적 계획법을 사용하여 풀 수 있습니다. 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming)이란? 동적 계획법(Dynamic Programming), 다이나믹 프로그래밍, DP라고 불리는 이 알고리즘은 무엇일까요?? 동적 프로그래밍? 저는 이 말을 처음 접했을 때 의미에 대해 생..

[파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)이란? 동적 계획법(Dynamic Programming), 다이나믹 프로그래밍, DP라고 불리는 이 알고리즘은 무엇일까요?? 동적 프로그래밍? 저는 이 말을 처음 접했을 때 의미에 대해 생각을 해봤는데 알고 보니까 이름하고는 별 상관이 없더라구요..ㅋㅋㅋㅋㅋ 동적 계획법은 어떤 문제를 여러개의 작은 문제로 나눠 해결하고 그 결과를 저장을 했다가 큰 문제를 풀 때 사용하는 문제 풀이 기법입니다! 즉, 한 번 푼 문제는 다시 풀지 않게 되는 것이죠. 분할 정복 알고리즘과 비슷하다고 생각하실 수도 있는데 해결한 문제를 반복적으로 해결하는 분할 정복과는 달리 동적 계획법은 이미 푼 문제는 기억하여 다시 풀지 않기 때문에 부분 문제가 중복된다면 더욱 효율적이라고 볼..